Typeahead system design
Design typeahead for our shop's search box.
The problem
Typeahead shows the 10 most searched queries that start with the letters typed so far (the prefix).
A search ends when the person picks a suggestion or presses Enter.
Questions to ask the interviewer
How many searches?
About 100 searches a second.
How many letters does a person type?
About 8, one request each, before they pick a suggestion.
How fast must it be?
Suggestions in under 100 ms.
Where do the top 10 come from?
Last month's searches, counted once by our data team.
What is the budget?
About $135 a month.
Want to try it yourself first? Play, then come back for the approach.
PlayThe design in short
Typeahead must answer while the person is still typing. That leaves very little time: suggestions in under 100 ms, for every letter. So the speed of one request is the requirement that shapes everything else.
Where does the time go? The top 10 for a prefix come from last month's searches, counted once. Nothing about them changes between two keystrokes. So ask: does the answer for a prefix have to be worked out when the request comes in? Compare the work of one request in each case, and you see where the time goes.
One search is many requests. A person types about 8 letters before they pick, and each letter is a request. So multiply searches a second by letters per search to get your real load. That number, not the number of searches, sizes the servers.
Questions for each box you draw:
- how many machines answer the prefix requests
- where the top 10 for each prefix comes from, and how fast one read is
- how big the stored lists get as the number of prefixes grows
The main trade-off is fresh against fast. Work done ahead is fast at request time but can be old. Work done on each request is fresh but slow. The brief says the data team counts once, so you know how fresh you must be.
Ask the interviewer what counts as one search. The playable version shows those letters arriving, one request each.
Last updated 22 October 2026