~/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.

2-D dynamic programming

Knapsack and coin change

0/1 vs unbounded; loop order decides combinations vs permutations.

Visual guide Quiz (10) Spot the pattern
Notes

Recognise it when: you choose items under a capacity or target: subset sum, coin change, partitioning.

# 0/1 (each item once): iterate capacity DOWNWARD
for w, v in items:
    for c in range(C, w - 1, -1):
        dp[c] = max(dp[c], dp[c - w] + v)

# Unbounded (reuse items): iterate capacity UPWARD
# Coin change II (combinations): coins outer, amount inner
# Combination Sum IV (ordered):  amount outer, coins inner
  • Minimum coins: dp[a] = min(dp[a], dp[a - coin] + 1) with dp[0] = 0, starting from infinity.
  • Partition into equal subsets is a 0/1 subset sum with target total // 2. It's impossible if the total is odd.

Gotchas: greedy coin change is wrong for arbitrary coins, e.g. [1, 3, 4] with a target of 6.

11 problems

Interview roadmap

2-D dynamic programming Grids, two strings, knapsacks, ranges.

Knapsack and coin change guide

esc