# Design a Typeahead Search: Precompute the Top Five (2026)
> Typeahead looks like a prefix search and is really a precomputation problem: the answer for each prefix must already be waiting. The prompt, the numbers, a prefix table with the top five per prefix, caching and debounce, and keeping suggestions fresh.
*Source: https://www.infowok.com/design-a-typeahead-search/ · Sukhveer Kaur · Published October 24, 2026*
---
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](/system-design-interview-framework-2026/) and [estimation primer](/back-of-envelope-estimation-primer/).
- [Caching strategies](/caching-strategies/), [copying and splitting data](/database-sharding-and-replication-explained/) and [design a news feed](/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:**
1. As the user types, return up to five suggested completions of the text so far.
2. Rank suggestions by popularity, meaning how often people searched for them.
3. 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](/cap-theorem-explained/) 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
```text
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 cap `q` length (Elasticsearch's default is [50 code points](https://github.com/elastic/elasticsearch/blob/main/docs/reference/elasticsearch/rest-apis/search-suggesters.md)).
- **A safe, cacheable GET.** An empty list is `200`, not `404`; bad input is `400`; overload is `429` with `Retry-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/searches` fires 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
```text
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/s
```
Then the data:
```text
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 peak
```
Each 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.
Cost grows with the data, and the shortest prefixes are the slowest. A toy test with 200,000 random queries scanned ≈ 7,700 for one letter, ≈ 297 for two, and ≈ 12 for three (see `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`](https://github.com/redis/docs/blob/main/content/commands/zrangebylex.md), 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.
This finds the range quickly but returns it in alphabetical order, not popularity order. "Cabbage" would beat "car rental". To rank by popularity you need something more.
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](https://github.com/elastic/elasticsearch/blob/main/docs/reference/elasticsearch/rest-apis/search-suggesters.md) 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](https://github.com/elastic/elasticsearch/blob/main/server/src/main/java/org/elasticsearch/index/mapper/CompletionFieldMapper.java), a finite state transducer, and Lucene's suggester runs a [top N search on that weighted FST](https://lucene.apache.org/core/10_5_2/suggest/org/apache/lucene/search/suggest/document/NRTSuggester.html). 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](https://github.com/redis/docs/blob/main/content/commands/ft.sugget.md).
Memory and build time. In the toy test, 200,000 random queries produced ≈ 982,000 stored prefixes, about 4.9 per query. Real text shares more prefixes, but the table is still far larger than the query list.
#### 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:
1. 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.
2. Each child must hand up its full top five (or all it has), or a parent can miss a winner.
3. 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](https://github.com/elastic/elasticsearch/blob/main/docs/reference/elasticsearch/rest-apis/search-suggesters.md), with a minimum input length before fuzzy matching starts (3 by default). Redis's `FT.SUGGET` has a `FUZZY` option that includes prefixes at edit distance 1. Fuzzy matching costs more, so start it after a few characters.
- **Duplicates.** Elasticsearch has a `skip_duplicates` option. 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.
About 12 requests per search at the assumed length, so ≈ 13,900 a second on average and ≈ 69,000 at peak, and most of the answers are for text the user already typed past.
Debouncing waits for a pause. MDN defines it as discarding calls that [happen too close together and running once at the end](https://github.com/mdn/content/blob/main/files/en-us/glossary/debounce/index.md), 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](https://github.com/mdn/content/blob/main/files/en-us/web/api/abortcontroller/index.md) so it stops using the connection.
A short delay before the list appears. Pick a pause short enough that it feels instant, and test it with real typists.
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](https://github.com/mdn/content/blob/main/files/en-us/web/http/reference/headers/cache-control/index.md), 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`.
A cached answer can be a few minutes old, so a very fresh trending query reaches long prefixes first. Keep the cache time short.
### 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.
Simple and consistent, but a topic that trends at breakfast waits until tomorrow.
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.
Rebuild cost grows with the data, and a half-built table must never be served. Keep the old one until the new one is checked; if a build fails, keep serving the last good one.
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](https://github.com/redis/docs/blob/main/content/commands/ft.sugadd.md), which the docs call useful for real-time updates from user queries. Elasticsearch's completion suggestions are [near real-time](https://github.com/elastic/elasticsearch/blob/main/docs/reference/elasticsearch/rest-apis/search-suggesters.md): new ones become visible after a refresh, and deleted documents are never shown.
Two sources to merge and explain. The second half of that Elasticsearch point is the one to remember: a harmful suggestion must be removable at once, not at the next rebuild.
### 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.
It must carry ≈ 23,000 requests a second at peak and it is a single point of failure.
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](https://github.com/elastic/elasticsearch/blob/main/docs/reference/elasticsearch/rest-apis/search-suggesters.md).
Every node pays the full memory cost, and a rebuild must reach all of them. That is fine at gigabytes and a problem at hundreds of gigabytes.
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.
Routing by prefix, uneven shards, and a rebuild that must write to the right places. Replicate first and split last.
**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:
1. The user types "ca", pauses, and one request goes out; stale answers are ignored.
2. 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.
3. 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.
4. 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)](/design-a-typeahead-search-follow-ups/).
| 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.
1. How big is the table?
2. Do you replicate or split?
3. What gets harder?
Multiply prefixes by suggestions by bytes, then compare with node memory, and think about what a rebuild has to do.
```text
100,000,000 x 5 x 30 B
= 15,000,000,000 B
= 15 GB per copy
```
15 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
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.
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.
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
```text
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 last
```
## Conclusion
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](/design-a-news-feed/) and [caching strategies](/caching-strategies/).
- **Copying versus splitting data:** the [lesson on splitting and copying data](/database-sharding-and-replication-explained/).
- **Production depth:** [failure modes, security and follow-ups](/design-a-typeahead-search-follow-ups/).
- **Next in Module 4:** [a video streaming service](/design-a-video-streaming-service/), where big files must play smoothly for millions of viewers.