Design autocomplete / typeahead suggestions
The setup
"A user starts typing in a search box. As they type each character, suggest completions in real-time. 100M users; each user makes ~10 search queries/day; suggestions must appear within 100ms of keystroke."
This problem tests data-structure knowledge. The naive approach (substring search over a corpus) is hopeless; the right data structure (trie + precomputed top-K) is dramatically faster. The interview test is whether you can identify the right data structure and then architect around it.
Clarifying questions
| Question | Story answer |
|---|---|
| Suggestions from what corpus — user queries, dictionary, product names? | Top user queries (search log analysis). |
| How many suggestions per keystroke? | Top 10 ranked by popularity. |
| Personalized? | Skip personalization for v1; mention briefly. |
| How fresh do new trending terms need to be? | Eventual: ~1-hour delay is acceptable. |
| Languages? | English for this design; mention multi-language at end. |
Capacity estimation
QPS: 100M users × 10 queries/day = 1B queries/day = ~12K queries/sec average But each query has multiple keystrokes (~10 average); each keystroke triggers a suggestion request: 12K queries × 10 keystrokes = 120K suggestion requests/sec Peak: ~500K/sec Corpus size: ~10M distinct popular terms (long-tail of unique queries, but trie nodes are shared by prefix) Avg word length: ~10 chars Trie node count: ~10M words × ~10 chars / avg fan-out ~5 = ~20M trie nodes Each node ~100 bytes (children map, top-K cache, metadata) Total trie size: ~2 GB — fits comfortably in memory
The data structure: trie with top-K cache
A trie (prefix tree) is the natural fit. Each path from root represents a prefix.
Root ├── 'c' │ ├── 'a' │ │ ├── 't' → 'cat' (popularity: 95) │ │ │ └── 's' → 'cats' (popularity: 60) │ │ └── 'r' → 'car' (popularity: 80) │ │ └── ... │ └── 'o' │ └── 'm' → 'com' ... etc.
For "ca" → traverse to 'a' node → look up children. Want top-10 from this subtree.
Design Decision 1: precomputed top-K at each node
Without optimization, finding top-K completions of "ca" requires walking all descendants of the "ca" node — potentially thousands of words. Per-keystroke at 500K req/sec, this is infeasible.
Precompute top-K at each trie node: each node stores the top-10 completions in its subtree, ranked by popularity. Lookup of "ca" → traverse 2 nodes → return cached top-10. O(prefix-length) operation, microseconds.
Cost: each trie node stores a 10-element list of (term, score). Adds ~200 bytes per node. Total: 20M × 200 = 4 GB. Still fits in memory.
Design Decision 2: how to update with new data
New search terms become popular every day. The trie must update.
| Approach | Tradeoff |
|---|---|
| Live updates | Each search event updates popularity; trie continuously rebuilt. Complex; lock contention |
| Periodic full rebuild | Every N minutes/hours, rebuild trie from current popularity scores; deploy to nodes |
| Delta updates | Apply incremental changes; merge top-K caches at each node |
Production pick: periodic full rebuild (every 1 hour). Aggregation job: count term frequencies from search logs → produce ranked term list → build a fresh trie offline → deploy to autocomplete service nodes (rolling update).
For real-time edge (trending right now): a smaller "delta trie" rebuilt every 5 minutes, merged with the base trie. Catches breaking news terms within minutes.
The architecture
SEARCH LOG STREAM
│
↓
[Kafka: search events]
│
↓
[Aggregation pipeline]
- Every hour: count term frequencies
- Produce ranked term list
│
↓
[Trie build job]
- Construct trie from ranked terms
- Precompute top-K at each node
- Serialise to compact format
│
↓
[Trie distribution]
- Push new trie to all autocomplete service nodes
- Rolling update: each node loads new trie, switches over
│
↓
[Autocomplete Service nodes (sharded by ... actually no, replicated)]
- Each holds full trie in memory (~4 GB)
- Serves keystroke queries in microseconds
│
▲
[Client app] sends keystroke → service returns top-10 suggestions
Important: trie isn't sharded; it's replicated. Each autocomplete service node has the full trie. Why: queries hit any node, and we need predictable low latency. 4 GB fits easily; replicate to many nodes; load-balance reads.
Cross-examination round 1: real-time updates
A: Smaller corpus (top-1000 trending terms in last hour). Trie build: a few seconds. Deploy: every 5 minutes. Memory: ~10 MB. Each query: lookup in base trie + lookup in delta trie + merge top-K. Negligible cost per query (still microseconds). Worth the freshness gain.
Cross-examination round 2: personalization
Cross-examination round 3: multi-language
Takeaway
Autocomplete is a specialized problem where the right data structure (trie + precomputed top-K) makes the system 100× faster than naive approaches. The systems lesson: the right data structure often beats the right infrastructure. A trie in RAM beats a database scan no matter how big your database cluster is. Before reaching for distributed systems patterns, ask: is there a data structure that makes this trivial?
The deeper insight: recognize when a problem has a known optimal data structure. Search systems have inverted indexes; autocomplete has tries; geospatial has spatial trees; routing has graphs. The architecture is downstream of the data structure. Choose the structure first.