The Technical Interview Guide to Dynamic Programming

A JavaScript guide to dynamic programming for interview prep and daily coding

After discussing how to prepare string manipulation interview questions, we are going to focus on another hot topic: dynamic programming.

Dynamic programming is a method to solve a larger problem by building up a solution to solving smaller subproblems.

An iterative implementation, eager and pre-caching, is usually preferred because it takes less time and memory. However, dynamic programming with iteration is harder to think through.

An iterative implementation is also called tabulation. The process is similar to a table-filling experience. It is a bottom-up approach, as the smaller subproblems are solved first, and then build up the whole solution. This makes it easier to trace the debug process.

Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. But a recursion can be inefficient in performance and space usage. Dynamic programming improves performance and space usage with memoization.

Dynamic programming with memoization is a top-down approach, assuming the smaller subproblems have been solved, and the whole solution is derived from these sub-solutions. All recursive algorithms can be implemented iteratively, although it is not intuitive sometimes.

We provide JavaScript examples in this article. Nevertheless, the principle and algorithms can be applied to other languages as well.

This interview series will prepare you for a successful technical interview, and it is also useful for daily coding.

Array

For dynamic programming, Array is an essential data structure for memoization, along with Map and Set.

Array is a list-like object, which has methods to perform traversal and mutation operations. In JavaScript, Array length and element types can be reset. It is interchangeably used as an object. The following are code samples for review, including includes in ES2016, flat flatMap in ES2019, at in ES2022, and findLast findLastIndex toReversed toSorted toSpliced with in 2023.

Dynamic Programming

There are many dynamic programming related tests. It is not possible to practice all of them. We go over a number of tests to emphasize problem-solving skills.

For each test, we give two dynamic programming solutions, one for iterative implementation and one for recursive implementation.

We try to standardize the solution through the following steps:

Name the memoization array as dp.
Name the recursion name as findResult.
Put the recursion inside the function to take the advantage of closure.

Closure is the combination of a function bundled together (enclosed) with references to its surrounding state. In other words, a closure gives us access to an outer function’s scope from an inner function. In JavaScript, closures are created every time a function is created, at function creation time.

Fibonacci Number

Fibonacci number is a classic dynamic programming problem. Fibonacci sequence is a series of numbers where a number is the addition of the last two numbers, starting with 0 and 1. Each number in the Fibonacci sequence is called a Fibonacci number.

For an algorithm to come up the nth Fibonacci number, the equation is:

fibonacci(n) = fibonacci(n - 1) + fibonacci(n — 2)

This is the iterative algorithm to calculate the nth Fibonacci number:

This is the recursive algorithm to calculate the nth Fibonacci number:

Both algorithms’ time complexity is O(n), and space complexity is O(n).

These are verifying tests:

Minimal Path

A minimal path is finding a path from the top left corner to the bottom right corner in a matrix by going right or going down, where the path should have the minimal sum assuming each point in the matrix is assigned a value. For Example, [[1,2], [3,4]] has a minimal path from 1 → 2 → 4, which has the sum of 7.

We initialize a two-dimensional array for memoization, where dp[i][j] stands for the minimal path sum from point[0][0] to point[i][j]. The minimal path is accumulated either from the left point(dp[i][j — 1]), or from the above point (dp[i — 1][j]):

dp[i][j] = Math.min(dp[i][j — 1], dp[i — 1][j]) + matrix[i][j].

This is the iterative algorithm to calculate the minimal path sum:

This is the recursive algorithm to calculate the minimal path sum:

Both algorithms’ time complexity is O(n²), and space complexity is O(n²).

These are verifying tests:

Longest Increasing Subsequence

A Longest Increasing Subsequence (LIS) is to find the longest subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. For example, [1, 3, 2, 2, 4] has the longest increasing subsequence, [1, 2, 2, 4], which has a length of four.

