How to prepare for software interview questions - Contiguous subset of sum K
- 10 mins cosminIn this article, I want to break down a simple interview problem for you. Here it is.
Given a list of integers and a number K, return which contiguous elements of the list sum to K.
For example, if the list is [1, 2, 3, 4, 5] and K is 9, then it should return [2, 3, 4], since 2 + 3 + 4 = 9.
This is a great example of typical interview questions for a few reasons:
- It has a simple, straight forward solution
- You can think about solving it in iterative approaches, starting with the simplest one
- The statement is very simple - so you have to ask a lot of questions first to make sure you solve what you need to solve and you are on the same page as the interviews.
The way I recommend people to tackle such problems is to:
- Understand the problem
- Come up with a simple solution
- Iterate until you find a solution that the interviewer is happy with.
Now let’s see how to do all of them.
1. Understand the problem
Clearly, you can’t solve a problem without knowing everything about it. This step is also here to make sure that you and the interviewers see the same problem. Otherwise, you might think about a different solution, code it, just to find at the end that it is not what the interviewer wanted, but because of a confusion.
The best way to tackle this is to ask a LOT of questions. For example:
- ask what’s the input type, does it fit into a 32-bit integer? 64-bit integers?
- do we have an order of the number of elements in the array? 100 000 maybe? 1 000 000 000 maybe?
- can we keep the array in memory?
- etc
This not only helps you clarify the questions but also shows the interviewer that you actually care about all of these details and don’t code until you have every detail sorted out - and that is a very strong indication that you are what the interviewer is looking for.
2. Come up with the simplest solution
A simple solution is usually straight forward. Just state to your interviewer that you know the brute-force/obvious solution and clearly state it. For example, in this problem you can say something like:
Well, clearly we can implement a simple brute-force solution, iterating through all of the contiguous subarrays and computing the sum. If the sum is K, we stop and return it.
Your code might look something like this:
def sum_k(arr, K):
n = len(arr)
for i in range(n): # set the start of the sequence
for j in range(i, n): # set the end of the sequence
sum = 0 # initialize the sum
for k in range(i, j+1): # compute it for the subarray arr[i:j]
sum += arr[k]
if sum == K: # if the sum is K, return it
return arr[i:j+1]
# Raise an exception if no such subarray exists
raise RuntimeError('Not Found')
Also, you see I raised an exception if no solution was found, but open up a discussion around this. Ask your interviewer: What do you think it would make sense to return if no solution exists? Maybe raise an exception, or return an empty array []?
This also indicates you care and know different ways to solve a sub-problem.
3. Iterate to the best solution
Not, this code runs in complexity O(n^3) because we try all the possibilities and then compute the sum, but we can make it better. Ask the interviewer what do they think about the brute-force/simple solution. Most likely they’ll say “can we do better?”. The correct answer is “of course”.
Now it’s time to make some observations, based on the brute force. We iterate with k from i to j, but that’s not needed, since we already do that with the j, so we can improve the performance to O(n^2) like this:
def sum_k(arr, K):
n = len(arr)
for i in range(n): # set the start of the sequence
sum = 0 # initialize the sum of **all** the sequences that start on the position i
for j in range(i, n): # set the end of the sequence
sum += arr[j] # now sum = sum(arr[i..j])
if sum == K: # if the sum is K, return it
return arr[i:j+1]
# Raise an exception if no such subarray exists
raise RuntimeError('Not Found')
Clearly this is an improvement. If N = 1000, we now make 1 000 000 (ie 1M - which runs in less than 1s) operations instead of 1 000 000 000 (ie 1B).
Now the interviewer will say “Great, but can we do better?”. Or he might just be happy with this solution and end the interview - but that’s unlikely here.
The correct answer is always “of course”. Then you can also ask a couple of other questions like:
- Are we allowed to use extra memory?
If you’re stuck, try to think out loud with all the solutions that you are trying to find. Take the hints if they are given to you - those don’t mean a lot anyway - you have to see the interview as a collaboration, not you showing off your skills.
Now the best solution, O(n) O(n) extra memory comes from a few observations and a common trick.
Let’s define the array sum[i] = sum(arr[0:i]) ie the sum of all elements up to and including arr[i].
This can easily be computed with a recurrence formula in O(n) as: sum[i] = sum[i - 1] + a[i].
The trick now is that we can compute the sum for two indices i and j as sum[j] - sum[i - 1] if i is not 0, or sum[j] otherwise.
Okay, but we still need to fix all the i and j pairs, right? Well not really because, you see for a fixed j, we are looking for an i such that sum[j] - sum[i] == K, which translates to sum[j] == K + sum[i] where i < j. So it means that we have to keep all the values K + sum[i] somewhere and ask if an element exists. We are looking for a fast data structure where we can add elements and ask if an element exists very fast. One such data structure is a hash, or a dictionary.
So our final solution is:
We keep computing the partial sum, check if one exists with sum K, add the current partial sum to the hash and continue until the end.
Let’s see how that looks like in the code:
def sum_k(arr, K):
n = len(arr)
p_sum = 0
dict = {K: -1} # wee add the sum K with index -1 corresponding to the i = 0 case
for j in range(n): # set the end of the sequence
p_sum += arr[j] # now p_sum = sum(arr[0..j])
if p_sum in dict: # if an element with this exist in the array
i = dict[p_sum]
return arr[i+1:j+1] # Return it
else: # Add the value K + sum[i] to the hash
dict[K + p_sum] = j # ie the right hand side of the equation described above
# Raise an exception if no such subarray exists
raise RuntimeError('Not Found')
Now the interviewer will be really happy with this solution. One thing that I always do after coding such a problem is telling them: “Okay, let me quickly re-read the code once again out loud to see if I didn’t miss anything”. That’s again a very good trick to do because it will also help them understand your code since you’re talking about loud what you do on each line of code. You should read basically what I’ve put as comments, or even add the comments at the end.
The last thing that you can also do to show off your skills to your interviewer is to write some small unit tests. Remember, your code doesn’t usually need to compile, but if it does and you can write some unit tests, that would be awesome. For example, you can write a few like this:
assert(sum_k([1, 2, 3, 4], 9) == [2, 3, 4]) # Handle example
assert(sum_k([1], 1) == [1]) # Handle simple edge case
try:
sum_k([], 1) # Raises exception
except RuntimeError:
pass
else:
assert(False)
... # etc, the sky is the limit
print("All tests passed")
You can play around with the code in the following repl.it.
That would be all, let me know what you think.
PS. I have a great community of engineers that want to get into freelancing or top-tier software companies like Google, Apple, Amazon, Microsoft or Facebook. You can check it out at https://academy.dutylabs.ro. Looking forward to seeing you there.
PPS. If you want to get exclusive articles like this on your inbox fast, sign up with your email below and never miss an article like this - I plan to do a lot more in the future.
Stay healthy, safe and motivated!
Cosmin
Cosmin-Ionuț Rusu
A simple action-taker who likes to just do stuff