Dynamic programming: interview drill
Timed one- and two-dimensional DP problems from the NeetCode-150, with progressive hints — solve each cold, then narrate the complexity.
You understand memoization and tabulation. Interviews test whether you can spot the overlapping subproblem under a timer, write the recurrence, and explain why it is correct out loud.
Solve each problem before you reveal a hint, hit the target time, and narrate the time and space complexity as if an interviewer were listening. The hints exist for when you are genuinely stuck — they nudge you toward the pattern, never the full solution.
Six NeetCode-150 problems on the one- and two-dimensional DP patterns this unit teaches. Set a timer, solve each cold without looking at a hint, then say the time and space complexity out loud before you move on. Reveal a hint only when you are truly stuck — the hints nudge, they never hand you the answer.
0/6 solved
1d dp
Follow-up (aloud)
You only ever read the last two states. Narrate how that collapses the space from O(n) to O(1).
Follow-up (aloud)
What is the optimal-substructure argument here — why does the best answer for the prefix only depend on the previous two answers?
Follow-up (aloud)
State the time and space complexity in terms of amount and number of coins. Why does greedy fail but DP not?
Follow-up (aloud)
In the O(n log n) version, the 'tails' array length is the answer but its contents are not a real subsequence. Why is that still correct?
2d dp
Follow-up (aloud)
State the time and space complexity for strings of length m and n, then explain how to drop the space to O(min(m,n)).
Follow-up (aloud)
There is also a pure combinatorics answer: C(m+n-2, m-1). Why does the grid DP equal that binomial, and which would you write in an interview?
Mark each problem solved once you finished it cold, inside the target time, and could state the recurrence and complexity without hesitation. Come back in a few days and re-solve the ones you marked — spaced revisits are what turn a recognised pattern into a reflex.
Something unclear?
Ask a question about this lesson. Questions are anonymous and go straight to the author to make the lesson better.