Given an array of numbers, nums, we initialize an array for memoization, where dp[i] stands for the longest increasing subsequence inside nums.slice(0, i + 1). Each element in nums is a single-length LIS. If a subsequent element is equal or larger, the current element can extend the length by one. Pick this new value, if it is larger. The breakdown algorithm is like this:

dp[i] = Math.max(dp[j] + 1), for every 0 ≤ j < i and nums[j] < nums[i]

The longest dp[i] among all choices will be picked, as the result is not necessary the last element’s dp[nums.length — 1].

This is not the fastest algorithm, but it is easy to understand. If you look for an O(n⋅log n) solution, please check out this Wiki page.

This is the iterative algorithm to calculate the length of LIS:

This is the recursive algorithm to calculate the length of LIS:

Both algorithms’ time complexity is O(n²), and space complexity is O(n).

These are verifying tests:

Change-Making

A change-making problem addresses the question of finding the minimal coin count that adds up to a given amount of money. Given the coin choices of [1, 5], the minimal coin count to make 100 is 20, i.e. 5 x 20 = 100. If there is no solution, the coin count is -1.

Given an array of numbers, coins, we initialize an array for memoization, where dp[i] stands for the minimal coin count to make the amount i. The equation is:

dp[i] = Math.min(dp[i — coins[j]] + 1), for every 0 ≤ j < coins.length and i — coins[j] >= 0 and dp[i — coins[j]] !== -1

This is the iterative algorithm to calculate the coin count for a target amount:

This is the recursive algorithm to calculate the coin count for a target amount:

Both algorithms’ time complexity is O(n⋅m), and space complexity is O(n).

These are verifying tests:

Longest Common Subsequence & Shortest Common Supersequence

A Longest Common Subsequence (LCS) is used to find the longest subsequence common to two sequences. A subsequence does not need to be consecutive within the original sequence. For simplification, we assume that the string only includes lower case letters. Given two strings, “apple” and “peach”, the longest common subsequence is “pe”, which has a length of two.

A Shortest Common Supersequence (SCS) is a common supersequence of minimal length of two given sequences. For the same examples, “apple” and “peach”, the shorted common supersequence is “appleach”, which has a length of eight.

Do you notice anything? The total length of “apple” and “peach” is ten, minus the length of the duplicated longest common subsequence, “pe”, the remaining value is eight. Therefore, the lengths of LCS and SCS can be calculated together.

Given two strings, str1 and str2, we initialize a two-dimensional array for memoization, dp[i][j] stands for the longest common subsequence of str1.slice(0, i) and str2.slice(0, j). The algorithm can be described as follows:

If (str1[i — 1] === str2[j — 1]), then dp[i][j] = dp[i — 1][j — 1] + 1.
Otherwise, dp[i][j] = Math.max(dp[i][j — 1], dp[i — 1][j]).

This is the iterative algorithm to calculate the lengths of LCS and SCS:

This is the recursive algorithm to calculate the lengths of LCS and SCS:

Both algorithms’ time complexity is O(n⋅m), and space complexity is O(n⋅m).

These are verifying tests:

Regular Expression Matching

A regular expression is a sequence of characters that defines a search pattern. The pattern is used to execute “find” or “find and replace” operations on strings. Here we simplify the pattern to be one of the following cases:

. matches any single character.
* matches the preceding character 0 or more times.
Otherwise, a character matches itself.

For example, “a” matches patterns “a”, “.”, “a*”, “a*b*”, and “a*b*c*”. But “a” dose not match patterns “b”, “b*”, “*a*b*”, and “a*b*c*d”.

This is the iterative algorithm to check regular expression match:

This is the recursive algorithm to check regular expression match:

Both algorithms’ time complexity is O(n⋅m), and space complexity is O(n⋅m).

These are verifying tests:

Conclusion

There are many variations of dynamic programming problems. Practice makes perfect.

The following are other interview guides:

Thanks for reading.

Want to Connect?

If you are interested, check out my directory of web development articles.