This was one of the interview questions I was recently asked; I wasn't able to answer it, but hopefully this post will help others solve it on their interviews.
The question is quite simple and perhaps classic. Given an array of n numbers and target sum, find the largest sequence within the array such that the sum of the array is equal to the target sum. Design an implementation in O(n) time complexity.
Hint? Use hash map.
This is how you can solve this. Say the array is given by {a_1, a_2, a_3, ..., a_n}. Any subsequence of the array will have the form {a_i, ..., a_j} where i <= j <= n. If you let S_k be the sum from a_1 through a_k, then you notice that sum of any subsequence is given by S_j - S_i.
Thus, you need to go through each number and calculate S_j, and see if there has been S_i in the hash map such that S_j - S_i = target. If so, you can update your result.
In code, you can easily implement with Python:
There are some subtleties, but it shouldn't be too difficult to follow the code.
No comments:
Post a Comment