(Directi Interview question) Given an array A and m queries

general
, , ,
1

Given an array A and m queries each query is integer T

For each query find index i and j such that

| (|sum of elements from i to j| - T) |
is minimum

where |x| is abs(x) and array can have negative numbers as well

I was asked this question in directi interview. I had the solution of finding all possible sum and store their indices and sort.

so there will be n*n sums possible.

That would take O(nn log(n*n))

Now for each query binary search T .That would be O(m* log(n* n))

But he asked to optimize it.I didn’t clear the round.

Can anyone give hint for this?

I asked the question on Stackoverflow as well.

1 Like
2

What’s the range of possible values of T? If that’s not to large you can make a table using dp in O(T*n)

3

If we disregard potential constraints on the range of values of A and T, an optimal approach also depends on the relationship between n and m :

If 2n\times log(n) > m then the solution described on StackOverflow (with the complexity of O(n\times log(n) + m\times n) for partial sum sorting) works the best; otherwise your solution is better.

4

I didn’t ask that but I think it will more than number of queries(m) else queries would be repeating.

5

there are two cases :-

  1. if T <= 0 then that means we need to find two indexs i and j such that |sum of elements from i to j| is minimum
  2. else if T > 0 then we need to find the sum of elements such that sum is closest to T which will give us minimum answer