Dynamic programming may be the bane of most software engineers' existence. I don't think there's any topic that I've received more questions about.
And I totally get it.
Interviewers love to ask these questions because they're hard.
Interviewees really struggle because they don't have a problem solving framework for approaching DP problems.
That means that every time you try to solve a dynamic programming problem, you are starting from square one. You can't apply patterns you seen with other DP problems because they look totally different. So you're always starting over and trying to solve these difficult problems from scratch.
In this post, I want to show you a better way.
The following videos will walk you through 6 of the most common DP problems that you can expect to see in your interviews. If you learn these problems and learn how to apply the FAST Method, you will be in very good shape to tackle dynamic programming in your interviews.
Protip: If you’re still new to dynamic programming, check out our free 42 page ebook, Dynamic Programming for Interviews, first
Check out the problems:
1. Smallest Change
Given an input amount of change x, write a function to determine the minimum number of coins required to make that amount of change.
eg. (using American coins)
|
1 2 3 4 |
change(1) = 1 change(3) = 3 change(7) = 3 change(32) = 4 |
2. Longest Common Substring
Given two strings, write a function that returns the longest common substring.
eg.
longestSubstring("ABAB", "BABA") = "ABA"
3. Fibonacci Number
Given an integer n, write a function to compute the nth Fibonacci number.
eg.
fibonacci(1) = 1
fibonacci(5) = 5
fibonacci(10) = 55
4. Square Submatrix
Given a 2D array of 1s and 0s, find the largest square subarray of all 1s.
eg.
|
1 2 3 |
subarray([1, 1, 1, 0] [1, 1, 1, 1] [1, 1, 0, 0]) = 2 |
5. Matrix Product
Given a matrix, find the path from top left to bottom right with the greatest product by moving only down and right.
eg.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
[1, 2, 3] [4, 5, 6] [7, 8, 9] 1 -> 4 -> 7 -> 8 -> 9 2016 [-1, 2, 3] [4, 5, -6] [7, 8, 9] -1 -> 4 -> 5 -> -6 -> 9 1080 |
6. 0-1 Knapsack
Given a list of items with values and weights, as well as a max weight, find the maximum value you can generate from items where the sum of the weights is less than the max.
eg.
|
1 2 3 |
items = {(w:1, v:6), (w:2, v:10), (w:3, v:12)} maxWeight = 5 knapsack(items, maxWeight) = 22 |
Have you seen any of these problems in an interview before? Comment below and let me know!
