Prompt
As the user types each character, return the top ~10 completions ranked by popularity. Billions of queries a day, p99 under ~100 ms per keystroke, and suggestions should reflect what people are actually searching for.
This is the web-scale version of the tries data structure — the interview checks whether you can take an in-memory trie to production. SDE-1: the trie and prefix walk. SDE-2: caching top-k per node, the offline build, and the latency budget. SDE-3 / Staff: sharding a giant trie, freshness vs. speed, personalization, and ranking. Asked at Google, Amazon, LinkedIn, Meta, Elastic.
1. Requirements
Functional: prefix → top-k completions ranked by popularity; reflect fresh/trending terms. Non-functional: p99 under ~100 ms (it fires on every keystroke, so the budget is brutal); extremely read-heavy; eventual freshness is fine — suggestions can lag minutes or hours behind reality without anyone noticing.
That last point is the key unlock: because suggestions don't need to be real-time, you can precompute aggressively.
2. Core data structure — a trie with top-k baked in
A trie maps prefixes to completions. The naive query — walk to the prefix node, then DFS all descendants and sort by frequency — is far too slow per keystroke for a popular prefix with millions of completions.
The fix: precompute and cache the top-k completions at each trie node. A query becomes:
- Walk to the prefix node — O(length of prefix).
- Return its cached top-k list — O(k).
No descendant scan, no per-query sort. Memory cost is k entries per node, which is the trade you happily make for a 100 ms budget.
1/25An empty trie — just a root with no letters. We'll insert: "car", "cat", "card", "do", "dog".
3. The offline build pipeline
Do not mutate the trie on every search — that would couple the write firehose to the read path. Instead:
query logs ──▶ aggregate (query, count) over a rolling window (MapReduce / stream)
──▶ build a weighted trie, precompute top-k per node (offline job)
──▶ ship an immutable snapshot to serving nodes (load into memory)
Serving nodes hold a read-only snapshot and swap to a fresh one periodically. You trade freshness (minutes/hours) for a serving path that's pure in-memory reads. Trending terms get a shorter window or time-decay so today's spike surfaces fast.
4. Serving & scale
- Shard by prefix (first 1–2 characters): the
a…trie lives on one set of nodes,b…on another. A query routes by its prefix to exactly one shard. - Replicate hot shards — common first letters get far more traffic.
- Cache + CDN the most common short prefixes at the edge; they dominate volume.
- Client-side debounce: only fire after a short pause in typing to cut request count.
5. Ranking
Popularity is the base signal, but strong suggestions blend:
- Frequency — the cached count from the logs.
- Recency / trending — time-decayed counts so spikes rise quickly.
- Personalization — the user's own history, language, location (applied as a re-rank on top of the global list, not a separate trie per user).
- Hygiene — de-dupe near-identical queries, filter offensive terms, basic spell correction. Learning-to-rank is the natural ML follow-up.
6. Deep dives
- Fresh trends fast: keep a small, short-window "trending" trie merged on top of the big slow one, so breaking terms appear without a full rebuild.
- Typos: fuzzy prefix matching via edit-distance (bounded) or a symspell-style index.
- Mid-word / multi-word: index suffixes or n-grams, not just whole-query prefixes.
Design drills
Whiteboard each one out loud for 5–10 minutes before you reveal what a strong answer covers — the gap between your sketch and the checklist is your study list. Progress is saved on this device.
Justify precomputing top-k at each node instead of scanning descendants per query.
Keep suggestions fresh without rebuilding the whole trie constantly.
The global trie is too big for one machine. Shard it.