## Amazon Interview Question for Software Engineer / Developers

Team: SDE
Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
6
of 6 vote

For every 0 <= i < arr.length, find the sum arr + ... + 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).

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

Comment hidden because of low score. Click to expand.
0

Does it need to start at 0 index? It can start from any index right?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

{-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

Comment hidden because of low score. Click to expand.
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.

Comment hidden because of low score. Click to expand.
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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

Understood, nice one!!

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.