Nail the Whiteboarding Interview with Dynamic Programming - Use Concepts You Already Know to More Simply Solve Difficult Algorithms in an Easy to Explain Way

Algorithm interviews are hard. While some companies are shifting away from them in favor of system design questions or take-homes, they remain the most common technical interview style.

As engineers, we can make the job hunt easier for ourselves by adding different tools to our problem-solving tool belt. One such tool is dynamic programming, which can be defined as a way to simplify a complicated problem by breaking it down into smaller sub-problems, solving them once, and combining their results to solve the original problem. Dynamic programming (DP) is an excellent problem-solving technique to use in interviews because it not only makes previously intimidating problems seem more accessible, but because it allows you to whiteboard your solution in a logical and systematic way that is easy for the interviewer to follow. Let’s take a look at how.

WHAT IS DYNAMIC PROGRAMMING?

As mentioned above, dynamic programming is a problem-solving strategy that breaks problems down into smaller subproblems, solves those smaller problems, saves their results, and combines them to solve the original problem.

There are two qualifications a problem must satisfy in order to be solved with DP: optimal substructure and overlapping subproblems.

Let’s see what each of these properties look like as we walk through an example.

EXAMPLE - LONGEST COMMON SUBSEQUENCE

Given two strings, return the length of the longest set of characters that appear in both strings in the same order. The characters can be consecutive or nonconsecutive. For example, the longest common subsequence of “

DABA” and “ZDBC” is “DB.”

Top-down, aka memoized recursion

The recursion tree for this approach looks like this:

In the worst case where there is no common subsequence between strings, there would be two additional recursive calls for each recursive call (remember, we are checking both the take and leave scenarios listed above). Because this solution makes one recursive call for each character in each string regardless of whether or not that subproblem’s solution has already been calculated, the worst-case time complexity would be exponential (O(2^(x+y)), where x and y are the lengths of each string argument). The space complexity would be constant (O(1)) because we aren’t creating any new data.

const lcs = (string1, string2) => {
  const lastString1Idx = string1.length - 1;
  const lastString2Idx = string2.length - 1;

  // base case: if either string's length is 0, return 0
  if (string1.length === 0 || string2.length === 0) return 0;

  // if last characters are the same
  if (string1[lastString1Idx] === string2[lastString2Idx]) {
    // return output of lcs slicing off last char of each string, + 1
    return lcs(string1.slice(0, lastString1Idx), string2.slice(0, lastString2Idx)) + 1;
  }

  // if last characters are different
  // return max of lcs chopping off last char from string1 or string2
  return Math.max(
    lcs(string1, string2.slice(0, lastString2Idx)),
    lcs(string1.slice(0, lastString1Idx), string2),
  );
};

Take a look at the recursion tree below. There are 7 subproblems being calculated more than once. This amounts to 67 recursive calls to our function, and this is with arguments that are each just four characters long!. Imagine if the strings were longer. We’d be exponentially increasing the number of subproblems as our input lengths grew.

The fact that we can break the original problem down into subproblems tells us that this problem has optimal substructure, and these overlapping subproblems (look at how many times we calculate the result for the same inputs) tell us that this is a great problem to use dynamic programming to optimize our solution.

Because we’re starting at the top, with the largest possible problem, and moving down, to the smallest possible problems, this approach is called a top-down solution. We’ll optimize our recursive solution using memoization, saving the result of each subproblem and only calculating a subproblem’s solution if it hasn’t already been calculated. In general, a solution is utilizing top-down dynamic programming if it implements the combination of memoization and recursion.

Now the recursion tree looks like this:

And the code:

const lcsTopDown = () => {
  const lengthMemo = {};

  return function getLength(string1, string2) {
    // base case: if either string's length is 0, return 0
    if (string1.length === 0 || string2.length === 0) return 0;

    if (!lengthMemo.hasOwnProperty(string1 + string2)) {
      const lastString1Idx = string1.length - 1;
      const lastString2Idx = string2.length - 1;

      // if last characters are the same
      if (string1[lastString1Idx] === string2[lastString2Idx]) {
      // return output of lcs slicing off last char of each string, + 1
        lengthMemo[string1 + string2] = getLength(
          string1.slice(0, lastString1Idx),
          string2.slice(0, lastString2Idx),
        ) + 1;
      } else {
        // if last characters are different
        // return max of getLength chopping off last char from string1 or string2
        lengthMemo[string1 + string2] = Math.max(
          getLength(string1, string2.slice(0, lastString2Idx)),
          getLength(string1.slice(0, lastString1Idx), string2),
        );
      }
    }

    return lengthMemo[string1 + string2];
  };
};

