Disclosure: This post includes affiliate links; I may receive compensation if you purchase products or services from the different links provided in this article.
image_credit - [Grokking Dynamic Programming Patterns by educative.io
Hello guys, if you are preparing for tech interviews to get a job in big tech companies like Amazon, Google, and Microsoft then you must pay attention to two important topic, Dynamic Programming and System Design. These are two topics which often is the reason between success and try again.
Dynamic Programming is one of the toughest concepts to master for programmers but at the same time, it's quite important to crack any programming job interviews.
Nowadays, you will find at least one Dynamic programming coding problem on every coding interview and that's where most of the programmers get stuck.
They try to solve the problem using techniques like divided and conquer but ultimately fail because it's difficult to come to a solution to such problems unless you have solved a decent number of dynamic programming-based coding questions.
This is very similar to system design questions which look easy but when you try to solve them you will often find yourself stuck and that's why I suggest you practice as much as possible.
For beginners, earlier, I have shared best Dynamic programming courses to learn dynamic programming basics and in order to help you with the practice, today, I am going to share some of the frequently asked Dynamic Programming problems from coding interviews.
You can use these DP problems to not only learn how to identify dynamic programming-based coding problems but also how to approach and solve them in a given amount of time.
I have not posted the solution of these dynamic programming coding problems here because that would make this article really long, it takes a lot of space to solve and explain the dynamic programming questions but don't worry, I have linked to the appropriate solutions wherever I found. I have also shared useful resources like online courses and tutorials to learn Dynamic programming and refresh your knowledge.
If there is a demand, I may be able to post my solutions to these problems in separate articles as well but that's doesn't stop you from practicing.
You should start your practice now and try to solve as many Dynamic programming problems as possible for your coding interviews.
If you have any dynamic programming question which should be in this list, feel free to suggest and I will add. I like to keep this list updated so that we have a good number of Dynamic programming questions for practice, with all difficulty levels like easy, medium, and hard.
By the way, if you are a complete beginner to Dynamic programming then I suggest you first go through a DP course like Master the art of Dynamic Programming on Udemy to try a couple of guided problems to understand how things works, otherwise you will stuck and don't enjoy solving these questions, particularly if you have never solved a dynamic programming questions.
11 Dynamic Programming Problems for Coding interviews
Without wasting any more of your time, here is a list of the most popular and frequently asked Dynamic programming-based coding problems from interviews.
They are not only great to practice this difficult technique but also gives you an opportunity to test your DP problem-solving skills.
If you can solve 5 out of these 11 questions without any help, you are in a good place to attempt coding interviews.
1. The Climbing Stairs problem
This is one of the most popular coding problems which can be solved using the Dynamic Programming technique. In this problem, you are climbing a staircase.
It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. The question is, in how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Example 1:
Input: 2\
Output: 2\
Explanation: There are two ways to climb to the top.\
1. 1 step + 1 step\
2. 2 steps
Example 2:
Input: 3\
Output: 3\
Explanation: There are three ways to climb to the top.\
1. 1 step + 1 step + 1 step\
2. 1 step + 2 steps\
3. 2 steps + 1 step.
2. The Knapsack problem
This is another common Dynamic programming-based coding problem and a pattern which can solve many such questions. In this type of problem, you will be given the weights and profits of 'N' items, put these items in a knapsack which has a capacity 'C'.
Your goal: get the maximum profit from the items in the knapsack. Each item can only be selected once.
A common example of this optimization problem involves which fruits in the knapsack you'd include getting maximum profit. Here's the weight and profit of each fruit:
Items: { Apple, Orange, Banana, Melon }\
Weight: { 2, 3, 1, 4 }\
Profit: { 4, 5, 3, 7 }\
Knapsack capacity: 5
Let's try to put different combinations of fruits in the knapsack, such that their total weight is not more than 5.
Apple + Orange (total weight 5) => 9 profit\
Apple + Banana (total weight 3) => 7 profit\
Orange + Banana (total weight 4) => 8 profit\
Banana + Melon (total weight 5) => 10 profit
This shows that Banana + Melon is the best combination, as it gives us the maximum profit and the total weight does not exceed the capacity. You can also see this free lesson from the Dynamic Programming course on Educative for a detailed solution to this problem.
3. Edit Distance Problem
This is one of the easier dynamic programming problems. In this question, you will be given two words word1 and word2, to find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character\ Example 1:\ Input: word1 = "horse", word2 = "ros"\ Output: 3\ Explanation:\ horse -> rorse (replace 'h' with 'r')\ rorse -> rose (remove 'r')\ rose -> ros (remove 'e')
4. Longest palindromic subsequence Problem
This is another common Dynamic programming question and pattern. In this type of DP question, you will be given a sequence, find the length of its Longest Palindromic Subsequence (or LPS). In a palindromic subsequence, elements read the same backward and forward.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example 1:\
Input:\
"bbbab"\
Output:\
4\
Explanation: LPS is "bbbb".
5. Best Time to Buy and Sell Stock Problem
This is one of the hard Dynamic programming problems which need some experience to solve. In this question, you will be given an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:\
Input: [7,1,5,3,6,4]\
Output: 5\
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.\
Not 7-1 = 6, as the selling price needs to be larger than buying price.
You can try this problem on your own but if you stuck you can also see the solution here on Educative.
6. The Nth Fibonacci problem
This is one of the easiest dynamic programming questions and many of you have already solved it without even knowing that you are using Dynamic programming.
This is also the most common example of Dynamic Programming and many instructors use Fibonacci numbers to teach Dynamic programming. In this question, you will be asked to write a function to calculate the nth Fibonacci number.
Fibonacci numbers are a series of numbers in which each number is the sum of the two preceding numbers. The first few Fibonacci numbers are 0, 1, 2, 3, 5, 8, and so on.
We can define the Fibonacci numbers as:
Fib(n) = Fib(n-1) + Fib(n-2) for n > 1
Given that: Fib(0) = 0, and Fib(1) = 1
You can also see my solution of how to calculate the Nth Fibonacci number in Java to learn more about how to solve this problem.
7. The Coin Change Problem
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 of any combination of the coins, return -1.
Example 1:\
Input: coins = [1, 2, 5], amount = 11\
Output: 3\
Explanation: 11 = 5 + 5 + 1
8. Longest common substring
Given two strings 1' and 's2', find the length of the longest substring common in both the strings.
Example 1:
Input: s1 = "abdca"\
s2 = "cbda"
Output: 2
Explanation: The longest common substring is "bd".
9. Longest common subsequence Problem
Given two strings 1' and 's2', find the length of the longest subsequence which is common in both the strings.
Example 1:\
Input: s1 = "abdca"\
s2 = "cbda"
Output: 3\
Explanation: The longest substring is "bda".
10. Equal Subset Sum Partition Problem
This is another popular Dynamic Programming question that is very similar to the Knapsack problem. If you know how to solve knapsack then you can solve this too.
In his problem you are given a set of positive numbers, find if we can partition it into two subsets such that the sum of elements in both the subsets is equal.
Example 1:
Input: {1, 2, 3, 4}
Output: True
Explanation: The given set can be partitioned into two subsets with equal sum: {1, 4} & {2, 3}
Example 2:
Input: {1, 1, 3, 4, 7}
Output: True
Explanation: The given set can be partitioned into two subsets with equal sum: {1, 3, 4} & {1, 7}
Example 3:
Input: {2, 3, 4, 6}
Output: False
Explanation: The given set cannot be partitioned into two subsets with an equal sum.
You can try solving the problem on your own but if you stuck then you can also see the solution here on Educative.
This free lesson is part of their Dynamic Programming course which explains this problem in detail and also shows you how to solve it in your browser.
11. Continuous Subarray Sum Problem
This is another popular dynamic programming-based coding problem from interviews. In this problem, you will be given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k, that is, sums up to n*k where n is also an integer.
Example 1:\
Input: [23, 2, 4, 6, 7], k=6\
Output: True\
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
7 Steps for Solving Dynamic Programming Problems
So far, we have looked at common Dynamic programming problems which has been asked on interviews, now its time to learn tips and tricks to solve them.
The key to solving Dynamic programming problems is first identifying them. It's very similar to recursive problems like those binary tree problems and linked list-based problems we have solved before.
You should first see if the whole problem can be broken down into smaller problems.
For example in the climbing stairs problem, you can break down the n step problem into 1 step or 2 step problems.
Once you can do that, you see if the complete solution can be obtained by combining the solution of subproblems, that's the key. If this holds true then its most likely Dynamic programming problems and you can use the divide and conquer, Recursion, and Memoization to solve the problems.
Here are the 7 steps of solving dynamic programming (DP) problems
- Recognize a DP problem by breaking it down into subproblems
- Identify problem variables.
- Clearly express the recurrence relation to applying recursion.
- Identify the base cases.
- Decide if you want to implement it iteratively or recursively.
- Add memoization.
- Determine time complexity.
You can also use the FAST method to solve dynamic programming problems which is an acronym for the 4 steps you need to solve any dynamic programming problem:
- Find the First Solution
- Analyze the First Solution
- Identify the Subproblems
- Turn around the solution
You can use these techniques to identify and solve the Dynamic Programming problem. I also highly recommend the Master the art of Dynamic Programming course on Udemy to try a couple of guided problems to understand how these steps fit together, particularly if you have never solved a Dynamic Programming problem.
If you need a book, I highly recommend Grokking Algorithms book by Aditya Bhargava which also explains Knapsack's problem in good detail and teaches you how to solve Dynamic programming problems.
That's all about 11 common Dynamic Programming problems for tech Interviews. Btw, this is just a small sample of the dynamic programming concepts and problems you may encounter in a coding interview.
Solving these coding problems will give you enough idea about how to identify Dynamic programming problems during coding interviews as well as how to solve them in a limited time.
These questions also cover all essential Dynamic programming patterns like the Knapsack problem which can be used to solve a host of DP problems.
Other Useful Resources for Programming Job Interviews:
- 10 Books to Prepare Technical Programming/Coding Job Interviews
- 10 Courses to Prepare for Programming Job Interviews
- 10 Algorithm Books Every Programmer Should Read
- Top 5 Data Structure and Algorithm Books for Java Developers
- Top 5 Free Data Structure and Algorithm Courses
- 20+ String Algorithms Interview Questions
- Review these Java Interview Questions for Programmers
- 20+ array-based Problems for interviews
- 10 Algorithms Courses Junior Developer should join
- 7 Best Courses to learn Data Structure and Algorithms
- 25 Software Design Interview Questions for Programmers
- Top 30 Object-Oriented Programming Questions
- Top 5 Courses to learn Dynamic Programming for Interviews
- 10 Best Courses to learn System Design for Interviews
Thanks for reading this article so far. If you like these Dynamic Programming problems and interview questions then please share them with your friends and colleagues. If you have any questions or feedback then please drop a note.
P. S. - If you need more practice and need more Dynamic programming problems and solutions for each pattern, check out Grokking Dynamic Programming Patterns for Coding Interviews on Educative. It's an excellent, text-based interactive course to build your Dynamic programming skills.
Top comments (0)