System designMediumsd-g342

Subject AutocompleteLevel Mid–Senior~40 minCommon in Distributed systems interviewsIndustries Technology

Question

Design typo-tolerant autocomplete that still returns good suggestions when the user mistypes the prefix — 'restaraunt', 'bluetooth', 'iphine' — within a 50ms p99 budget at 500k QPS. Exact-prefix trie matching returns nothing for a typo. You can't run full edit-distance against millions of terms per keystroke. How do you make fuzzy matching fast enough to stay on the autocomplete hot path?

What a strong answer looks like

Clarify scale and constraints first. Propose a clean component breakdown, then go deep on the hard parts — data model, bottlenecks, consistency, failure modes — and name the trade-offs you are making.

Learn the concepts

Narrate your design

Loading whiteboard…

Run or narrate your approach, then ask the coach.