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

algorithm
binary-search
query
sorting

#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.


#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 imes log(n) > m then the solution described on StackOverflow (with the complexity of O(n imes log(n) + m imes n) for partial sum sorting) works the best; otherwise your solution is better.


#4

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

#5

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