Spell Checker
Suggest corrections ranked by edit distance, string matching with a bug → feature → scale arc.
Problem
A spell-checker service holds a dictionary of words and checks typed words against it. The starter code has a bug.
Phase 1: Fix the bug
lookup(word) returns false for "Hello" when the dictionary contains "hello". Word comparisons must be case-insensitive.
Phase 2: Feature
Add suggest(word, k): return the k dictionary words closest to word by edit distance (insertions, deletions, substitutions), ordered by distance then alphabetically. Ignore an exact match.
Phase 3: Scale
The dictionary grows from thousands to millions of words. Suggestions must stay fast: a full distance computation against every word won't survive.
What interviewers watch
Whether you pick the edit-distance flavor deliberately, keep normalization consistent, and think about bounding the candidate set before scaling.