To ace your coding interview for a software engineering job, you’ll need to understand dynamic programming. Dynamic programming optimizes naive solutions to complex problems that have repeated recursive calls for the same inputs. This is achieved by storing solutions to simpler sub-problems to be used later so that they don’t need to be recalculated.
Let’s take a look at some typical dynamic programming questions.
6 typical dynamic programming interview questions
-
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount.
-
You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
-
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
-
Given n, calculate the Fibonacci sequence.
-
Given an m x n binary matrix filled with 0s and 1s, find the largest square containing only 1s and return its area.
- Given an input string s and a pattern p, implement regular expression matching.
Below, we take a look at 50 dynamic programming questions and provide you with links to high quality solutions to them.
This is an overview of what we’ll cover:
-
Easy dynamic programming interview questions
- Medium dynamic programming interview questions
- Hard dynamic programming interview questions
- How to prepare for a coding interview
Let's get started.
1. Easy dynamic programming interview questions
You might be tempted to try to read all of the possible questions and memorize the solutions, but this is not feasible. Interviewers will always try to find new questions, or ones that are not available online. Instead, you should use these questions to practice the fundamental concepts of dynamic programming.
As you consider each question, try to replicate the conditions you’ll encounter in your interview. Begin by writing your own solution without external resources in a fixed amount of time.
If you get stuck, go ahead and look at the solution, but then try the next one alone again. Don’t get stuck in a loop of reading as many solutions as possible! We’ve analysed dozens of questions and selected ones that are commonly asked and have clear and high quality answers.
Here are some of the easiest questions you might get asked in a coding interview. These questions are often asked during the “phone screen” stage, so you should be comfortable answering them without being able to write code or use a whiteboard.
Question 1: Maximum subarray
- Text guide (Baeldung)
- Video guide (Back to Back SWE)
- Code example (FujiwaranoSai)
Question 2: Climbing stairs
- Text guide (Medium/Analytics Vidhya)
- Video guide (NeetCode)
- Code example (liaison)
Question 3: Pascal's triangle
- Text guide (Dev.to/seanpgallivan)
- Video guide (Nick White)
- Video guide (NeetCode)
- Code example (rheaxu)
Question 4: Pascal's triangle II
- Text guide (Aaronice)
- Video guide (Knowledge Center)
- Code example (LongsPeak)
Question 5: Best time to buy and sell stock
- Text guide (Medium.com/Algorithms and Coding)
- Video guide (Kevin Naughton Jr.)
- Video guide (take U forward)
- Code example (earlme)
Question 6: Counting bits
- Text guide (Medium/Yinfang)
- Video guide (NeetCode)
- Video guide (TECH DOSE)
- Code example (lixx2100)
Question 7: Is subsequence
- Text guide (Algorithms and me)
- Video guide (Kevin Naughton Jr.)
- Video guide (NeetCode)
- Code example (DBabichev)
Question 8: Fibonacci number
- Text guide (Medium/Fatboy Slim)
- Video guide (Nick White)
- Code example (pratik_patil)
Question 9: Min cost climbing stairs
- Text guide (Dev.to/seanpgallivan)
- Video guide (NeetCode)
- Video guide (Nick White)
- Code example (avval)
Question 10: Divisor game
- Text guide (Medium/Hanif Ariffin)
- Video guide (Lead Coding by FRAZ)
- Code example (lee215)
Question 11: N-th tribonacci number
- Text guide (Medium/cutesciuridae)
- Video guide (Alex Hoang)
- Code example (lee215)
Question 12: Get maximum in generated array
- Text guide (Tutorialspoint)
- Video guide (Algorithms Made Easy)
- Video guide (Timothy H Chang)
- Code example (YehudisK)
2. Medium dynamic programming interview questions
Here are some moderate-level questions that are often asked in a video call or onsite interview. You should be prepared to write code or sketch out the solutions on a whiteboard if asked.
Question 13: Longest palindromic substring
- Text guide (RedQuark)
- Video guide (NeetCode)
- Video guide (Errichto)
Question 14: Unique paths
- Text guide (Medium/Arpit Choudhary)
- Video guide (NeetCode)
- Video guide (Kevin Naughton Jr.)
- Code example (jianchao-li)
Question 15: Unique paths II
- Text guide (Medium/Nerd For Tech)
- Video guide (TECH DOSE)
- Code example (tusizi)
Question 16: Minimum path sum
- Text guide (Learn Coding Fast)
- Video guide (Kevin Naughton Jr.)
- Video guide (NeetCode)
- Code example (jianchao-li)
Question 17: Decode ways
- Text guide (Medium/Tech Life Fun)
- Video guide (Back to Back SWE)
- Video guide (Knapsak)
- Code example (yu6)
Question 18: Triangle
- Text guide (Jeff Okawa)
- Video guide (NeetCode)
- Video guide (Algorithms Made Easy)
- Code example (stellari)
Question 19: Unique binary search trees
- Text guide (Dev.to/codingpineapple)
- Video guide (NeetCode)
- Video guide (TECH DOSE)
- Code example (liaison)
Question 20: Best time to buy and sell stock II
- Text guide (Medium/Clark Johnson)
- Video guide (Kevin Naughton Jr.)
- Video guide (NeetCode)
- Code example (chipbk10)
Question 21: Unique binary search trees II
- Text guide (Tutorialspoint)
- Video guide (Casual Code Talk)
- Code example (jianwu)
Question 22: Interleaving string
- Text guide (After Academy)
- Video guide (Tushar Roy)
- Video guide (NeetCode)
- Code example (sherryxmhe)
Question 23: Palindrome partitioning
- Text guide (Educative)
- Video guide (Tushar Roy)
- Code example (yfcheng)
Question 24: Maximal square
- Text guide (After Academy)
- Video guide (NeetCode)
- Code example (arkaung)
Question 25: House robber
- Text guide (Medium/Sergey Piterman)
- Video guide (Nick White)
- Video guide (Kevin Naughton Jr.)
- Code example (heroes3001)
Question 26: Word break
- Text guide (Medium/Len Chen)
- Video guide (Knapsak)
- Video guide (NeetCode)
- Code example (segfault)
Question 27: House robber II
- Text guide (cheonhyangzhang)
- Video guide (NeetCode)
- Video guide (Naresh Gupta)
- Code example (lx223)
Question 28: Maximum product subarray
- Text guide (After Academy)
- Video guide (NeetCode)
- Code example (mzchen)
Question 29: Longest increasing subsequence
- Text guide (Techie Delight)
- Video guide (Back to Back SWE)
- Code example (dietpepsi)
Question 30: Perfect squares
- Text guide (Yu Coding)
- Video guide (TECH DOSE)
- Video guide (NeetCode)
- Code example (zhukov)
Question 31: Partition equal subset sum
- Text guide (Educative)
- Video guide (Kevin Naughton Jr.)
- Video guide (NeetCode)
- Code example (ZhuEason)
Question 32: Coin change
- Text guide (Techie Delight)
- Video guide (NeetCode)
- Video guide (Back to Back SWE)
- Code example (wyattliu)
3. Hard dynamic programming interview questions
Similar to the medium section, these more difficult questions may be asked in an onsite or video call interview. You will likely be given more time if you are expected to create a full solution.
Question 33: Regular expression matching
- Text guide (RedQuark)
- Video guide (Tushar Roy)
- Video guide (NeetCode)
- Code example (LeetCode)
Question 34: Maximal rectangle
- Text guide (Rohith Vazhathody)
- Video guide (Knapsak)
- Video guide (TECH DOSE)
- Code example (morrischen2008)
Question 35: Edit distance
- Text guide (After Academy)
- Video guide (Back to Back SWE)
- Video guide (Tushar Roy)
- Code example (anderson5)
Question 36: Wildcard matching
- Text guide (Techie Delight)
- Video guide (Keerti Purswani)
- Video guide (Tushar Roy)
- Code example (LeetCode)
Question 37: Distinct subsequences
- Text guide (Medium/Vivek Ranjan)
- Video guide (NeetCode)
- Code example (balint)
Question 38: Palindrome partitioning II
- Text guide (Medium/Anj)
- Video guide (happygirlzt)
- Code example (yavinci)
Question 39: Scramble string
- Text guide (just4once)
- Video guide (TECH DOSE)
- Code example (shaka_shadows)
Question 40: Best time to buy and sell stock III
- Text guide (Yu Coding)
- Video guide (Jayati tiwari)
- Video guide (TECH DOSE)
- Code example (meng)
Question 41: Burst balloons
- Text guide (Medium/Algorithms Digest)
- Video guide (Tushar Roy)
- Video guide (NeetCode)
- Code example (dietpepsi)
Question 42: Best time to buy and sell stock IV
- Text guide (WorkatTech)
- Video guide (TECH DOSE)
- Video guide (Jayati tiwari)
- Code example (jinrf)
Question 43: Dungeon game
- Text guide (just4once)
- Video guide (happygirlzt)
- Code example (RohanPark)
Question 44: Frog jump
- Text guide (Medium/Gobind Singh)
- Video guide (happygirlzt)
- Code example (quincyhehe)
Question 45: Arithmetic slices II - subsequence
- Text guide (Medium/Nitish Chandra)
- Video guide (happygirlzt)
- Code example (fun4LeetCode)
Question 46: Russian doll envelopes
- Text guide (Dev.to/seanpgallivan)
- Video guide (TECH DOSE)
- Video guide (happygirlzt)
- Code example (TianhaoSong)
Question 47: Freedom trail
- Text guide (Programmerall)
- Code example (shawngao)
Question 48: Cherry pickup
- Text guide (Massive Algorithms)
- Video guide (TechLife With Shivank)
- Code example (fun4LeetCode)
Question 49: Concatenated words
- Text guide (Tutorialspoint)
- Video guide (happygirlzt)
- Code example (shawngao)
Question 50: Remove boxes
- Text guide (Tutorialhorizon)
- Video guide (Coding Decoded)
- Code example (fun4LeetCode)
Question 51: Student attendance record II
- Text guide (programmeralll)
- Video guide (Tony Teaches)
- Code example (KJer)
Question 52: K inverse pairs array
- Text guide (Medium/dume0011)
- Video guide (Coding Decoded)
- Code example (dreamchase)
Question 53: Decode ways II
- Text guide (Programmerall)
- Video guide (Coding Decoded)
- Code example (Luckman)
4. How to prepare for a coding interview
4.1 Refresh your knowledge
Before you start practicing interviews,you’ll want to make sure you have a strong understanding of not only dynamic programming but also the rest of the relevant algorithms and data structures. Check out our guides for detailed explanations and useful cheat sheets.
Algorithms explained:
- Depth-first search
- Breadth-first search
- Binary search
- Sorting
- Dynamic programming
- Greedy algorithm
- Backtracking
- Divide and conquer
Data structure guides:
4.2 Practice on your own
Once you’re confident in all of these, you’ll want to start working through lots of coding problems.
For depth-first search you can obviously use the questions we’ve listed above. For the other algorithms you need to know, check out the rest of this series:
- Depth-first search interview questions
- Breadth-first search interview questions
- Binary search interview questions
- Sorting interview questions
- Greedy algorithm interview questions
- Backtracking interview questions
- Divide and conquer interview questions
We also recommend working through our list of 73 data structure interview questions. To get used to an interview situation, where you’ll have to code on a whiteboard, we recommend solving the problems on a piece of paper or google doc.
One of the main challenges of coding interviews is that you have to communicate what you are doing as you are doing it. Talking through your solution out loud is therefore very helpful. This may sound strange to do on your own, but it will significantly improve the way you communicate your answers during an interview. Of course, if it’s with someone else playing the role of the interviewer, even better.
4.3 Practice with others
However, sooner or later you’re probably going to want some expert interventions and feedback to really improve your coding interview skills.
That’s why we recommend practicing with ex-interviewers from top tech companies. If you know a software engineer who has experience running interviews at a big tech company, then that's fantastic. But for most of us, it's tough to find the right connections to make this happen. And it might also be difficult to practice multiple hours with that person unless you know them really well.
Here's the good news. We've already made the connections for you. We’ve created a coaching service where you can practice 1-on-1 with ex-interviewers from leading tech companies. Learn more and start scheduling sessions today.
Any questions about dynamic programming interview questions?
If you have any questions about dynamic programming or coding interviews in general, don't hesitate to ask them in the comments below. All questions are good questions, so go ahead!