Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
You'll also have to check for a 0 in the running sum array. This is an edge case for 2, -2, 3, 4
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.
if sub-array means contiguous m/m , there we can search for '0' in cumulative array. what is the need to search for duplicate ???
Why do we need to search for duplicates in the sub-array? Checking for '0' in the sub-array should suffice.
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.
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);
}
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;
}
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;
}
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 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.
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
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.
subarray=>contiguous slice
- luffy September 26, 2011take 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);