Design a search autocomplete (typeahead) system like Google's search box. As a user types each character, the system suggests the top 10 completions ranked by popularity. The system handles 100,000 queries per second, draws from a corpus of 5 billion historical search queries, and must return suggestions within 100ms. Suggestions update as new searches are performed (a query trending today should appear within minutes).
In your 90-second answer, cover: - Data structure for efficient prefix matching across billions of terms - How you rank and select the top 10 suggestions for a given prefix - Caching strategy for hot prefixes and the long tail of rare ones - How the suggestion corpus is updated as new queries arrive
Constraints: p99 latency must be under 100ms. The client should debounce requests (not send on every keystroke). Suggestions must reflect trending queries within 15 minutes.
How to approach it
- Hint 1
Think about what data structure lets you efficiently find all strings sharing a common prefix. A Trie (prefix tree) is the classic choice -- each node can store the top-K results for that prefix to avoid traversing the entire subtree at query time.
- Hint 2
Not every prefix needs to hit the Trie. The most popular prefixes (top 1-2 characters) can be cached in Redis or at the CDN edge. Consider how cache hit rates vary by prefix length -- short prefixes are queried far more often.
- Hint 3
The Trie cannot be rebuilt on every new search query. Use an offline pipeline that periodically aggregates query logs, computes frequencies, and rebuilds the Trie. Serve from the old Trie while the new one is being built, then swap atomically.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.