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);

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

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

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

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.

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

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

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

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

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

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.

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

what is there is no duplicate?

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

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)

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

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

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

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

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

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

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);
}``````

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;

}``````

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

this is a DP problem

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;

}``````

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

sumbset sum, NP-complete

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

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.

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

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

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

it works

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

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

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

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.

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.

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

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.

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.