Amazon Interview Question
Software Engineer / DevelopersTeam: SDE
Country: India
Interview Type: In-Person
It doesn't need to start with 0 but a range i...j having sum 0 implies ranges 0...i-1 and 0...j having the same sum (0...i-1 + i...j = 0...j), so if i...j = 0, 0...i-1 = 0...j
It doesn't need to start with 0 but a range i...j having sum 0 implies ranges 0...i-1 and 0...j having the same sum (0...i-1 + i...j = 0...j), so if i...j = 0, 0...i-1 = 0...j
But I guess this is not working with the following example
{-1,2,-4,3,1,2}
The answer would be {-1,2,-4,3,1,2}. But this would give answer as {-4,3,1}.
{-1,2,3,-4,0,0,2,4}
how will it work ?
can you run me through this example?
sum array would be {-1,1,4,0,0,0,2,6}
duplicates will be 0 so it will be {0,0}
but it should be -1,2,3,-1,4,0,0
you should consider 0 differently.i think,if index of last 0 is >found duplicate indexes difference than answer would be 0 to the index of last 0.
@sachin: Yes, you're right. I forgot to consider that one special case. All we need to do to fix this is add the extra check you're proposing. Either that, or we can prefix 0 to the sum array before we run the algorithm that involves the HashMap (that's the easiest way to do it, in my opinion).
instead we could use kadane's algorithm.....instead of finding max element we can compare with zero.
Kadane's Algorithm cannot be used here.
We can find all sub strings of this array and extract the longest sub string which has sum 0.
See (nobrainer .co .cc) for the implementation in JAVA
For every 0 <= i < arr.length, find the sum arr[0] + ... + arr[i] and store it as sum[i] a sum array. In fact, sum[n+1] = sum[n] + arr[n+1], so this can be obtained in O(n). Essentially, we want to find two duplicates in this sum array that are as far apart as possible, since a duplicate in a sum array means there are two subarrays [0...i] and [0...j] that have the same sum, and so [i+1...j] will have sum 0 (indexes inclusive on both ends).
- eugene.yarovoi February 02, 2012Build a map that maps each value in the sum array to the largest index at which it occurs. This can be done simply by going through the elements of the sum array and adding the key-value pair (element, index where it was found) to the map for each element (O(n) expected time). If the same element is seen twice, the subsequent map inserts for the element will overwrite the earlier entries made for it. Finally, scan from the beginning of the sum array and for each element, check the map for the latest-occurring duplicate value, if any (expected O(1) per element, O(n) for the whole array). Keep track of the start and end index of the largest endIndex - startIndex difference seen so far, and report that as the answer when you're done scanning the array.
The entire algorithm can be done in linear time.