# Home » My second favorite interview question

Recently I wrote a blog post analyzing my favorite interview question. Here's my second favorite:

Given an array of integers and an integer `k`, find the maximum sum that can be made with `k` contiguous numbers.

Another way of saying this is: "what is the maximum sum of all possible subsequences of size `k`?"

This is just a warmup question. Interviews are stressful and unnatural, so I like putting candidates at ease by starting with a question that they probably will know the answer. All candidates are able to come up with a brute force solution to this question, and half of the candidates will start with the optimal solution.

# Initial solution

The brute force solution iterates over the sum of all possible subsequences:

``````def find_max_sum(numbers: List[int], k: int) -> int:
max_sum = -float("inf")

for i in range(len(numbers) - k):
candidate = 0
for j in range(k):
candidate += numbers[i + j]

max_sum = max(max_sum, candidate)

return max_sum
``````

Notice that we're not doing any kind of error checking here — for example, verifying that `k` is less than the size of the array. Good candidates will talk about error checking, and discuss what would be the return type. I usually don't ask them to code the error handling, being satisfied with them just mentioning it.

The time complexity of the solution is `O(nk)`, and the space complexity is constant. Usually weak candidates will initialize `max_sum` to zero, and in that case I ask what would be the solution if all numbers in `numbers` were negative.

# A better solution

Since this is a warmup question, I usally try to discuss the question with the candidate until they've come up with a moving window solution. Only then I ask them to translate the solution to code. It usually looks something like this:

``````def find_max_sum(numbers: List[int], k: int) -> int:
max_sum = 0
for i in range(k):
max_sum += numbers[i]

candidate = max_sum

for i in range(k, len(numbers)):
candidate += numbers[i]
candidate -= numbers[i - k])
max_sum = max(max_sum, candidate)

return max_sum
``````

This solution is linear in time (as fast as possible), and also uses constant space. It works by computing the sum of a window of size `k`, and then moving that window one step at a time, by summing the new value and subtracting the one that is no longer part of the window. For example, for a `k` equals to 3:

``````[1  2  3] 4  5  6  =>  1 + 2 + 3 = 6
1 [2  3  4] 5  6  =>  6 + 4 - 1 = 9
-        +
2 [3  4  5] 6  =>  9 + 5 - 2 = 12
-        +
``````

# The main question

Once the candidate has answered the warmup question, I move to the main question:

Given an array of integers and an integer `k`, find the maximum sum that can be made with 3 non-overlapping windows of size `k`.

Good candidates quickly realize that this is a much harder question. They will try to reuse their initial solution to the warmup question, coming up with a greed solution. I usually give them this example, which does not work with a greedy solution:

``````1  4  6  2  1  1  4  7  8  5  1
``````

For the input above and `k` equals to 2 the answer should be:

``````1 [4  6] 2  1  1 [4  7][8  5] 1  =>  4 + 6 + 4 + 7 + 8 + 5 = 34
``````

But a greedy solution would first find `[7 8]`, then `[4 6]`, and finally `[5 1]`, giving as an answer 31.

Some candidates will assume that this is a dynamic programming question. It can be solved with dynamic programming, but I would always tell candidates thay they were free to use dynamic programming, but it was not necessary. In general I tend to find dynamic programming solutions too opaque, and I have a hard time getting good signal from candidates when they use it.

# Brute force solution

Most candidates realize that the brute force solution has a cubic time complexity. If they can't come up with a better solution I ask them to code the brute force solution, mentioning that we can always try to improve it later. Candidates usually write an iterative solution similar to this:

``````def find_max_sum_3(numbers: List[int], k: int) -> int:
max_sum = -float("inf")
n = len(numbers)
for i in range(n - 3 * k):
for j in range(i + k, n - 2 * k):
for l in range(j + 2 * k, n - k):
candidate = sum(numbers[i:i+k]) + sum(numbers[j:j+k]) + sum(numbers[l:l+k])
max_sum = max(max_sum, candidate)

return max_sum
``````

The time complexity is now `O(n^3 k)`. A cleaner and more efficient solution uses two pointers to split the array into 3 subsequences:

``````def find_max_sum_3(numbers: List[int], k: int) -> int:
max_sum = -float("inf")
n = len(numbers)
for i in range(n - 2 * k):
for j in range(i + k, n - k):
candidate = (
find_max_sum(numbers[:i]) +
find_max_sum(numbers[i:j]) +
find_max_sum(numbers[j:])
)
max_sum = max(max_sum, candidate)

return max_sum
``````

I like this solution because it reuses the solution from the warmup question. The time complexity is now `O(n^3)`, which is a small improvement. Space complexity can be improved, since slicing Python lists creates new lists, instead of views. We can modify the original solution to take indexes:

``````def find_max_sum(numbers: List[int], k: int, start: int, end: int) -> int:
max_sum = 0
for i in range(start, start + k):
max_sum += numbers[i]

candidate = max_sum

for i in range(start + k, end):
candidate += numbers[i]
candidate -= numbers[i - k])
max_sum = max(max_sum, candidate)

return max_sum

def find_max_sum_3(numbers: List[int], k: int) -> int:
max_sum = -float("inf")
n = len(numbers)
for i in range(n - 2 * k):
for j in range(i + k, n - k):
candidate = (
find_max_sum(numbers, 0, i) +
find_max_sum(numbers, i, j) +
find_max_sum(numbers, j, n)
)
max_sum = max(max_sum, candidate)

return max_sum
``````