~/problems

Problems

Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.

1-D dynamic programming

Intro DP

State, transition, base case; top-down memo vs bottom-up table.

Visual guide Quiz (11) Spot the pattern
Notes

Recognise it when: you're asked for a count of ways, a min or max over choices, or "can you reach", and the subproblems overlap.

Four questions: What is the state? What is the transition? What are the base cases? What order do you fill the table in?

# House robber: best up to i = max(skip i, take i)
prev2 = prev1 = 0
for x in nums:
    prev2, prev1 = prev1, max(prev1, prev2 + x)
  • Top-down: @functools.cache on a recursive function is fastest to write, but watch the recursion limit.
  • Bottom-up plus rolling variables gives O(1) memory.
  • Decode ways: dp[i] = dp[i-1] (one valid digit) + dp[i-2] (valid 10..26). The trap is "0".

17 problems

Interview roadmap

1-D dynamic programming One index of state: stairs, robbers, subsequences.

Intro DP guide

esc