Design search autocomplete
Suggest the top completions as the user types into a search box.
Why interviewers ask it
It tests data structures at scale (tries), precomputing results, caching, and separating serving from data processing.
Functional requirements
- Return the top 5–10 suggestions for a prefix.
- Rank by popularity, and by freshness.
Non-functional requirements
- Very fast: under about 100 ms per keystroke.
- Highly available; suggestions can be slightly out of date.
From version 1 to the final design
- Version 1: an SQL query: LIKE 'prefix%' ORDER BY count LIMIT 5.
- Version 2: an in-memory trie, searching the subtree on each request.
- Version 3: top-k precomputed at every node, rebuilt by a background job.
- Version 4: tries split across servers, edge caching, trending updates and filtering.
The design, step by step
- Serving: an in-memory trie (or a prefix → top-k map in Redis); a lookup just walks the prefix.
- Data pipeline: log searches → count them every hour or day → rebuild the trie → swap the new one in.
- Client: wait for a short pause in typing before asking, and cache recent prefixes; cache common prefixes at the edge.
- Split the trie across servers by prefix when it gets too big.
Deep dives
- Store the top-k completions at every node, so a query never has to search a whole subtree.
- Freshness: trending terms through a streaming pipeline, with older counts decaying over time.
- Filter offensive or harmful suggestions out of autocomplete before they are shown.
- Personalisation: blend global suggestions with the user's own history.
Common mistakes
- Searching the whole subtree on every keystroke.
- Rebuilding the trie inside the serving path.
- Sending a request on every keystroke, with no pause.
Not true: An autocomplete box should send a request for every single keystroke, with no pause.
In fact: Most of those requests are out of date before the reply arrives. Wait a short moment after the last keystroke, and far fewer requests are sent.
In the interview
Suggestions are served from an in-memory trie where each node already stores its top-k completions, so a lookup is just walking the prefix. Search logs feed a background job that rebuilds the trie regularly. Clients wait for a pause in typing and cache results, and popular prefixes are cached at the edge.
Part of Unit 8: High-level design questions in the free System Design course.