34. Design Search Autocomplete (Typeahead)
1
The interview prompt2
34.1 What do you ask first?3
34.2 How big is this, really?4
34.3 What are the doors?5
34.4 What do we store?6
34.5 What does the whole system look like?7
34.6 Trie or prefix index?8
34.7 How do you compute top-K per prefix?9
34.8 How do suggestions follow trends?10
34.9 How do you cache suggestions?11
34.10 What would you say in the last five minutes?12
Score yourself13
Variations to practise14
Sources15
Code lab34. Design Search Autocomplete (Typeahead)
34.2 How big is this, really?
3 min read+10 XP
Step 2: Estimates (5 minutes)
Assume about 8 requests per search (one per keystroke after debouncing), a peak factor of 5, about 50 million distinct queries seen in a month, about 6 new prefixes per query after sharing common starts, and 25 bytes per stored suggestion.
| What | Working | Result |
|---|---|---|
| Requests a day | 10 million × 3 × 8 | 240 million |
| Average requests a second | 240 million ÷ 86,400 | ≈ 2,800 |
| Peak | 2,800 × 5 | ≈ 14,000 a second |
| Prefixes | 50 million × 6 | ≈ 300 million |
| Prefix table | 300 million × 5 × 25 bytes | ≈ 37.5 GB before pruning |
| After pruning rare queries | keep queries searched ≥ a few times (assumed ~10× fewer) | ≈ 4 GB: fits in memory |
What the numbers say, out loud:
- "14,000 reads a second with a sub-20 ms budget means memory lookups, not queries. A cache or in-memory KV store."
- "Writes are offline. The table changes hourly or daily, not per request, so reads never compete with writes."
- "Prune the long tail. Most distinct queries are typed once; they'll never be in anyone's top 5, so don't store them."
Interviewer pushback:
- "Why does debouncing matter?" → Without it, a user typing 'database' sends 8 requests in a second; with a ~100 ms pause rule, fast typists send fewer, and the client can also cancel stale requests. It cuts load and avoids flicker.
Memory code: "Huge reads, offline writes, prune the tail."