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

Greedy

Greedy with sorting

Sort, then take the locally best choice; prove it with an exchange argument.

Visual guide Quiz (10) Spot the pattern
Notes

Recognise it when: a locally best choice never hurts. Typical shapes: interval scheduling, the earliest deadline, the smallest or largest first, "can we reach the end".

  • Max non-overlapping intervals: sort by end and take every interval that starts after the last one you took ended.
  • Jump game: track the farthest index reachable so far. If i > farthest, you're stuck.
  • Gas station: if total gas < total cost, it's impossible. Otherwise, restart from i + 1 whenever the running tank goes negative.

Prove it (or at least argue it) with an exchange argument: swapping any optimal solution's first choice for the greedy choice never makes it worse.

Gotchas: many problems look greedy but need DP. Coin change with arbitrary denominations is the classic trap, so test a counterexample before committing.

21 problems

Interview roadmap

Greedy Sort, then take the locally best choice.

esc