Amazon Interview Question
Country: India
Interview Type: Phone Interview
I did one test with the following array: -5,3,-2,-2,-1,4,6 And it seemst that i have S[0] = -5 and S[3] = -5 But the 0-sequence is A[1]...A[3]. Correct? Or i misunderstood the answer? Is possible that the 0 sequence starts from t+1?
assuming sequence mean continuous elements
int solution(int A[],int N)
{
int sum=0;
int partialsum = 0;
if((N==1) && (A[0] == 0)) return 1;
for(int i =0;i<N;i++)
sum=sum+A[i];
if(sum==0) return N;
for(int i=N-1;i >0;i--)
{
partialsum+=A[i];
if ((sum - partialsum) ==0)
{
length = i;
return length;
}
sum = sum - partialsum;
}
return length;
}
I tried to solve it in Java here is the solution. using comments from robin.
public class largestSumToZero {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
int arr[] = {10,12,-10,-13,10,-10,11};
largestSubarraySumToZero(arr);
}
private static void largestSubsequenceSumToZero(int[] arr) {
int temp[]= new int[arr.length];
for(int i=0;i<arr.length;i++)
{
temp[i]= sumArray(arr, i);
}
HashMap<Integer, Integer> checkValue = new HashMap<Integer,Integer>();
int start=0,end=0,max=0;
for(int i=0;i<temp.length;i++)
{
if(!checkValue.containsKey(temp[i]))
{
checkValue.put(temp[i],i);
}
else
{
if(max < Math.abs(i-checkValue.get(temp[i])))
{
max = Math.abs(i-checkValue.get(temp[i]));
start = checkValue.get(temp[i]);
end = i;
}
}
}
System.out.println((start+1)+" "+end);
}
private static int sumArray(int arr[],int index)
{
int sum = 0;
for(int i=0;i<=index;i++)
{
sum+=arr[i];
}
return sum;
}
}
public static int findLargeSeqSumZero(int[] arr) {
int[] sumArr = new int[arr.length];
int sumSoFar = 0;
for (int i=0; i<arr.length; i++) {
sumSoFar += arr[i];
sumArr[i] = sumSoFar;
}
//Find 2 identical integers in sumArr furtherest apart
HashMap<Integer, Integer> checkValue = new HashMap<Integer, Integer>();
int start = 0;
int end = 0;
int max = 0;
for (int i=0; i<arr.length; i++) {
if (!checkValue.containsKey(sumArr[i])) {
checkValue.put(sumArr[i], i);
} else {
start = checkValue.get(sumArr[i]);
end = i;
//We plus 1 because an array starts at 0
max = Math.max(max, ((end - start)+1));
}
}
return max;
}
This is a solution that does not require any N related extra space and is of the order of O(N). beginIndex and endIndex shows the longest sequence.
void find_opt(int[] ar){
int beginIndex=0;
int endIndex=0;
int i=0;
int j=0;
int sum=0;
while(j<ar.length){
sum+=ar[j];
if(sum==0 && j-i > endIndex-beginIndex) {
sum=-1*ar[beginIndex];
beginIndex=i;
endIndex=j;
i++;
}
j++;
}
}
This is the recursive solution. It returns size of the largest set.
1. Calculate sum of the array.
2. If the total is zero, return j - i means sub set size. i and j can be returned to have sub set of array.
3. Call same method recursively (2. step) with subset of [i] to [j -1] and [i + 1] to [j], return max size of sub set
public class LargestSetTotalZero {
public int findLargestSet(int[] values) {
int total = 0;
for (int i : values) {
total += i;
}
return findLargestSetSize(values, total, 0, values.length - 1);
}
private int findLargestSetSize(int[] values, int total, int i, int j) {
if (total == 0) {
return j - i;
}
int firstSet = 0;
int secondSet = 0;
if (i < j - 1) {
firstSet = findLargestSetSize(values, total - values[j], i, j - 1);
secondSet = findLargestSetSize(values, total - values[i], i + 1, j);
}
return firstSet > secondSet ? firstSet : secondSet;
}
}
These are the tests
public class LargestSetTotalZeroTest {
private LargestSetTotalZero largest;
@Before
public void setup() {
largest = new LargestSetTotalZero();
}
@Test
public void test() {
assertEquals(0, largest.findLargestSet(new int[] { 1 }));
assertEquals(1, largest.findLargestSet(new int[] { 1, -1 }));
assertEquals(1, largest.findLargestSet(new int[] { -1, 2, 1, -1 }));
assertEquals(3, largest.findLargestSet(new int[] { -1, 2, 1, -2, -1 }));
assertEquals(5, largest.findLargestSet(new int[] { 3, 5, -2, 6, -8, 1, -2, 4, 2 }));
assertEquals(6, largest.findLargestSet(new int[] { 3, 5, -2, 6, -8, 1, -1, -1, 2 }));
}
}
Here is a solution help from Roby for the core insight of keeping track of current sum. Done in 1 pass.
public int largestSubsequence(int[] array) {
// store <sumUpToI, i> key value pairs to determine if we have a 0 sum sequence
HashMap<Integer, Integer> iValueWithSum = new HashMap<>(array.length);
// our sum is 0 before we start, this is to catch sequences that start at i=0
iValueWithSum.put(0, -1);
int currentMaxSequenceLength = 0;
int currentSum = 0;
for(int i=0;i<array.length;i++) {
currentSum += array[i];
if(iValueWithSum.containsKey(currentSum)) {
int startIndexForZeroSum = iValueWithSum.get(currentSum) + 1;
int currentSequenceLength = (i - startIndexForZeroSum) + 1;
currentMaxSequenceLength = Math.max(currentMaxSequenceLength, currentSequenceLength);
} else {
iValueWithSum.put(currentSum, i);
}
}
return currentMaxSequenceLength;
}
The statement of the question is vague. Do you mean a continuous sequence or a subset of the sequence which sums to zero ? The subset problem is NP-hard but the continuous sequence problem can be done as follows.
- Robin May 10, 2014Let A be the input array of integers with length n. Proceed as follows. Declare a new array S of the same length where S[i] = \sum_{j=0}^{i} A[j] i.e., the i'th entry of S contains the sum of the entries in A upto and including index i. Now, if A[t] ... A[t+k] is a zero sum subsequence then S[t] = S[t+k]. So, the problem reduces to finding two farthest entries in S which have the same integer entries. This can be done easily using a hash map. Go through the entries of S, hash S[i] and store i if S[i] was not seen before. Note that when you see that S[i] was seen, you can compute the length of the current zero sum sequence as i - index which is stored at S[i].