Design a search typeahead
Medium40 minFree, no account
A 50ms budget, a request per keystroke, and a data structure you precompute.
The question
Design the suggestion service behind a search box: as the user types, show the ten most likely completions.
It must feel instant.
Functional
- Return the top 10 completions for any prefix.
- Rank by popularity, with recent trends weighted up.
- Tolerate a typo or two.
Non-functional
- 5B searches/day; a typeahead request per keystroke means ~10× that.
- p99 under 50ms end to end, including the network.
- New trending queries appear within minutes, not days.
40:00Commit to an answer before you open the solution. Reading it first teaches you to recognise good answers, which is not the skill being tested.
Stuck?
0 of 3 hints takenThe worked solution
written by a person · not a gradeScore yourself
0 of 5 marked- Computed the request rate and saw it exceeds search itself20
- Precomputed top-k at each trie node rather than ranking at query time30
- A freshness strategy that does not require constant full rebuilds20
- Client-side debounce, cancellation and caching20
- Treated typo tolerance as a separate fallback path10
We run no AI here and nothing on this page grades you. The score is yours, and the useful number is the one you get on the same problem a month from now, cold.
kept in this browser only