Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
The example suggest sub-array. 2,1, -1,-1,-1, is missing from the output, for example...
need to evaluate all possibilities, O(2^n)
#include <iostream>
#include <math.h>
void print(int k, int* array, int size)
{
int p = 0;
while(k > 0)
{
if (k & 1)
{
std::cout << array[p] << ",";
}
++p;
k = k >> 1;
}
std::cout << "\n";
}
void find_zero(int* array, int size)
{
int n = pow(2, size);
for (int i = 1; i < n; ++i)
{
int k = i, p = 0, sum = 0;
while (k > 0)
{
if (k & 1)
{
sum += array[p];
}
k = k >> 1;
++p;
}
if (sum == 0)
{
print(i, array, size);
}
}
}
int main()
{
int a[7] = {2, 1, -1, 0, 2, -1, -1};
find_zero(a, 7);
return 0;
}
output:
1,-1,
0,
1,-1,0,
1,-1,
2,-1,-1,
1,0,-1,
2,-1,0,-1,
-1,2,-1,
-1,0,2,-1,
1,-1,
2,-1,-1,
1,0,-1,
2,-1,0,-1,
-1,2,-1,
-1,0,2,-1,
2,-1,-1,
2,1,-1,-1,-1,
2,0,-1,-1,
2,1,-1,0,-1,-1,
2,-1,-1,
1,-1,2,-1,-1,
0,2,-1,-1,
1,-1,0,2,-1,-1,
public void findSumZero(int [] arr){
int sumArray [] = new int[arr.length];
sumArray[0] = arr[0];
for(int i=1 ; i<arr.length ; i++){
sumArray[i] = sumArray[i-1] + arr[i];
}
for(int i=0;i<sumArray.length;i++){
for(int j = i+1; j<sumArray.length;j++){
if(sumArray[i] == sumArray[j] || sumArray[j] == 0){
print(i,j,arr);
}
}
}
}
public void print(int i,int j,int [] arr){
System.out.print("subArray is");
for (int k = i; k<=j;k++){
System.out.print(arr[k] + " ");
}
System.out.println();
}
Is your output missing these subarrays?
{1, -1, 0, 2, -1, -1}
{-1, 0, 2, -1}
{0, 2, -1, -1}
These are also there in the output arrays...Please verify once again.consider all possibilities of 2's and 3's also....
This question is not correct given the examples. [2, 1, -1, 0, 2, -1, -1] is not a 'set'. Nor is [2, -1, -1] (one of the listed answers). Can I ask if the wording of the question should be:
"Given an array of integers, find all the contiguous sub-arrays of the given array whose sum is 0."
If my question is correct, then the example plus answers make sense. This is somewhat similar to the subset sum question though that returns a bool whereas this is expecting all contiguous subarrays that satisfy the sum of zero condition.
if values is small, all between -100~+100, create an array sub[100][10] using the value as index,
first:create a sum array;
second:save subsum and the index in orig arr to array sub[subsum][index];
last: traverse sub[][]
eg orig[2, 1, -1, 0, 2, -1, -1]
then :
sub[0]=[];
sub[1]=[];
sub[2]=[0,2,3,6];
sub[3]=[1,5];
sub[4]=[4];
...
the result is :
orig(0,2],orig(0,3],orig(0,6];orig(2,3];orig(2,6];orig(3,6]
orig(1,5]
first of all, example does not represent sets, secondly this problem is similar to finding two subsets with minimum difference which is a np-complete problem
/// public void findSumZero(int [] arr){
int sumArray [] = new int[arr.length];
sumArray[0] = arr[0];
for(int i=1 ; i<arr.length ; i++){
sumArray[i] = sumArray[i-1] + arr[i];
}
for(int i=0;i<sumArray.length;i++){
for(int j = i+1; j<sumArray.length;j++){
if(sumArray[i] == sumArray[j] || sumArray[j] == 0){
print(i,j,arr);
}
}
}
}
public void print(int i,int j,int [] arr){
System.out.print("subArray is");
for (int k = i; k<=j;k++){
System.out.print(arr[k] + " ");
}
System.out.println();
}\\\
As per example given..the code can be
void printarray(int a[],int start,int end)
{
int i=0;
for(i=start;i<=end;i++)
printf("%d\t",a[i]);
printf("\n");
}
void getsub(int a[],int n)
{
int i=0,j=0;
int b[100];
b[0]=a[0];
for(i=1;i<n;i++)
b[i]=b[i-1]+a[i];
for(i=0;i<n;i++)
{
if(b[i]==0)
{
printarray(a,0,i);
continue;
}
for(j=0;j<i;j++)
{
if(b[j]==b[i])
printarray(a,j+1,i);
}
}
}
For subset code can be
void printarray(int a[],int start,int end)
{
int i=0;
for(i=start;i<=end;i++)
printf("%d\t",a[i]);
printf("\n");
}
int power(int a,int n)
{
while(--n>0)
a=a*2;
return a;
}
void getsubset(int a[],int n)
{
int i=0,j=0;
int set[100];
int ind=0;
int count = power(2,n);
int sum=0;
for(i=0;i<count;i++)
{
sum=0;
ind=0;
for(j=0;j<n;j++)
{
if(i&(1<<j))
{
sum = sum + a[j];
set[ind++]=a[j];
}
}
if(sum==0)
printarray(set,0,ind-1);
}
}
As other people pointed out earlier, it is very vague question. Assumptions I made for this question was:
Print out subsets that sum of numbers in the set is zero
No duplicate is allowed (e.g. "1,0,-1" and "-1,1,0" are the same)
def find_zerosum(inputs):
next_pos = 0
used=[]
current = []
found = {}
for i in range(0, len(inputs)):
used.append(0)
zero_sum(found, inputs, current, used, 0)
def zero_sum(found, ordered, current, used, pos):
if len(current) > 0 and is_zerosum(current) == True:
key = ",".join(str(x) for x in sorted(current))
if found.has_key(key) != True:
found[key] = 1
print key
return
for i in range(pos, len(ordered)):
if (used[i] == 1): continue
new_current = list(current)
new_current.append(ordered[i])
new_used = list(used)
new_used[i] = 1
zero_sum(found, ordered, new_current, new_used, i)
def is_zerosum(numbers):
s = 0
for i in range(0,len(numbers)) :
s+= numbers[i]
return s == 0
a = [2, 1, -1, 0, 2, -1, -1]
i = 0
j = a.length - 1
result = []
def printSubSets(a, i, j, result)
sum = 0
a[i..j].map{|x| sum = sum + x}
if sum == 0 && !result.include?(a[i..j])
result << a[i..j]
end
if(i != j)
printSubSets(a, i, j-1, result)
printSubSets(a, i+1, j, result)
end
end
printSubSets(a[i..j], i , j, result)
puts "The subsets are "+result.to_s
O/p: The subsets are [[1, -1], [1, -1, 0], [0], [-1, 0, 2, -1], [1, -1, 0, 2, -1, -1], [0, 2, -1, -1], [2, -1, -1]]
1. Given A[i]
A[i] | 2 | 1 | -1 | 0 | 2 | -1 | -1
-------+---|----|--------|---|----|---
sum[i] | 2 | 3 | 2 | 2 | 4 | 3 | 2
2. sum[i] = A[0] + A[1] + ...+ A[i]
3. build a map<Integer, Set>
4. loop through array sum, and lookup map to get the set and generate set, and push <sum[i], i> into map.
Complexity O(n)
Assuming that the subset array sum ==0
import java.util.*;
public class Sum_Zero {
/*
* Question: You have an array which has a set of positive and negative
* numbers. Print all the subset sums that which is equal to 0
*/
public void calculateSum() {
int arr[] = { 5, 3, -2, -5, -1, 0, 6, 3, 2 };
int sum = 0;
sum = arr[0];
ArrayList<Integer> arrList;
HashMap<Integer, ArrayList<Integer>> hash = new HashMap<Integer, ArrayList<Integer>>();
/*
* Loop through the array and sum it
*/
int count = 1;
for (int i = 0; i < arr.length; i++) {
sum = arr[i];
arrList = new ArrayList<Integer>();
int j=i+1;
arrList.add(arr[i]);
while (sum != 0 && j < arr.length - 1) {
sum = sum + arr[j];
arrList.add(arr[j]);
j++;
}
if (sum == 0) {
count++;
hash.put(count, arrList);
}
}
for (Map.Entry<Integer, ArrayList<Integer>> entry : hash.entrySet()) {
ArrayList<Integer> arrList1 = entry.getValue();
System.out.println("Subset:" + arrList1);
}
}
}
This will work. The algorithm is the same as most of you have used, i.e. finding subsets. Its just looks fancy i guess.
input = [ 2, 1, -1, 0, 2, -1, -1 ]
map = {}
for num in input :
newMap = {num:[[num]]}
for key in map :
newListOfLists = []
for list1 in map[key] :
newlist = list1[:]
newlist.append(num)
newListOfLists.append(newlist)
newMap[key+num] = newListOfLists
for key in newMap :
if key in map :
map[key].extend(newMap[key])
else :
map[key] = newMap[key]
print map[0]
I can think of this only.
Complexity-Horrible.
#include<iostream>
using namespace std;
void function(int arr[], int st, int size, int data[], int start, int end)
{
if(st <= size)
{
if(start==end)
{
int sum = 0;
for(int i=0;i<end;i++)
sum += data[i];
if(!sum)
{
for(int i=0;i<end;i++)
cout<<" "<<data[i];
cout<<endl;
}
return;
}
data[start] = arr[st];
function(arr, st+1, size, data, start+1, end);
function(arr, st+1, size, data, start, end);
}
}
int main()
{
int arr[] = {1,2,3,-2,-1,4,-5,1};
int size = sizeof(arr)/sizeof(*arr);
for(int i=1;i<=size;i++)
{
int* data = new int[i];
function(arr, 0, size-1, data, 0, i);
}
system("PAUSE");
return 0;
}
Algo:-
- blackfever March 29, 2014let the array be arr
1.Create An array sum as below
sum[i]=arr[0]+arr[1]+...arr[i];
2.Now see for duplicate values in sum array.
for eg:-
the array is 1,2,3,-2,-1,4,-5,1
sum array 1,3,6, 4, 3,7,2,3
so after finding duplicate values you will see the all the elements between their indices will sum upto zero and you can print it.
It will also work for over lapping intervals