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.1 What do you ask first?
3 min read+10 XP
Step 1: Requirements (5 minutes)
| Letter | Candidate asks | Interviewer answers |
|---|---|---|
| Scope | "Suggestions are past searches, or book titles too? Personalised? Multiple languages? Spelling correction?" | "Popular past searches, plus new book titles. Not personalised for now. English only. Skip spelling correction." |
| Count | "How many users and searches?" | "10 million daily active users, about 3 searches each a day." |
| Access pattern | "Do we call on every keystroke?" | "Yes, after the client waits ~100 ms between keystrokes." |
| Latency | "How fast must suggestions appear?" | "Faster than the user types: under 100 ms end to end." |
| Exactness | "Must suggestions reflect searches from the last minute? Exact popularity?" | "Roughly right is fine. New launches should show up the same day." |
Agreed requirements:
- Functional (verbs): as the user types a prefix, return the top 5 suggestions; learn from searches over time; surface trending queries and new titles within hours; filter inappropriate suggestions.
- Non-functional (adjectives): very fast (server time under ~20 ms, total under 100 ms), highly available (if suggestions fail, search still works), scalable for keystroke traffic, fresh within hours, safe (no offensive or manipulated suggestions).
Interviewer pushback:
- "Why not just query the search index (Chapter 19) on every keystroke?" → A full search ranks documents and is far too slow and heavy to run per keystroke at this volume. Suggestions should be a precomputed lookup, built offline from what people search.
- "What's 'top'?" → Ranked by a score: mostly how often a query is searched, blended with how fast it's rising (34.8).
Memory code: "Every keystroke is a request; answer from a table, not a search."