Amazon Interview Question
Developer Program EngineersLets take input array as a[]={-3,2,4,-6,-8,10,11}
Make an array b [] such that b[i]=b[i-1]+a[i];
So b[]={-3,-1,3,-3,-11,-1,10}
Now all those pairs at indexes (i,j)in array b[] having equal numbers are the indexes of subarrays from (i+1,j) having sum as zero.
Finding all pairs in O(n) can be done by using map.
Same idea explained:
b[i] = b[i-1] + a[i] - this means that b[i] = sum(a[0],..., a[i]);
we have to find some (i, j) so: a[i] + a[i+1] + ... + a[j] = 0. But a[i] + a[i+1] + ... + a[j] = b[j] - b[i-1].
when creating the map using b values, the key in map is the value from b and the value in map is the index of from b. if a new key exists, this means we found a solution.
in the ex:
-3 => 0
-1 => 1
3 => 2
-3 => 3 (-3 exits, so, the solution is from first index + 1, 1, to current index, 3)=2, 4 , -6
-11 => 4
-1 => 5 (-1, exists, so, the solution is from 2 (1+1), to 5 = 4, -6, -8, 10
10 => 6
We found both solutions (or none, if there are no duplicates in b).
this doesn't give all pairs , what about the subset { -3,2,4,-6,-8,11} they sum to 0 too
It's a trivial solution with bad time complexity :( . But still a solution :) !!
This is the first solution that strikes me.
We can sort the array in O(nlogn) using quicksort.
Then, we will generate all possible sum of the negative number and store the corresponding elements using Map.
So two map are created with all possible sum of positive numbers and negative numbers respectively. Sort these map.
Check it in these two map, two numbers are equal(Ignore the sign, obviously the sum of negative is always negative). All elements of negative and positive numbers stored corresponding to those two location in two map(+ve number and -ve number) will be the answer.
try to do it in O(n)
- manni October 29, 2010