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[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).

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.

- eugene.yarovoi February 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hello world February 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi February 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi February 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anonymous February 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sachin June 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 June 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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).

- eugene.yarovoi July 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Understood, nice one!!

- hello world February 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

instead we could use kadane's algorithm.....instead of finding max element we can compare with zero.

- Shreyas February 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anony February 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anony February 07, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More