Dynamic programming interview questions
Turning repeated recursion into tables: state, transition, base case and fill order, from one-row counts to two-string tables, with the memory tricks interviewers ask about.
– interview-ready · 18 questions in this topic
– of 18 tried
Saved on this device. Interview-ready means you got it right on two different days. Guesses and hints count for less.
Questions
- Ways to cross n stepping stones, one or two at a timePredict
- Fewest coins to make an amountPredict
- Fewest edits to turn one word into anotherPredict
- Best haul without opening two neighbouring lockersPredict
- Best haul when the lockers form a ringPick the fix
- Ways to read a digit string as letters (1 = A … 26 = Z)Predict
- Can a string be split into dictionary words?Predict
- Longest rising sequence of picks from a listPredict
- Longest shared subsequence of two stringsPredict
- Routes across a grid with blocked cellsPredict
- Cheapest route from top-left to bottom-rightPredict
- Split items into two piles of equal weightPredict
- Number of ways to pay an amount with unlimited coinsPredict
- Largest product of a contiguous runPredict
- Dynamic programming in four stepsOrder the steps
- Top-down caching or bottom-up tables?Predict
- Saving memory with rolling rowsPredict
- How to tell a problem needs DPPick the fix
Practise this topic
Flashcards · 28
Flip, then say if you knew it. Needs JavaScript; every answer is also on its question page.
Quick quiz · 18 questions
One exercise per question, checked as you go. Needs JavaScript.
Mock interview · 3 sets
Timed, out loud, then tick what you covered. Needs JavaScript.
Quick facts
Recall the answer first, then tap Show to check.
functools.cache@cache(Python 3.9+) memoises a function by its arguments with no size limit;@lru_cache(maxsize=None)is the same.Cache arguments must be hashable
Memoised functions need hashable arguments: pass tuples or indexes, not lists.
Recursion depth in top-down DP
A top-down solution recurses once per state along a chain, so n above about 1,000 needs a bottom-up loop in CPython.
[[0] * n for _ in range(m)]Build 2-D tables with a comprehension;
[[0] * n] * mrepeats one row object m times.math.inffor 'impossible'math.infcompares greater than any integer, somin(best, x)works without special cases.
Printable cheat sheet · Review your weak spots in this topic
Share your progress
Sources: Topic outline informed by the Tech Interview Handbook by Yangshun Tay and the NeetCode 150 pattern grouping by neetcode-gh, both MIT licensed. Every problem, solution and explanation is written by Best Latest Apps. Credits and license