In the optimized solution, we still make two recursive calls for each previous recursive call. However, if the function has been called with those arguments before, we get the returned value from the lengthMemo object instead of continuing to recurse. As a result, in the worst case, for each character in string x, we would make only 2y recursive calls. This would result in a linear time complexity (O(2xy)). Now, because we’re creating an auxiliary object to track each unique recursive call, the space complexity increases from O(1) to O(xy) (constant to linear).

This top-down approach is both efficient and intuitive, but how would you draw out your logic and explain it in an interview? Longer inputs would make drawing out the recursion tree impossible, and you’d have to resort to a higher-level conceptual explanation before coding your solution. Bottom-up DP offers a great solution to this dilemma, and also allows you to optimize your space complexity to just O(x).

Bottom-up, aka iterative tabulation

What if we started with the simplest and smallest subproblems, calculated each one once, and added each one to the previous problem until we reached the solution to the original problem? That is exactly what bottom-up DP aims to do. Further, it gives you the opportunity to diagram your step by step tabulation of each solution as you go.

Our bottom-up solution will iterate over each string to build a two-dimensional array of values that correspond to the longest common subsequence of the characters of each string up to that point in the iteration. So how do we get there?

To fill each cell of the grid, we’ll be finding the longest common subsequence of the substrings of each string up to the current character. So, to fill the first row, we’ll compare each substring of the string along the top of the table (string x) to an empty string. Since it’s impossible to have characters in common with an empty string, the first row will have all zeroes:

The next character of string y is ‘Z,’ which no substring of string x includes, so we’ll end up with another row of zeros.

In the next row, things get interesting. The current substring of string y is now ‘ZD,’ which has a common subsequence of one with the substring of string x ‘D.’ In the cell where those two substrings intersect, we’ll add a ‘1’.

Now for every other substring of string x, the longest common subsequence with ‘ZD’ will be one. Another way to think of this is that, if the current characters don’t match, the value of the cell where they intersect is the higher value of the adjacent cell to the left and the adjacent cell above.

In the next row, the last characters of ‘ZDB’ and ‘DAB’ match. Since those substrings have both ‘D’ and ‘B’ in common, the value in the cell where they intersect will be two. To think of this purely in terms of the logic of the table, if the current characters match, then the value in the current cell will be the value of the cell one row up and one column over, plus one.

Filling out the last row, the final table will end up looking like this, and the value in bottom-most, right-most cell will be our result:

Similarly, the 2D array that our code builds will look like this:

Here's the code for this approach:

const lcsBottomUp = (string1, string2) => {
  const string1Length = string1.length;
  const string2Length = string2.length;

  const table = [];

  // add new nested array for each character in string1
  // * these are the rows of the table
  for (let i = 0; i <= string1Length; i++) {
    table.push([0]);
  }

  // in the first nested array, add a 0 for each character in string2
  for (let j = 0; j < string2Length; j++) {
    table[0].push(0);
  }

  // for each character in string1
  // find the lcs between the string1 substring up to that character
  // and every possible string2 substring
  for (let i = 1; i <= string1Length; i++) {
    for (let j = 1; j <= string2Length; j++) {
      // if the current characters are the same
      string1[i - 1] === string2[j - 1]
        // the current element becomes the value of the cell in the previous row
        // one column to the left
        // plus 1
        ? table[i][j] = table[i - 1][j - 1] + 1
        // if the current characters are different, the current element
        // becomes the higher value of the cells immediately to the left and above
        : table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
    }
  }

  // return the last element in the last nested array
  return table[string1Length][string2Length];
};

In this approach, we are iterating over each character in string x y times, and vice versa. This yields a linear time complexity of O(xy). Since we’re also creating an additional array element for each possible combination of characters between the two strings, the space complexity is also O(xy).

To optimize the space complexity of this approach, we can modify our solution to only create an array for the previous row and the current row. This would improve space complexity to O(2x), or simplified to O(x).

In addition to this optimization, imagine how much easier this would be to whiteboard out in an interview compared to the top-down approach! You can explain every single step of your code to the interviewer in a highly intuitive way before you even write a single line.

TO WRAP UP

Dynamic programming is not the end-all, be-all of solving algorithms in interviews, but it is an extremely useful problem-solving strategy to be comfortable with. It applies to a specific subset of algorithms that would otherwise be difficult to approach, explain, and execute in such a high-pressure setting as an interview.

By breaking problems down into smaller subproblems with DP, not only will you be able to quickly solve problems that would have otherwise taken much longer to understand, but you’ll also be able to solve them efficiently and explain them in a way that is easy to follow, which demonstrates a strong understanding of core computer science concepts like time and space complexity, memoization, and recursion.

Additional Resources: 

• Jonathan Paulson's Quora post
• Techie Delight - Intro to DP
• Top 50 DP Problems
• Tabulation vs Memoization