Amazon Interview Question
Country: United States
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)
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.
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.
In the code above the k is the desired sub-array sum (in the original problem it should be 1)
- IvgenyNovo February 19, 2014Not sure if it's the best solution though, maybe someone can offer a worst case linear algorithm.