Design search autocomplete
Typeahead for web or app search: prefix matching, ranking, and extreme read QPS with tight latency budgets.
~22 minDesign interview
Step 0 / 0
Interview script (outline)
- Clarify: scope (web docs vs global query log), languages, offensive filtering, personalization level.
- Estimate: keystroke rate, suggestions per keystroke, p99 latency target (often <100ms).
- Data structure: trie / prefix tree / FST; optional n-gram index for fuzzy.
- Ranking: popularity, previous clicks, freshness; A/B bucket.
- Serving: cache hot prefixes at edge; debounce client; collapse duplicate requests.
- Update path: batch index build + streaming updates for fresh queries.