Hey Everyone!

Hope you’re all having a fantastic day!

We’re going to do a Tech Dive today on Dynamic Programming!

The goal is to give you a toolkit to solve any dynamic programming question you get in an interview!

The solution to yesterday’s interview question is also below! It uses a pretty important trick about matrices that you should be aware of!

On thursday, we’ll send out our tech dive on Serverless Computing. So stay tuned!

Tech Dive

Dynamic Programming is the technique of storing repeated computations in memory to save time by not recalculating them. You’re trading off memory for time.

This is a common pattern used in coding interviews, since you’ll be given a question where the brute force solution has an exponential time complexity. Using Dynamic Programming (DP), you can reduce the time complexity to a linear time solution.

Here’s a step by step process on how to master DP questions. After, we’ll go through a real DP interview question using the process.

1. Find the brute force solution - Solve the question for the input test case using the brute force way. Don’t worry about efficiency, but figure out a brute force solution that breaks the problem down into smaller subproblems and solves it recursively. Here, you have to define the subproblems that you’ll be using.

2. Figure out if you can use Dynamic Programming

   1. Check for Optimal Substructure - you can solve the problem recursively by breaking it down into smaller subproblems.

   2. Check for Overlapping Subproblems - when you split the problem into smaller subproblems, some of the subproblems are repeated.

3. Use a memo table (hash table) to cache your solutions to the subproblems. This way, if you have a repeated subproblem, you don’t have to recalculate. This is the Top-Down Dynamic Programming Solution.

4. Flip the solution around for the Bottom-Up Solution. Solve the subproblems in reverse order with a for loop instead of using recursion. In some scenarios, this can reduce your space complexity (you only have to store the solutions to specific subproblems).

5. Practice writing out the code for 5 - 10 Dynamic Programming Questions. Train yourself on being able to write a code solution once you have the subproblems. Once you figure this out, the trick is in being able to determine the subproblems.

6. Go through tons of Dynamic Programming questions and focus on figuring out the subproblems. Once you figure out the subproblems, don’t bother coding the full solution (you already practiced that in step 5). The goal is to train your pattern recognition muscle to be able to quickly find the subproblems.

   1. Educative has a curated list of ~30 Dynamic Programming questions that are an excellent guide on which problems to solve. If you go through all 30 problems and figure out subproblems, you should be good for interviews.

   2. Use the Dynamic Programming Tag on LeetCode and go through DP questions there. These aren’t curated, so you may have to go through more than 30 questions to get a good variety. Try and filter by frequency if you have LeetCode premium.

Let’s go through this process on an example question

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Input - [1,5,10,25], amount = 12

Output - 3

Here’s the question in LeetCode.

So, the first step is to find a recursive brute force solution to the question. Unfortunately, we can’t use a greedy approach since it will fail in scenarios such as [1, 15, 25], amount = 30 (the greedy approach gives you 6 instead of the real answer, which is 2).

Therefore, we must solve this question by trying all possibilities. Using our amount, we have to try all the coin denominations and see if we’re still left with a positive amount. If so, we recursively call our function on that amount. If not, then we can return the number of coins that were used and figure out the minimum used.

Here’s a REPL with the brute force solution.

Now, we check for optimal substructure and overlapping subproblems.

The optimal substructure has already been proven by our brute force solution. We can solve this problem by reducing it to subproblems of the same variant. We just reduce our amount by subtracting all our coin denominations (taking one of each coin) until our amount is less than or equal to 0.

The overlapping subproblems can be proven by drawing the recursion tree. Take our sample input of [1,5,10,25], amount = 12. You’ll notice that there are calls that are being repeated. _coinChange(5) is called multiple times for example (_coinChange is from our brute force solution in the REPL).

We can move on to Step 3. We’ve already defined the subproblems in our brute force approach, now we just have to add the memo table. The memo table is a way for us to put our solutions in cache, so that we’re not recalculating the solutions for the repeat subproblems. We can do that pretty easily with our old code.

Here’s a REPL with the Top Down DP Solution using a Memo Table.

Now, Step 4. Figure out the Bottom Up solution!

We flip the subproblems around and use a for loop instead of recursion. Going back to our input example of [1,5,10,25], amount = 12, we’ll have to figure out the fewest number of coins for every amount from 0 to 11. We’ll cache our solutions in an array. Then, we can use those solutions to calculate 12. It’s the same exact subproblems, but we’re just doing it in reverse order! Start with 0 and work our way up to 12.

Here’s a REPL with the Bottom Up DP Solution

That’s it! That’s the process.

So, practice this process on 5 - 10 problems and completely write out the code. Once you get done with those questions, you should have a solid understanding of how to go from subproblems to a completed Top Down and Bottom Up solution.

Then, the trick is being able to recognize the subproblems. That just comes with practicing your pattern matching muscle. Go through a bunch of DP problems and just try to recognize the subproblems.

Educative’s course on DP interview questions is a terrific curated list of DP questions so you should definitely be familiar with all of them. 

You can also go on LeetCode and look at all the questions with a Dynamic Programming tag. Sort the questions by Frequency and then go through them and identify the subproblems.

Previous Solution

As a reminder, here’s the previous question

Given a matrix with dimensions M x N, return all elements of the Matrix in diagonal order.

Input -

[[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ]]

Output - [1,2,4,7,5,3,6,8,9]

Here’s a link to the question in LeetCode

Solution

Here’s a really useful property to understand and memorize.

The sum of the indices on all diagonals are equal!

So, going to our matrix in the example input… 3, 5 and 7 are all on the same diagonal. 3 has indices [0, 2], 5 has indices [1, 1] and 7 has indices [2, 0]… so they all have an indice sum of 2.

The same goes for 2 and 4, they are on the same diagonal and have an indice sum of 1. The same goes for 6 and 8, which are on the same diagonal and have an indice sum of 3. 1 has an indice sum of 0 and 9 has an indice sum of 4.

Therefore, we can solve this problem by looping through the matrix, storing each element by the sum of it’s indices in a dictionary. Then, reverse every other diagonal level for the “zig zag”.

Here’s a Python 3 REPL with the solution

I didn’t want to make the email too long, so no Interview Question today! We’ll have another one tomorrow!

Best,

Arpan