Design Interviews · lesson 12 of 15 · about 28 min
Search suggestions end to end: the load every keystroke creates, how a prefix tree answers in a few steps, how new trends surface, how clients cut requests, what typo tolerance costs, and how suggestions get manipulated. Tap any for a plain-language card.
Fast enough to keep up with typing
That makes it a read-heavy, latency-critical service built from pre-computed data: suggestions are computed offline from query logs and served from memory. The write path (aggregating logs into popularity counts) is entirely separate from the read path (looking up a prefix). Size the read side first.
500 million users making 8 searches a day, each triggering 4 prefix requests, is 46,000 searches and 185,000 suggestion requests a second, 556,000 at a 3× peak, each with a budget of about 100 ms.
500 million users at 8 searches a day with 4 suggestion requests each is 185K requests a second (556K at peak), every one needing an answer within 100 ms. That rules out computing suggestions per request: they must be precomputed and served from memory.
Arithmetic. The number of requests per search depends on the client (see debouncing later), and the typical gap between keystrokes is a couple of hundred milliseconds.
Walk down the letters
The fix is to precompute the top-k completions at every node, so serving a prefix is just walking its length and reading a ready-made list: O(length), independent of how many queries start with it. The cost is memory (k entries on every node, which is acceptable) and the work of keeping the lists current, done offline when the trie is rebuilt. The numbers below come from a real trie built over a synthetic Zipf-popular query log.
For the one-letter prefix the subtree beneath it holds about 7,700 nodes on average (weighted by how often such prefixes occur); reading a precomputed list takes 1 step. At 4 letters the subtree is 44 nodes.
After 2 letters the average subtree has 425 nodes to search; with the top-5 list stored at each node the answer is 2 steps, 213× less work. The trie of 15,741 queries has 81,822 nodes; the lists cost about 2.5× the trie's memory.
Real trie of a seeded synthetic log (about 16,000 distinct queries, Zipf popularity). Subtree sizes are weighted by how often each prefix is typed. Memory assumes 24 B per node and 12 B per stored suggestion; production tries are compressed (radix trees, FSTs).
An earthquake happens and nobody can find it
Batch rebuilds every few hours are simple and cheap; streaming counts (events aggregated in near real time into a small overlay of fresh trending queries merged at serve time) cut the delay to minutes. Most systems combine both: a big stable trie rebuilt daily and a small hot overlay updated continuously. Try the numbers.
A phrase at 100 searches a minute doubling every 30 minutes passes a 5,000-a-minute cut-off after about 169 minutes. With a 60-minute batch refresh it appears about 199 minutes in on average.
A phrase starting at 100/min and doubling every 30 min passes 5,000/min after 2.8 h. With rebuilds every 60 min, users see it about 3.3 h after the event starts (worst case 3.8 h). A streaming overlay removes the refresh term.
Exponential growth: time to cross = doubling time × log2(cut-off ÷ start rate). A batch rebuild adds on average half its interval.
Do not ask on every letter
Other client-side savings stack on top: cache results in memory for the session (backspacing returns to a prefix already fetched, with no request), prefetch nothing for one-letter prefixes (they are useless and expensive), and cap the minimum prefix length. The trade-off is a delay in showing suggestions, so the debounce must stay below the perceptual threshold. Simulated below with log-normally distributed gaps between keys.
With a median 200 ms between keys, a 10-character query sends 10 requests with no debounce and 3.3 with a 300 ms debounce: 67% fewer. A 500 ms debounce sends 1.6, but suggestions feel sluggish.
A 10-character query typed with a median 200 ms between keys sends 3.3 requests with a 300 ms debounce instead of 10: 67% fewer, taking the server from 460K to 151K requests a second.
Seeded Monte Carlo of 4,000 queries with log-normal key gaps. A request is sent after every pause at least as long as the debounce, including the final one.
“resturant”
Practical systems avoid brute force: walk the trie while tracking an edit-distance table and prune branches that already exceed the limit; or precompute a small dictionary of common misspellings and corrections from logs (“people who typed this clicked that”); or index n-grams. They also keep fuzzy matching as a fallback only when the exact prefix returns too few results, and rank exact matches first. Try the prefix length.
A 6-letter prefix has 344 strings within one typo (6 deletions, 150 substitutions, 182 insertions, 5 swaps, plus the original). A 10-letter prefix has 556.
A 6-letter prefix has 344 variants within one edit, so brute-force fuzzy matching makes 344 trie lookups for every keystroke instead of one. Pruned trie walks, correction tables and exact-first ranking avoid that.
Counts for a 26-letter alphabet: deletions L, substitutions 25L, insertions 26(L + 1), adjacent swaps L − 1, plus the original.
Pick the technique
Each problem has one technique that fits best. Each answer is worth 20 XP.
Match the symptom: slow prefix lookups, request flood, late trends, or manipulation?
Serving the prefix 'a' means scanning and sorting millions of queries beneath it.
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
Public facts about autocomplete systems.
predictions from search activity
Google describes its autocomplete predictions as reflecting real search activity and how it removes predictions that violate its policies, such as those that are hateful or sexually explicit, an acknowledgement that raw popularity must be filtered.
finite-state transducers
The Lucene search library, which underlies Elasticsearch, can store a dictionary of suggestions as a finite-state transducer, a compressed automaton held in memory that looks up prefixes extremely quickly in a fraction of a trie's space.
lexicographic range queries
A well-known Redis pattern uses a sorted set where all members have equal scores and lexicographic range commands to retrieve the entries that begin with a prefix, a quick way to build small autocomplete features.
typo-tolerant instant search
Algolia and similar hosted search services pitch instant results on every keystroke with typo tolerance, showing that the debounce, prefix-index and fuzzy-matching ideas in this lesson are sold as a product.
Interview angle
Six questions, each worth 20 XP. Strong answers explain how the latency budget is met and how abuse is handled.
Say where suggestions are computed, how fresh they are, and how requests and abuse are limited.
Why must typeahead answers come from precomputed data?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
Defences raise the attacker's price. Count unique users (accounts, devices, IPs) rather than raw queries, and cap how much any one counts (1 query per user per day is typical); require a minimum number of distinct users before a phrase can appear; filter against blocklists and classifiers for abuse, hate and personal data; keep a human-review path and a fast takedown; and reduce reliance on the last hours of raw counts for sensitive prefixes. Compare how many identities an attacker needs.
A phrase needs 20,000 queries in the window to reach the top five. If one user can count 1,000 times, the attacker needs just 20 accounts. Capped at 1 count per user per day, 20,000 distinct users are needed.
To reach the top suggestions an attacker needs 20,000 queries. With each user counting at most 1,000 times and at least 1 distinct users required, that means 20 fake identities. That is trivially cheap: tighten the per-user cap.
Arithmetic: identities = max(needed queries ÷ per-user cap, minimum distinct users). It makes manipulation costlier, not impossible; moderation and fast takedown still matter.
Where to go next