Design Search Typeahead
Design the autocomplete box for Pinterest search. As the user types, show the top ten suggestions. It should feel instant, work for hundreds of millions of users, and reflect what's trending, not just what was popular last year.
Assume prefix matching on the whole query plus the last token, no spell-correction in v1. Suggestions come from real user queries, ranked by a popularity score with time decay; blocked terms must never appear (a hard filter, not a ranking signal). Base popularity refreshes hourly; trending spikes should be visible within minutes. Latency budget: p99 under 100 ms end to end, which leaves ~20 ms in the service. Multi-language, per-locale suggestions.
Cover: the data structure and its top-k tradeoff, how you shard, how snapshots roll out without downtime, and where trending freshness comes from.
Hints
Hint 1
Size it before choosing a structure: ~100M distinct suggestible queries × 40 B ≈ 4 GB of strings, times 3–4 for per-node top-k lists. Tens of GB fits in RAM across a few shards — disk never belongs on the read path.
Hint 2
Hash-sharding whole queries forces scatter-gather on every keystroke. Shard by prefix range so a lookup hits exactly one shard, then handle the skew ('s' vs 'x') with data-driven boundaries and per-shard replication.
Hint 3
Incremental trie updates are the trap: a count change touches a list at every prefix node. Build snapshots offline, roll them out with an atomic pointer swap, and layer a tiny streaming delta on top for trends.
Asked at
Sign in to talk to the interviewer — ask what's in scope, what scale to design for, or for a nudge when you're stuck. Conversations save to your account.