You type “ca” into a search box. Before your finger lifts, five suggestions appear: “cat food”, “car rental”, “calendar” and two more. Type “car” and the list changes. It feels free.
Now the interviewer asks: “Design that.” The candidate says: “Find past searches that start with the text, sort by how often they were searched, and return the top five.” Correct. The follow-up: “On every keystroke, for millions of people, in under a tenth of a second. How many rows does the letter ‘c’ match?”
A large share of everything. This lesson fixes that with one idea: do the work before the user types, so each keystroke is a lookup.
- The interview framework and estimation primer.
- Caching strategies, copying and splitting data and design a news feed, because precomputing, copying data and rebuilding it all return here.
Why did the feed keep a ready-made list per reader? Storing the answer was cheaper than computing it each time. Typeahead stores a ready-made list per prefix, for the same reason.
- A short prefix matches too many queries to search and rank on every keystroke, so precompute the top few per prefix.
- A prefix table is small enough to copy to every node, so replicate it and split it only if you must.
- Debounce on the client, ignore stale answers, and cache the few short prefixes at the edge.
- Rebuild the table from query logs and swap it in, with a fast path for trending queries.
- Ranking, typo tolerance and removing bad suggestions are product decisions that need an owner.
Design typeahead end to end in 45 minutes: precompute top suggestions per prefix, serve them quickly with debounce and caches, keep them fresh, and scale the table.
Step 1: Pin Down the Problem#
Ask what is suggested, from what data, and how fresh it must be. Write the answers down. Four questions to ask first, with the answer to assume if the interviewer shrugs:
- Whole past queries, or single words? Whole queries.
- One language or many? Many, so text is normalised.
- The same list for everyone, or personal? The same for everyone.
- Web only, or mobile too? Both, so the API stays small.
Functional requirements:
- As the user types, return up to five suggested completions of the text so far.
- Rank suggestions by popularity, meaning how often people searched for them.
- New popular queries appear in suggestions after a reasonable time.
Out of scope (say it aloud):
- The search results page, spell correction (“did you mean”), ads and personalisation models.
- The editorial policy for harmful suggestions. The mechanism to remove them is in scope.
Non-functional requirements, each with a number. These are assumptions you announce:
- Fast: assume a p99 suggestion round trip of about 100 ms, so the list keeps up with typing. Measure the slow tail, not the average, because every keystroke is a request.
- Available: if suggestions fail, the search box must still work.
- Consistent enough: two users may see different lists for a few minutes. In CAP terms that picks availability, and in the PACELC extension (the trade-off even without a failure) it picks low latency over strong consistency. This is a judgement: no user is hurt by a slightly old list.
- Fresh: the main ranking can be hours old, and a new trending topic should appear within minutes.
- Scale: assume 10 million daily users. Step 4 turns that into numbers.
Step 2: Entities and API#
Query text, count
Prefix text, top5[]
GET /v1/suggest?q=ca
&limit=5&lang=en
-> 200 {"items": [
"cat food", "car rental",
"calendar", ...]}
POST /v1/searches (async)
{"q": "car rental",
"picked": 1}The data is two things: queries with counts, which come from search logs, and prefixes with their top five, which are derived from them. The read path only ever touches the second one.
The contract, in short:
- No pagination. The list is five items; cap
limit(say 10) and capqlength (Elasticsearch’s default is 50 code points). - A safe, cacheable GET. An empty list is
200, not404; bad input is400; overload is429withRetry-After. The client treats any failure as “no suggestions”. - Anonymous by default. Rate limit per IP or session. Sign-in matters only if you personalise.
- Log a search, not a keystroke.
POST /v1/searchesfires once on submit and records which suggestion, if any, was picked. That click is a ranking signal.
Step 3: A Design That Works#
Start with the candidate’s answer. On each keystroke, the server finds all past queries that start with the prefix and sorts them by count.
It works on a small data set, and many candidates stop here.
Assume the log holds 1 billion distinct queries spread evenly across the 26 starting letters. How many does one letter match, and what does that mean per keystroke?
That is 1,000,000,000 ÷ 26 ≈ 38 million matches to sort, on a keystroke with 100 milliseconds. Real text is not evenly spread, so some letters are worse. The cost grows with the data, and the first letters, which everyone types, are the most expensive.
Step 4: Estimate What Matters#
Assume 10M users, 10 searches
a day = 100M searches a day
With debounce (~4 a search):
400M / 86,400 ≈ 4,600/s
peak ≈ 23,000/s
Without: ~12 a search
≈ 13,900/s, peak ≈ 69,000/sThen the data:
Table: 50M prefixes
x 5 suggestions x 30 B
= 7.5 GB
1-3 letter prefixes:
26 + 676 + 17,576 = 18,278
Logs: 100M x 50 B = 5 GB/day
= 1.8 TB/year
Reply ~0.5 KB x 23,000/s
= 11.5 MB/s at peakEach line decides something:
- Debouncing cuts requests about three times at these assumptions, so it is the cheapest capacity you will ever buy.
- At ≈ 23,000 requests a second at peak, the service must answer from memory. A database lookup per keystroke is too slow.
- A table of ≈ 7.5 GB fits in memory on one machine. That decides scaling: copy it, do not split it.
- Call it 18,278 distinct prefixes of one to three letters, yet they take a big share of keystrokes, because everyone types them. That is the case for caching.
- 5 GB of logs a day (assumed 50 bytes a search) makes the rebuild a modest batch job. Keep raw logs briefly (privacy) and counts longer.
- 11.5 MB/s (about 92 Mbit/s) is small: request count is the limit, not bandwidth.
- The 100 ms p99 budget is mostly network: assume 30 to 50 ms to the edge and under 10 ms for the lookup. The lookup is the smallest slice, so the edge cache helps more than a faster trie.
- The 50 million prefixes, 30 bytes a suggestion, 50 bytes a log line and 0.5 KB a reply are assumptions. Measure your own.
Step 5: Deep Dives#
Five questions decide this design. Follow the interviewer’s order, or this one.
How Do You Answer a Prefix Instantly?#
A precomputed answer is a cache you fill ahead of time. The only question is what to store and how to rebuild it.
Find every query with the prefix, then sort by count, as in step 3.
sources.md).Keep queries sorted and read the range that starts with the prefix. In Redis, store words in a sorted set with equal scores and read a lexicographic range with LIMIT, which costs about O(log(N)) for a constant limit. (ZRANGEBYLEX is deprecated since Redis 6.2.0; today you write ZRANGE with BYLEX.) Redis says the result is unspecified if the scores differ.
Store the answer itself. A trie, also called a prefix tree, has a node per prefix, and each node holds its top five completions. A lookup walks one step per letter and reads a ready list.
Real engines ship a compact version. Elasticsearch’s completion suggester uses in-memory data structures that are fast to look up and costly to build, and each suggestion has a ranking weight.
Its source says the values are indexed as a weighted FST, a finite state transducer, and Lucene’s suggester runs a top N search on that weighted FST. Think of it as a trie squeezed to save memory. Redis’s FT.SUGADD stores a string with a score and FT.SUGGET returns completions for a prefix.
How Do the Top-Five Lists Get Built?#
Not by searching from every node. Build from the bottom up, off to the side, never on the read path:
- A node’s top five is the best five among its children’s top-five lists, plus the query that ends at that node, if any.
- Each child must hand up its full top five (or all it has), or a parent can miss a winner.
- One pass from the leaves to the root fills every list.
To save memory, a node can store short ids instead of full text, and the build can drop queries searched fewer than a minimum number of times, which also keeps one-off searches (names, addresses) out of everyone’s suggestions.
What About Typos and Duplicates?#
Two details come up in the room.
-
Typos. Elasticsearch’s completion suggester supports fuzzy queries, so a typo in the prefix can still return results, with a minimum input length before fuzzy matching starts (3 by default). Redis’s
FT.SUGGEThas aFUZZYoption that includes prefixes at edit distance 1. Fuzzy matching costs more, so start it after a few characters. -
Duplicates. Elasticsearch has a
skip_duplicatesoption. In your own table, normalise text first (lowercase, collapse spaces) so “Car Rental” and “car rental” share one count. Other languages need more care than that; the companion lesson covers Unicode.
What Does the Client and the Edge Do?#
Sending a request on every keystroke is an unplanned flood of traffic. Slowing it down at the source is cheaper than limiting it at the server.
Every key press sends a request.
Debouncing waits for a pause. MDN defines it as discarding calls that happen too close together and running once at the end, and names giving suggestions as a typical use. At the assumed 4 requests a search it cuts load about three times.
Answers can arrive out of order, so “ca” may come back after “car”. Tag each request and show only the latest answer. In a browser, an AbortController can cancel the older fetch so it stops using the connection.
Only 18,278 prefixes have one to three letters, and everyone types them, so put them in an edge cache. A response with Cache-Control: max-age=N stays fresh for N seconds, and stale-while-revalidate lets a cache serve a stale answer while it refreshes in the background, hiding the refresh delay.
MDN also warns that a shared cache reuses one response for many users, so never cache personalised suggestions there. For personalisation, fetch the shared top suggestions and re-rank them per user behind the edge, with Cache-Control: private.
How Do You Keep Suggestions Fresh?#
A precomputed list goes stale, like a feed list. You choose between rebuilding it and patching it, and usually do both.
A batch job counts the last period’s searches, builds a new table, and replaces the old one.
All-time counts keep last year’s big story on top forever. Shrink old counts by a fixed factor at each rebuild so old spikes fade.
How do the counts reach the rebuild? Every submitted search goes to a durable log (a message queue), and a job counts it. This is judgement, not a benchmark:
| Path | How | Delay | Cost |
|---|---|---|---|
| Batch | Count a window of logs, rebuild all prefixes | Hours | Cheap, exact, easy to re-run |
| Stream | Count per minute in a stream processor, keep the top few rising queries | Minutes | More moving parts, approximate |
Run both: batch for the main table, stream for trending. Before counting, drop bots and repeats (one client repeating a query counts once), or anyone can push a query into everyone’s suggestions.
Rebuild every hour or so, off to the side, then switch readers to the new table in one step.
Keep a small, short-lived list of recently rising queries, updated within minutes, and merge it with the table at answer time. Redis’s suggestion dictionary supports this style: FT.SUGADD has an INCR option that adds to an existing score instead of replacing it, which the docs call useful for real-time updates from user queries. Elasticsearch’s completion suggestions are near real-time: new ones become visible after a refresh, and deleted documents are never shown.
How Do You Scale the Table?#
Splitting data across machines costs routing and failure handling. Copying it costs only memory, if it fits.
One machine holds the table and answers every request.
At the assumed 7.5 GB, each node can hold the full table in memory. Any node can answer any prefix, so no routing is needed, and adding load means adding a replica. Elasticsearch agrees: a completion query over several shards runs in two phases, so a single shard is more performant.
When the table outgrows a node, split it, called sharding, by the first letters of the prefix, for example a to f on one shard and g to m on another, and keep replicas of each shard.
Do not split by whole query: the prefixes of one query would land on different shards. Watch for hot prefixes: split busy ranges finer, merge quiet letters, and give hot shards more replicas. A hash of the prefix spreads load more evenly; letter ranges let each shard build its own part of the trie. The same docs note that when heap use is high, splitting is still recommended over squeezing one shard.
Precompute the top five per prefix, cache the short prefixes, and rebuild then swap. Debounce the typing, replicate before you split, and keep a fast path for what is new.
The Final Design in One Picture#
Follow one keystroke and one new trend:
- The user types “ca”, pauses, and one request goes out; stale answers are ignored.
- The edge cache holds short prefixes and answers at once. A longer prefix reaches a node, which reads the top five from memory and merges trending entries.
- The submitted search is logged. The fast path updates trending counts within minutes, and every hour a batch job rebuilds the table and swaps it in everywhere.
- A harmful suggestion is removed from the table and cache directly, not at the next rebuild.
What Is Left for the Companion Lesson#
The core answer ends here. The rest is the production depth that senior rounds probe, and it lives in Design a Typeahead Search: Failure Modes, Security and Follow-Ups (2026).
| Probe | Where it goes deeper |
|---|---|
| A node, the cache or the rebuild dies | Failure table, four signals to watch, alert rules, canary rollout, cost |
| Who ranks, who blocks, who abuses | Ranking signals, layered blocking, abuse and log privacy |
| Other languages, screen readers, other regions | Unicode, the combobox pattern, multi-region copies, follow-up answers, the 45-minute plan |
What Each Level Should Show#
| Level | Expected in the room |
|---|---|
| Mid-level | A query on every keystroke, a trie or index, some caching, a clear API. Needs a hint about ranking and scale. |
| Senior | Top-k stored per prefix and built bottom up, numbers that drive choices, debounce, edge cache for short prefixes, a rebuild with a swap, replicate the table, failure modes. |
| Staff+ | Trending fast path, time decay, removal of bad suggestions, dropping rare queries for privacy, fuzzy matching and Unicode, abuse and privacy, split by prefix and hot prefixes, multi-region, alerting and rollout, rebuild cost, and what to build first. |
Red Flags and Green Flags#
“Store the queries in a database with an index on the text, and run LIKE ‘prefix%’ ORDER BY count LIMIT 5.” Nothing about short prefixes, request volume or stale data.
“One letter matches a huge share of queries, so I’ll precompute the top five per prefix in memory, debounce on the client, cache the short prefixes at the edge, and rebuild from logs with a fast path for trending queries.”
Drawing a trie and stopping. The interviewer is waiting for how it is built, how it stays fresh, and why one letter does not melt the service.
Try It: A Table Ten Times Bigger#
Change one variable. Assume the table grows to 100 million prefixes, still 5 suggestions of about 30 bytes each, and your service nodes have 64 GB of memory.
- How big is the table?
- Do you replicate or split?
- What gets harder?
Hint
Multiply prefixes by suggestions by bytes, then compare with node memory, and think about what a rebuild has to do.
One reasonable answer
100,000,000 x 5 x 30 B
= 15,000,000,000 B
= 15 GB per copy15 GB fits in a 64 GB node with room left, so keep replicating the whole table: no routing, and any node answers any prefix. Splitting can wait.
What gets harder is the rebuild: 15 GB must be built, checked and pushed to every node before the swap. Watch rebuild time and the cost of every replica.
Expect the follow-ups in this order: “How do you make each keystroke fast?”, “How do you keep it from sending too many requests?”, “How do new trending queries show up?”, and “What if the table is too big for one machine?” Close each answer with a trade-off and a number.
If you are short on time, cut the scaling dive, not the failure modes. The companion lesson has a minute-by-minute plan.
Check Yourself#
1.Why not search the query log on every keystroke?
A short prefix matches a huge share of all queries, so finding and ranking them takes too long for a 100 ms budget. Precomputing the top few suggestions per prefix makes each request a lookup.
2.Node ca has children cab, caf and car. How do you fill its top five without scanning every query under ca?
Merge the children’s top-five lists, add the query “ca” itself if people searched it, and keep the best five. Do it bottom up in one pass, so every child’s list is ready before its parent needs it.
3.A harmful suggestion is reported. Why can it not wait for the next rebuild?
The table is rebuilt only every so often, so the suggestion would keep appearing until then. Remove it from the table and the caches directly. Elasticsearch’s completion suggester never shows deleted documents, which is the behaviour to copy.
In One Picture#
Requirements
top 5 per keystroke, fresh
Scale
≈ 23,000 req/s · 7.5 GB table
Answer
precomputed top 5 per prefix
Client
debounce, latest wins
Edge
cache 1-3 letter prefixes
Fresh
rebuild + swap, trending path
Rule
replicate first, split lastConclusion#
Typeahead is a precomputation problem wearing a search box. Store the top few suggestions for every prefix, keep them in memory on every node, debounce and cache the short prefixes, and rebuild from logs with a fast path for what is new. The same trade, answers stored ahead of time for memory and rebuild work, appears in the feed and cache problems before it.
Where would you start in an interview: the stored top five, the debounce or the rebuild? Tell us in the comments.
- Precomputed lists: design a news feed and caching strategies.
- Copying versus splitting data: the lesson on splitting and copying data.
- Production depth: failure modes, security and follow-ups.
- Next in Module 4: a video streaming service, where big files must play smoothly for millions of viewers.
