Amazon Interview Question


Country: India
Interview Type: Phone Interview




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

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.

Let 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].

- Robin May 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Awesome solution :)

- Brave Heart May 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Execellent

- koustav.adorable May 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if the largest sequence starts from 0th element e.g 4,-2,-2

- Ankit Jain May 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Iv June 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Robin : will your algo work for the below input..

{10,12,-10,-13,10,-10,11};

- Tama November 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- northernlight May 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Good idea. Need some fix though.

- uuuouou May 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ok, inside the 2nd for loop sum = sum - partialsum; before next iteration.

Also breakout if length > 0, no need to continue the loop, as we have started from end of array.

- northernlight May 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

do such questions asked in phone interview ? I can't answer such questions on phone unless I have solved this problem before and memorized it for the sake of interview.

- northernlight May 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- vish1310 May 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solutions gives wrong answer based on the input your r giving.

- Tama November 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

problem can be solved using brute force (compute largest subsequence at each element). Brute force solution will be of complexity N^2 but O(1) memory. However, if we use dynamic programming, as the solution given by Robin, it will be 0(N) and 0(N) memory.

- CodeKaur May 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

problem can be solved using brute force (compute largest subsequence at each element). Brute force solution will be of complexity N^2 but O(1) memory. However, if we use dynamic programming, as the solution given by Robin, it will be 0(N) and 0(N) memory.

- CodeKaur May 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- KateM May 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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++;
		   }
	}

- Mehdi May 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Yasin Efe May 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

it is a vague question. If the interviewer was really interested in interviewing he would have asked "continuous sequence". He just want to fool around.
or
OP needs to clarify the question.

- I tink May 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Will your algo work for the below input..

{10,12,-10,-13,10,-10,11

}

- Tama November 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Mike DeCosta March 09, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More