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.