Autocomplete is two systems: an offline pipeline that builds an immutable trie, and an online service that only reads it. The interview tests whether you see that the pipeline is the real system and that keystrokes are the real traffic.
Requirements and capacity
Top-5 completions per prefix, p99 under 50ms measured at the edge. 500M searchers; 1B queries/day, but every keystroke is a query → ~10B keystrokes/day ≈ 116k keystroke QPS average, 500k+ at peak. Keystroke traffic is an order of magnitude above query traffic — the whole serving design has to be cheap per keystroke.
The pipeline (the part people skip)
Query logs → hourly aggregation (count per term) → trie build → versioned snapshot to blob store → push to serving fleet. Serving never writes; it loads immutable tries and swaps versions. Freshness lag: a term that trends at 8pm appears at the next build — hourly builds are the default; daily is too stale for news, minute-level is too expensive for 99% of terms. This tradeoff is a real product decision — say it as one.
The trie
Node = (children map, precomputed top-5 suggestions with counts, subtree count). Precomputing top-N per node at build time is the move: serving is a walk of the prefix (O(prefix length), ~30–100ns per char in RAM) plus reading the precomputed top-5 — zero subtree traversal at query time. Size: ~10M distinct prefixes × ~200B ≈ 2–4GB per shard — that fits in RAM, and RAM is a requirement, not a luxury: 1µs access vs 100µs on SSD is the difference between 50ms p99 and 500ms. Say "the trie must be RAM-resident" as a hard constraint.
Sharding and serving
Partition by first character(s) — each shard owns a subtrie; hot shards (common first letters) get replicated. Consistent hashing over the shard set keeps rebalancing cheap. Serving path: CDN/edge cache of prefix → top-5 with minute-scale TTL absorbs the bulk of keystrokes; miss → shard lookup → top-5. Personalization is the enemy of cacheability: serve generic suggestions from the edge cache; personalize only on a small fraction (or client-side), because a per-user cache is a per-user cost.
Rate limiting
Keystroke traffic is 10x query traffic and mostly junk (bots, rapid backspacing): debounce at the client, rate-limit per client at the edge (rate-limit-trace), and cap at one suggestion response per ~100ms per session. Cheap to say, expensive to skip — it decides whether the fleet is sized for humans or for bots.
Bottlenecks
Keystroke amplification; hot-prefix shards (the letter "a" is a shard, and it is hot); build latency for fresh terms; RAM cost of the trie; and cache invalidation on version swaps. The winner names these in order of blast radius: traffic, freshness, memory.