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)
Score yourself
3 min read+10 XP
Score yourself
Give yourself 0, 1 or 2 points per row.
| Area | 0 points | 1 point | 2 points |
|---|---|---|---|
| Requirements | Started drawing | Listed features | Latency per keystroke, freshness and safety agreed |
| Estimates | None | Numbers, not used later | Numbers that showed reads must be memory lookups and the tail must be pruned |
| API and data | Skipped | API or store, not both | Cacheable GET, debounce, prefix → top-K store with versions |
| High-level design | Queries the database per keystroke | Read path only | Read path and offline/streaming build path, with atomic publish |
| Deep dive | Hand-waved | Trie described | Top-K per prefix, trend blending or multi-layer caching done properly |
| Trade-offs | None named | Named when asked | Raised unprompted (freshness vs cache, manipulation, storage vs speed) |
| Communication | Long silences | Mostly clear | Thought out loud, checked in, managed time |
12 to 14: strong hire signal. 8 to 11: solid, polish the weak rows. Under 8: redo the round in a week, timer on.
The bar: fresher vs SDE-2
| Fresher | SDE-2 | |
|---|---|---|
| Data structure | Trie, walked per request | Top-K per prefix, served from a flat table |
| Building | "Update counts on every search" | Offline batch + streaming trends, atomic publish |
| Freshness | Rebuild daily | Decayed recency blended with long-term popularity |
| Scale | One server | Sharded in-memory store, CDN and client caching, hot short prefixes |
| Safety | Not mentioned | Filters, unique-user counts, purge path |
Common mistakes
- Running a search query or a SQL
LIKE 'dat%'per keystroke. - Walking the trie's subtree at request time for short prefixes.
- Writing to the trie on every search, mixing heavy writes into the read path.
- No debounce or client cache, multiplying traffic.
- Ignoring manipulation and offensive suggestions.
Quick check
Five questions on this chapter. Pick an answer, then check it.
quiz