## Amazon Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
1
of 3 vote

Are you sure that example is correct? 5-3-1+2-3 = 0, not 1.

Anyway, one possible solution is to maintain a HashSet of partial sums. Partial sum is defined as follows:
partial_sum[0] = 0
partial_sum[i] = input[0] + input[1] + ... + input[i-1]

Notice that in order to find a sub-array whose elements sum to a given number k, it would suffice to find 0<=i<j<=input.length such that:
k = partial_sum[j] - partial_sum[i] = input[i] + input[i+1] + ... + input[j-1]

This is equivalent to finding an index i<j given some j which satisfies:
partial_sum[i] = partial_sum[j] - k

Using this observation, iterate over the input array and maintain the following:
1. Current partial sum (partial_sum[i+1]) where i is the current index
2. A HashSet of the previous partial sums: hashset = {partial_sum[0], partial_sum[1],...,partial_sum[i]}. At the end of each iteration we add the current partial sum to the hashset.

During each iteration, check whether the hashset contains partial_sum[j+1]-k. If it does then all that's left is to find an appropriate index i such that:
partial_sum[i] = partial_sum[j+1] - k
and return the sub-array from i to j.

Notice the found i will satisfy i<=j because of (2) above.

Complexity: O(n) average run-time complexity with O(n) space complexity.

``````private static int getIndexForSum(int[] arr, int sum){
if (arr==null){
throw new NullPointerException("arr cannot be null");
}

int i=0;
int curSum=0;
for (;(curSum!=sum) && (i<arr.length);i++){curSum+=arr[i];}

return i;
}

public static int[] findSubSet(int[] arr, int k){
if (arr==null){
throw new NullPointerException("arr cannot be null");
}

Set<Integer> sumsSet = new HashSet<Integer>();
int sum = 0;
int start = -1;
int end = -1;
for (int i=0;i<arr.length;i++){
sum+=arr[i];
if (sumsSet.contains(sum-k)){
start = getIndexForSum(arr,sum-k);
end = i;
break;
}
}

return (end!=-1) ? Arrays.copyOfRange(arr, start, end+1) : null;

}``````

In the code above the k is the desired sub-array sum (in the original problem it should be 1)

Not sure if it's the best solution though, maybe someone can offer a worst case linear algorithm.

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

Typical DP problem, by the way, do you need the longest sequence, or anyone is fine. If no longest constraint, the python code below could solve the problem:

``````def sum_equal_k(A,k):
results=[]
for i,v in enumerate(A):
for idx in range(len(results)):
results[idx][1]+=v
results.append([i,v])
for r in results:
if r[1]==k:
print(r,i)

sum_equal_k([4,3,5,-3,-1,2,-3,10,2],1)``````

Comment hidden because of low score. Click to expand.
0

It's an O(n^2) algorithm, anyone can find a better one?

Comment hidden because of low score. Click to expand.
0

We may try the following idea:

``````create an array of pairs (S_i, i) where
S_i = A[1] + a[2] + ... + A[i],

Sort the array of pairs so that the first element increase. In the sorted array find
(S_i, i) and (S_j, j) so that S_i = S_j -1 and j < j``````

Average cost should be the same as the sorting and searching algorithms.

Comment hidden because of low score. Click to expand.
0

@samuel Effectively you would be examining all the contiguous subsets. sum of a subset is derived from the sum of the immediate smaller subset which is where you save cost. Is that correct? (pardon, i could not understand your code)

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

stackoverflow.com<slash>questions<slash>5534063<slash>zero-sum-subarray

you could subtract 1 from all elements and search for the largest zero subarray :)

I guess it should be O(n), but i haven't coded it yet

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.

### 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.

### 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.

### 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.