Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




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

subarray=>contiguous slice
take cumulative sum of the array; if the cumulative sum has duplicate numbers then there is subarray which sums to zero;

for(i=1;i<n;i++)
c[i]=c[i-1]+input[i];
if(duplicates in array 'c')
then true
Complexity-O(n);

- luffy September 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You'll also have to check for a 0 in the running sum array. This is an edge case for 2, -2, 3, 4

- Anonymous September 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

To make it perfect add one more line. Before loop
1. c[0]=input[0];
And then update if condition saying
if(a zero in array 'c' or duplicate in array 'c')
return true.

- tezkrishna September 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if sub-array means contiguous m/m , there we can search for '0' in cumulative array. what is the need to search for duplicate ???

- adi October 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do we need to search for duplicates in the sub-array? Checking for '0' in the sub-array should suffice.

- Anonymous January 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In better words -

The subarray can starts at any index. While iterating keep track of the sum for each index ( this sum will be from this index to the end, zero if the sum became zero while calculating). No extra array needed, we can use the same array to store the sum for each index after the value is read.

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

what is there is no duplicate?

for example:
for Array 1,-1,3
cumulative array will be 1,0,3

- Leon April 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

- make new array sums that sums[i] = sum (input[0],..,input[i]) -> O(n)
- find any duplicate elements in sums - O(n log n) (sort + iteration)

Total complexity - O(n log n)

- Anonymous September 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if subarray => any random elements picked from array
its an np-complete

- luffy September 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if the array is
2,-1,3,-4,1,2,3
I don't think your solution will work for that

- noMAD September 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Am sorry, your solution is perfect.
And to add, to find the exact subarray [i,j]
i = the position of 1st occurance + 1
j = the position of second occurance in the new "SUM" array

In this example, i = 1 + 1 = 2
j = 4
Hence in the original array [2,4] is the sub array

- noMAD September 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

for the n*log(n) solution, you'll also have to check for a 0 in the running sum array. This is an edge case for 2, -2, 3, 4

- Anonymous September 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my O(N^2) solution:
I didn't 100% understand the O(N+N) talk above...

public bool foundSumZero(int[] arr)
{
    return findSubSumWithSkip(arr, 0, 0);
}
private bool findSubSumWithSkip(int []arr, int pos, int subSum)
{
    if (pos == arr.length)
    {
        return false;
    }
    return findSubSumWithSkip(arr, pos + 1, subSum) ||
           findSubSum(arr, pos, subSum);
}

private bool findSubSum(int []arr, int pos, int subSum)
{
    if (pos == arr.length)
    {
        return false;
    }

    subSum = subSum - arr[pos];

    if (subSum == 0)
    {
        return true;
    }

    return findSubSum(arr, pos + 1, subSum);
}

- Ninja Coder October 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

boolean find0SubArray(int [] array){
//Get array prefix sums w.r.t first element till current element

for(i=1;i<n;i++)
    array[i]=array[i]+array[i-1];

//Check for duplicate elements in the array - if present there is a sub array of sum 0

HashTable ht = new HashTable<Integer,Integer>();
for(i=0;i<n;i++)
{
     if (ht.get(array[i])==null)
            ht.put(array[i],1);
     else
            return true;
}

return false;

}

- sk007 February 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is a DP problem

- Anonymous January 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] findSubArrayWithZeroSum(int[] arr)
{
    Array.Sort(arr);
   
    for(int i=0; i<arr.Length-1; i++)
    {
      int target=0-arr[i],sum=0;
      for(int j=i+1; j<arr.Length; j++)
      {
          sum+=arr[j];
          if(sum==target)
          {
              int[] result = new int[j-i+1];
              Array.Copy(arr,i, result,0, result.Length); // subarray from [i...j]
              return result;
          }
      }
    }
    return null;

}

- Anonymous February 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

sumbset sum, NP-complete

- Alvin September 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The best solution that I can think of is in n*n complexity. Take an extra array temp, for the first iteration fill the temp[0] = arr[0], temp[1] = arr[0] + arr[1], so on and so forth, till end. For second iteration consider first element of the array and delete it from every element of array temp from second to last, similarly do the same for third element. and every time jsut keep on checking if at any point of time the temp array contains value = "0" . This way we would have considered all possible cases in n*n complexity.

- Ishant September 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ishant your solution does not work.
Consider a,b,c,d
Your solution considers only a,b,c,d,a+b,a+b+c,a+b+c+d,b+c,b+c+d,c+d.
It does not consider a+c.

- gavinashg@yahoo.com September 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it works

- rocks September 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

we dont need to consider a+c.. bcoz thy are asking for subarray that means it needs to be continuous..

if you dont consider them to be continuous then it would be a NP complete problem.. ishant's solution works fine with complexity n(n+1)/2===n^2

- rocks September 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Perhaps creating a hash table instead of an array for sums will help. Any duplicate entry for the same sum would mean that the sub-array added up to 0. We only need to answer the existence of a sub-arrray with sum and this should work.

Complexity should be O(n+n), considering the hashing is a simple one.

- Anonymous September 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

find all possible subsets and check if their sum is 0.
time complexity O(2^n).
but i think a better solution will exist and will be posted by some geniuos.

- techcoder September 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sub-array usually means a slice. a[i], a[i+1], ..., a[j]. Which is easier and can be done in O(n) (average) time and O(n) space.

- Anonymous September 24, 2011 | 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