How to prepare for software interview questions - Largest sum of non adjacent numbers

Continuing the series on How to prepare for software interview questions, with another dynamic programming coding challenge.

My previous articles:

Contiguous subset of sum K

Simulate a queue with two stacks.

Number of ways to decode a message.

On the list today is the following:

Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.

For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we pick 5 and 5.

Follow-up: Can you do this in O(N) time and constant space?

Some say this problem was asked by Airbnb, who knows?

Dynamic Programming

Well I already leaked a hint by saying this is a dynamic programming coding challenge, so yeah.

Sorin likes to think about the dynamic programming questions as recursions with memoziation. If you’re not familiar with them, please read my previous article.

Now this problem doesn’t instantly scream DYNAMIC PROGRAMMING unless you really have a lot of experience dealing with these problems and you noticed the patterns.

Recursion

So let’s see how we can come up with some sort of recursion to solve this problem. In recursion, we usually have two things we need to think about:

1. The base case
2. The recursive formula

The base case

Well the base case for this problem is pretty straight forward because it consist of the array of only one element (or none) in which case the solution is simply that element (or 0 if empty array). In a one-element (or zero) array you don’t have any adjacent numbers, so yeah, not much work for your brain here.

The recursive formula

The recursive formula is usually the tricky part in any dynamic programming (dp) task. The idea is usually to, brace yourself, assume you are able to compute the solution for a smaller problem and then post-process that to compute the solution for the bigger problem.

In this case, let’s suppose we have an array with N values, arr, and let’s assume we are able to compute the solution for the array with the first 1, 2, …, N - 2, N - 1 elements. How can we compute the solution for the big array? Well we can either use the last element, arr[N], or not use it. If we decide to use it, we can only use the first 1...N-2 elements, because the element arr[N - 1] is adjacent to arr[N]. Also let’s keep in mind that we want to take the maximum sum, so if our current number is negative, we might also not want to use it, in which case we can (potentially) use the element on the position arr[N - 1].

With this idea in mind, let’s derive the formula.

max_non_adjacent_sum(arr, N):
  - 0 if N is 0

  - arr[0] if N is 1

  - max(
      # Case 1: Only take the last element if all the other ones are negative

      arr[N],

      # Case 2: Take the last element and combine that with the solution for
      # the sub-array with the first N - 2 elements

      arr[N] + max_non_adjacent_sum(arr[:-2]),

      # Case 3: Take the optimal solution of the array with the first N - 1
      # elements, and don't use the arr[N] element at all

      max_non_adjacent_sum(arr[:-1])
   )

So you case see we have 3 cases, and we take the one that’s the highest one, hence the max of 3 values.

Questions for corner cases

When you think about this solution out load, there are some corner cases that stand out and your interviewer will be really happy if you ask them. For example, can you not use any element at all? But why would you ever want to do that? Well, what if the array consists only of strictly negative elements? For example, for [-1, -2, -3] you might choose to not pick any element and have the sum 0.

Based on his answer, you will update the base case, for N = 1, you will take max(0, arr[0]).

Another good question would be what happens for an empty array? Return 0, raise an error? All of these are great questions and your interviewer will give you extra points for asking them 😉.

Moving on, I will consider we can not take any element, and hence can return 0 for empty array, and not use any element if all of them all negative.

Code

memo = {}
def max_non_adjacent_sum(arr):
  N = len(arr)
  if N == 0:
    return 0
  if N == 1:
    return max(0, arr[0])

  if N in memo:
    return memo[N]

  memo[N] = max(
    arr[-1],
    arr[-1] + max_non_adjacent_sum(arr[:-2]),
    max_non_adjacent_sum(arr[:-1])
  )

  return memo[N]

assert(max_non_adjacent_sum([2, 4, 6, 2, 5]) == 13)

Follow-up

Now, if you came so far, you’ll almost an Airbnb employee. Or maybe not.

Let’s try to also solve the follow-up question: Follow-up: Can you do this in O(N) time and constant space?.

Now if you want to be an Airbnb employee you really really need to know the fact that our memo dictionary consumes O(N) memory and also that our recursion is consuming memory for the recursion stack, O(N) as well.

Let’s first try to fix the stack recursion issue, by using an iterative solution:

def max_non_adjacent_sum(arr):
  memo = {}
  memo[-2] = 0
  memo[-1] = 0

  N = len(arr)
  for i in range(N):
    memo[i] = max(
      arr[i],
      arr[i] + memo[i - 2],
      memo[i - 1],
    )

  return memo[N - 1]

assert(max_non_adjacent_sum([2, 4, 6, 2, 5]) == 13)

With this solution, there a small thing to notice right there. In our recursive formula we only need the last two elements from our memo dictionary. So the trick is to only store those two values, in two variables, and using constant additional memory O(1). Pretty cool, huh.

def max_non_adjacent_sum(arr):
  last = 0
  before_last = 0     # Hard problem: naming your variables

  N = len(arr)
  for i in range(N):
    # Compute the new 'last'
    new_last = max(
      arr[i],
      arr[i] + before_last,
      last
    )

    # Update the before_last and last variables moving forward
    # Remember, before_plays the role of memo[N - 2], last memo[N - 1],
    # and new_last of memo[N].
    before_last = last
    last = new_last

  return last

assert(max_non_adjacent_sum([2, 4, 6, 2, 5]) == 13)

Hurray, we have a working solution with O(1) memory, so now you’re ready to become an employee at this UnIcOrN. I heard Airbnb requires all their employees to become Hosts, so clean you’re room before your interview, they might also ask that!

Testing

Coding without writing tests is like having unprotected sex. I don’t think I need to explain more.

Let’s see a couple of cool examples.

That’s it for today, later!

Cosmin

Cosmin-Ionuț Rusu

A simple action-taker who likes to just do stuff

Tweet Share