Design Search Autocomplete (Typeahead)
Suggest top completions per keystroke in single-digit milliseconds using a trie.
Overview
Autocomplete suggests the top-k most likely completions as a user types. It's extremely read-heavy and latency-critical (it fires on every keystroke), which makes the trie + precomputation design a clean, focused interview.
Requirements
Functional
- Given a prefix, return the top-k (e.g., 5–10) suggestions.
- Rank suggestions by popularity/frequency.
- Update suggestions as query trends change.
- Support fuzzy/typo tolerance (stretch).
Non-functional
- Very low latency (< 20 ms) — it runs per keystroke.
- Massively read-heavy; writes (trend updates) are batched and infrequent.
- Scale to millions of QPS.
Back-of-the-envelope
The numbers that justify the architecture.
| Queries / day | ~5B searches | |
| Autocomplete QPS | 20× | each search = several keystroke lookups |
| Latency budget | < 20 ms | |
| Vocabulary | billions of phrases |
Reference architecture
A precomputed trie (each node caching its top-k completions) served from memory, rebuilt offline from an aggregated query-frequency log.
Deep dives
The trie, and why you precompute top-k
A trie (prefix tree) maps prefixes to completions: walking the characters of a prefix lands you at a node whose subtree contains all completions. But traversing that subtree per keystroke is too slow. The trick is to precompute and cache the top-k completions at each node. Then a lookup is: walk to the prefix node (O(prefix length)) and return its cached list — no subtree scan. This turns a search into a near-constant-time memory read.
Ranking and updates
Suggestions rank by frequency (plus recency/personalization). You cannot update the trie on every query — instead, aggregate query counts offline (a streaming/batch job over the query log), rebuild or incrementally update the trie's cached top-k lists periodically, and hot-swap the snapshot. Trends thus lag by minutes, which is fine. Sampling counts keeps the aggregation tractable at billions of queries.
Scale and latency
Keep the trie in memory, sharded by first characters/prefix ranges across servers so it fits and load spreads. Cache hot prefixes at the edge/CDN — the top prefixes serve a huge share of traffic. Debounce on the client (fire after a short pause, not every keypress) to cut QPS. The whole design is about doing the expensive work offline so the online path is a memory read.
Key trade-offs
For each decision: the two options, and when to pick which.
Bottlenecks & follow-ups
Where it breaks under load — and what an interviewer will probe.
- ▲Trie too big for one node → shard by prefix range.
- ▲Per-keystroke QPS → client debounce + edge caching of hot prefixes.
- ▲Update cost → offline aggregation + snapshot hot-swap.
What a strong answer sounds like
- ✓The one insight that matters: cache top-k at each trie node. Say it early.
- ✓Separate the offline build path from the online serving path explicitly.
- ✓Mention client debouncing and edge caching to tame the keystroke QPS.