Amazon Interview Question SDE1s
Country: -
@nice algos
Implementation in python of the same:
def subArraySumZero(intList):
sumHash= { }
sumSoFar = 0
index = 0
for index in range(0,len(intList)-1):
sumSoFar += intList[index]
if sumSoFar in sumHash.keys():
print intList[ sumHash[sumSoFar] +1 : index+1]
return
else:
sumHash[sumSoFar] = index
print "NO SUCH RESULT"
testList = [2, 3, -4, 9, -1, -7, -5, 6, 5 ]
subArraySumZero(testList)
Nice effort & sol, however I think you method may not generate all subsets that sum to zero.
Example:-
1. It is possible for a zero sum subset to exist that escapes your method. What if I have this array
"2 3 -4 9 -1 -7 -5 6 5 0 -2" --> I have added 0 & -2 at the end. However
(2,0,-2) will not show up in your method.
I don't agree with the subarray definition of some of the posts here. In mathematics {1,7} is definitely a subset of {1,2,3,5,6,7}. If that's the principle definition of subset we will certainly make similar inferences/assumptions for defining sub-array. If that's not the case the poster must specifically state that subarray is contiguous.
@Itanium as the people have already mentioned that the Q is for subarray not subset which needs to be contiguous.
@algos However there is a cost in this solution of space O(n).
geeksforgeeks.org/find-subarray-with-given-sum/
This above article explains an O(n) solution which requires no extra space and can be used for any target sum and not only 0.
@vik:the solution you have suggested by the link doesn't work for negative numbers but here we want the solution for both positive and negative numbers.
@Vik
Mathworks definition of subarrays:
Definition of Subarrays
In Phased Array System Toolbox™ software, a subarray is an accessible subset of array elements. When you use an array that contains subarrays, you can access measurements from the subarrays but not from the individual elements. Similarly, you can perform processing at the subarray level but not at the level of the individual elements. As a result, the system has fewer degrees of freedom than if you controlled the system at the level of the individual elements.
It clearly states that - " A subarray is an accessible subset of array elements". Although the context of subarray definition is different here I am sure Mathworks would adopt consistent definition across their product. So what applies for one should apply for all. I wish I could give the link but the comments wont allow me to post hyperlinks. Besides there are tons of online discussions that make deliberate distinction between normal sub-arrays and contiguous sub-arrays.
@stan: If you find 0 in the cumulative sum, it needs to equal to the start of array.
One thing missed by the solution is the value 0 itself, which would also be a subarray with a 0 sum.
Let's try this example:
2 -1 -1 3 5
Sum:
2 1 0 3 8
So this method is great in case of the sub-array is in the middle or at the end of the parent array, but if the sub-array is at the beginning. this method fails, So we need to check also if the sum contains "0" and then consider all the values starting from it, to the start of the array
sum : 0 2 1 0 3 8 (add 0 at start of sum array)
index: -1 0 1 2 3 4
here 0 is duplicate number with start index = -1 and end = 2
so sub-array with sum zero is from start+1 to end i.e.. index 0 - 2 (2 -1 -1)
He algo is nice.
However, In java it is not easy using the hashMap to get the key of values if we use hashmap(index,value). And if we want to use hashtable(value,index), the array cannot have dup as it will have the same key and cover the previous value. We can use a biMap to handle it.
if we don't want to use biMap here is my solution using two hashMap.
static void sumEqZero()
{
int [] tmp= {2,-3,1,2,-2,3,-1,4,2};
HashMap <Integer,Integer> sum = new HashMap<Integer,Integer>();
HashMap <Integer,Integer> revSum = new HashMap <Integer,Integer>();
//sum.put(0, tmp[0]);
int sumSofar = 0;
for (int i = 0; i< tmp.length; i++)
{
sumSofar += tmp[i];
if(sum.containsValue(sumSofar))
{
System.out.println(Arrays.toString(Arrays.copyOfRange(tmp,revSum.get(sumSofar)+1,i+1)));
sum.put(i,sumSofar);
revSum.put(sumSofar, i);
}
if (sumSofar == 0)
{
System.out.println(Arrays.toString(Arrays.copyOfRange(tmp, 0,i+1)));
sum.put(i,sumSofar);
revSum.put(sumSofar, i);
}
else
{
sum.put(i,sumSofar);
revSum.put(sumSofar, i);
}
}
//System.out.println(sum.toString());
}
Found in Stackoverflow:
This algorithm will find all subarrays with sum 0 and it can be easily modified to find the minimal one or to keep track of the start and end indexes. This algorithm is O(n).
Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element.
Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j < k, then the sum of the input till j is equal to the sum till k and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k.
NOTE: if j + 1 == k, then k is 0 and that's it! ;)
NOTE: The algorithm should consider a virtual tmp[-1] = 0;
NOTE: An empty array has sum 0 and it's minimal and this special case should be brought up as well in an interview. Then the interviewer will say that doesn't count but that's another problem! ;)
The implementation can be done in different ways including using a HashMap with pairs but be careful with the special case in the NOTE section above.
Example:
int[] input = {4, 6, 3, -9, -5, 1, 3, 0, 2}
int[] tmp = {4, 10, 13, 4, -1, 0, 3, 3, 5}
Value 4 in tmp at index 0 and 3 ==> sum tmp 1 to 3 = 0, length (3 - 1) + 1 = 4
Value 0 in tmp at index 5 ==> sum tmp 0 to 5 = 0, length (5 - 0) + 1 = 6
Value 3 in tmp at index 6 and 7 ==> sum tmp 7 to 7 = 0, length (7 - 7) + 1 = 1
UPDATE
Assuming that in our tmp array we end up with multiple element with the same value then you have to consider every identical pair in it! Example (keep in mind the virtual '0' at index '-1'):
int[] array = {0, 1, -1, 0}
int[] tmp = {0, 1, 0, 0}
By applying the same algorithm described above the 0-sum subarrays are delimited by the following indexes (included):
[0] [0-2] [0-3] [1-2] [1-3] [3]
Although the presence of multiple entries with the same value might impact the complexity of the algorithm depending on the implementation, I believe that by using an inverted index on tmp (mapping a value to the indexes where it appears) we can keep the running time at O(n).
This algorithm will find all subarrays with sum 0 and it can be easily modified to find the minimal one or to keep track of the start and end indexes. This algorithm is O(n).
Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element.
Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j < k, then the sum of the input till j is equal to the sum till k and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k.
NOTE: if j + 1 == k, then k is 0 and that's it! ;)
NOTE: The algorithm should consider a virtual tmp[-1] = 0;
NOTE: An empty array has sum 0 and it's minimal and this special case should be brought up as well in an interview. Then the interviewer will say that doesn't count but that's another problem! ;)
The implementation can be done in different ways including using a HashMap with pairs but be careful with the special case in the NOTE section above.
Example:
int[] input = {4, 6, 3, -9, -5, 1, 3, 0, 2}
int[] tmp = {4, 10, 13, 4, -1, 0, 3, 3, 5}
Value 4 in tmp at index 0 and 3 ==> sum tmp 1 to 3 = 0, length (3 - 1) + 1 = 4
Value 0 in tmp at index 5 ==> sum tmp 0 to 5 = 0, length (5 - 0) + 1 = 6
Value 3 in tmp at index 6 and 7 ==> sum tmp 7 to 7 = 0, length (7 - 7) + 1 = 1
What's about this?
static void subArraySumsZero() {
int [] seed = new int[] {1,2,3,4,-9,6,7,-8,1,9};
int currSum = 0;
HashMap<Integer, Integer> sumMap = new HashMap<Integer, Integer>();
for(int i = 0 ; i < seed.length ; i ++){
currSum += seed[i];
if(currSum == 0){
System.out.println("subset : { 0 - " + i + " }");
}else if(sumMap.get(currSum) != null){
System.out.println("subset : { " + (sumMap.get(currSum) + 1) + " - " + i + " }");
sumMap.put(currSum, i);
}else
sumMap.put(currSum, i);
}
}
public static void main(String[] args) {
int[] a= {4, 6, 3, -9, -5, 1, 3, 0, 2} ;
int[] s = new int[a.length];
s[0]=a[0];
for (int i=1; i < a.length; i++)
{
s[i]=a[i]+s[i-1];
}
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
Hashtable<Integer, Integer> ht = new Hashtable<Integer, Integer>();
for (int k=0; k< s.length;k++)
{
Integer tmp= hm.put(s[k], k);
if(tmp !=null)
{
System.out.println("Sub-Array index is from: "+(tmp+1)+" to "+k);
}
else if (s[k]==0)
{
System.out.println("Sub-Array index is from 0 to "+k);
}
}
I think this solution will work as well
public static int[] findSubArrWithSumZero(int[] arr) {
int sum = 0;
for (int i=0; i < arr.length; i++) {
sum += arr[i];
if (sum == 0) {
return Arrays.copyOfRange(arr, 0, i+1);
}
}
if (sum == 0) {
return arr;
}
for (int i=0; i < arr.length-1; i++) {
sum -= arr[i];
if (sum == 0) {
return Arrays.copyOfRange(arr, i+1, arr.length-1);
}
}
return null;
}
It s very easy ques..i dnt knw y amazon askng these knd of ques?
Anyway i m gng 2 ans ths..
int a[]={2,3,4,-5,-4,4,6}
constraint :
subarray sum shld be equal to zero ;But we dnt knw where the subarray present in array.
so use TRAVERSING METHOD..
1)Pick one starting element i;and j=i+1;
2)So,iterate through the array for more elements i,i+1 etc.,
3)now compare the subarray with elements
if(arr[i]==sum)//means arr[i]==0;
sample code:
//starting point
for (i = 0; i < n; i++)
{
subarray_sum = arr[i];
for (j = i+1; j <= n; j++)
{
if (subarray_sum == sum)
{
printf ("Sum found between indexes %d and %d", i, j-1);
return 1;
}
refer this..
Compute a cumulative sum array where cum_sum[i] holds the sum of all array elements up to index i. If for any i and j, cum_sum[i] == cum_sum[j], this means that the sub array from index i to index j has a sum of 0. Therefore search for all pairs of indices with same value in cum_sum and you have all sub arrays with zero sum.
Time complexity O(n)
Well time complexity is not O(n) if you search in cum_sum. Let`s say you wanna find element which equals to cum_sum[0], you need to iterate through the array which is O(n), if not found, again you have to pick up cum_sum[1] and do it again. The time complexity is O(n2). To solve this, we need a hashmap of which key is the sum and value is subarray indices.
time complexity is O(n) and space complexity is O(n)
- algos October 02, 2013hash the sum from 0 to i for all array elements, i.e sum[i] = sum of all elements from a[0] to a[i] and corresponding index as data to key (starting from -1 to n)
ex: 2 3 -4 9 -1 -7 -5 6 5
sum to enter in hash table : 0 2 5 1 10 9 2 -3 3 8
index to enter in hash table: -1 0 1 2 3 4 5 6 7 8
hash sum as key and its corresponding index as data. and while hashing check if any sum is already exists in hash table
here there is one duplicate number that is 2 in sum array... the indexes of duplicate numbers is 0 and 5, so we need to take sum from index 1 to 5 in original array that is 3 to -7
if there are no duplicates in sum array then sub-array with sum ZERO doesn't exists in given array