In this article
Before you start
This page is part of the machine learning (ML) system design guide, which covers the framework interviewers expect: requirements, data, model or ranking, serving and evaluation.
Why interviewers ask this
Typeahead looks simple, so it is a good probe of whether a candidate can turn a vague product feature into numbers. The interviewer wants to hear the read-path latency target, the scale in requests per second, where the ranking work happens, and how fresh the suggestions must be. It appears in system design screens as "design a search autocomplete", "design a typeahead", or as a part of a larger search or e-commerce question.
A weak answer says "use a trie" and stops. A strong answer says what is stored at each node, who builds it and when, how the numbers change at peak load, and which parts are cached or sharded.
Autocomplete system design from first principles
In plain words
- Query autocomplete
- Query autocomplete is a feature that proposes ways to extend the characters a user has typed into a full search query, as defined in the survey of Cai and de Rijke (2016); it is also called typeahead.
- Top-k list
- A top-k list is the k highest-ranked completions of a prefix, stored at the trie node for that prefix so that a lookup reads the list instead of searching below the node.
- Debouncing
- Debouncing is a client-side rule that sends a request only after the user has paused typing for a short time, which cuts the number of requests per search.
Think of a librarian who already knows, for every opening of a title, the three books people ask for most. She has written them on index cards, one card per opening. When you say "hel", the librarian does not search the shelves. She reads the answer off a card filed under "hel". The analogy breaks in one place. A librarian's cards stay valid for years, while search interest moves daily, so the cards must be rewritten regularly, and a card for a very common opening must be easy to find.
In one precise sentence, an autocomplete service maps a prefix to a short ranked list that was computed before the request arrived.
Step 1: Define the contract
The contract is a prefix in and a short ranked list out, with a latency target and a freshness target. Write both down before drawing boxes. An illustrative budget is a response in well under 200 milliseconds from the user's point of view, because suggestions must keep up with typing, and a list of about five to ten items. Freshness is a separate number: whether a news event should appear in minutes, hours or the next day.
Two facts frame the problem. Google says its predictions come from common and trending queries that match what someone starts to type, shaped by language, location, trending interest and, if signed in, past searches (Google Search Help). And the Cai and de Rijke survey groups ranking approaches into heuristic models and learning to rank.
The input is a product requirement. The output is a latency target, a freshness target, a list size and a ranking signal.
Step 2: Store the top few completions at every trie node
Each trie node holds a precomputed top-k list, so a lookup walks one node per typed character and reads the list, with no search of the subtree. Without the stored lists, finding the best completions of "he" means visiting every query below that node, and that cost grows with the number of queries. With them, the cost is the prefix length, which is a handful of steps. The top-k list at the node is built in advance in a batch job.
On a toy set of ten illustrative queries with counts, the trie has 28 nodes including the root. The prefix "hel" returns help, hello and helmet, and "wo" returns world, work and word, each read straight from the node1. A prefix with no match, such as "x", returns an empty list.
Step-by-step description
- A prefix goes in, a short list comes out.
- Walk one node per character.
- The best results are precomputed.
- Cache, filter and return.
- The lookup walks one trie node per typed character.
- The top-k list at the node is built in advance in a batch job.
The cost is memory, because every node stores k entries. The next worked example sizes it.
Step 3: Build the lists in a batch job from query logs
A batch job reads the query logs, aggregates a score per query, and fills each node's list with its k best queries. Doing this outside the request path is what keeps reads cheap. It runs on a schedule, with a fast path for trending queries, as the batch versus streaming comparison describes.
The score needs thought, because a raw count favours old, steady queries. Recency decay is a weighting that shrinks a count the older it is, so recent activity dominates; in this illustrative example each day of age halves it (a half-life of one day).
In an illustrative week, a steady query with 1,000 searches a day has a raw total of 7,000 and a decayed score of about 1,984, while a surging query that jumped to 1,200 and then 3,000 on the last two days has a raw total of 4,200 and a decayed score of 3,600. Decay puts the surging one first1. Google says rising interest can produce a trending prediction even when it is not the most common one (Google blog, 2020).
Step 4: Serve, cache and filter
At serving time a request hits a cache first, then the trie shard that owns the prefix, and the result passes a filter before returning. Popular short prefixes repeat constantly, so a cache absorbs a large share of the traffic, and the client's debouncing cuts requests further. The filter removes suggestions that must not be shown: Google says its systems try to block predictions that are violent, sexually explicit, hateful, disparaging or dangerous, and may suppress ones unlikely to lead to reliable content.
To scale out, split the trie by the first characters of the prefix and replicate each shard. Elasticsearch's completion suggester is a managed version of this idea: it is optimised for speed, held in memory, with a weight per suggestion for ranking, and its reference notes that a single-shard index performs better because multi-shard queries run in two phases.
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →Worked example
A toy trie shows the lookup, and the dictionary and request-rate figures show the cost. The inputs are illustrative, so each number carries the script that produced it1.
| Prefix typed | Completions read from the node | Trie steps |
|---|---|---|
| h | help, hello, helmet | 1 |
| hel | help, hello, helmet | 3 |
| wo | world, work, word | 2 |
| we | weather, web | 2 |
| x | none | 1 |
Prefix sharing decides the memory. Using the 234,454 distinct lower-case words of the dictionary file on the machine that ran the script as a stand-in for queries, the 2,248,642 characters collapse into 758,880 trie nodes including the root, about three characters per node. If each node stored five completion ids of four bytes each, the lists would need about 15.2 MB. Real query logs differ, so treat these as an illustration of the method, not a forecast1.
Text description of the diagram
- The steady query has a raw total of 7,000 and a decayed score of 1,984.
- The surging query has a raw total of 4,200 and a decayed score of 3,600.
| Quantity | Value |
|---|---|
| Daily active users (illustrative) | 50,000,000 |
| Searches per user per day (illustrative) | 8 |
| Requests per search after debouncing (illustrative) | 3 |
| Requests per day | 1,200,000,000 |
| Average requests per second | 13,889 |
| Peak requests per second at a factor of 3 | 41,667 |
The average is the requests per day divided by 86,400 seconds in a day. The peak factor of 3 is an assumption to state out loud and revise with real traffic1. Each cache hit removes a request from the shards, so the cache hit rate is the lever on this number.
Trade-offs and edge cases
The design trades memory and freshness for lookup speed. A trie with a top-k list per node has the fastest reads and the largest memory, a sorted list of queries is smallest but must search and scan a range, and a search engine suggester gives near-real-time updates at the cost of keeping its index in memory.
Text description of the diagram
- A trie lookup costs the length of the prefix.
- The Elasticsearch completion index is held in memory.
Freshness is the main tension. A nightly batch leaves breaking news out for a day, so teams add a fast path for trending queries and merge it with the batch lists. Personalisation is another layer: Google lists past searches among its signals when a user is signed in, which means the final ranking mixes a global list with a user-specific one. This is related to the problem of ranking with little history discussed on the cold start page.
Quality has edge cases that interviewers like. Typos can be handled with fuzzy matching, which the Elasticsearch suggester supports. Very rare queries should be kept out of the lists by a minimum count, a design choice that also limits exposure of private text. Safety filters must run on the stored lists and not only on the logs. Current practice goes beyond the trie.
Everaert et al. (AmazonQAC, Empirical Methods in Natural Language Processing 2024, arXiv 2411.04129v1, submitted 22 October 2024) built a 395M-sample dataset from Amazon Search logs and compared prefix trees, semantic retrieval and large language models with and without that extra training; they report that models trained further on the task did best, especially with session context, yet the best system reached only half of the theoretical maximum they calculate on their test data (arXiv).
In practice a learned ranker re-ranks the trie's candidates inside the latency budget, so the trie stays the fast first stage. And the ranking itself may be learned: the survey notes learning-to-rank as one of two main approaches, with time-sensitive and user-specific signals as the main trends.
When the question is about a catalogue, such as e-commerce, the same pipeline can surface filters or categories next to queries, and exact-prefix lookup can sit alongside the hybrid search backend that serves results.
How to answer it in an interview
Design a typeahead for a search box.
I would fix the contract first: a prefix in, the top five completions out, under about 200 milliseconds end to end. I store queries in a trie with a precomputed top-five list at every node, so a lookup walks one node per character. A batch job builds the lists from logs, ranked by decayed counts so trending queries rise, and a fast path adds breaking ones. Requests hit a cache, then the shard that owns the prefix, then a safety filter, and the client debounces keystrokes. Memory is the cost, so I would shard by prefix.
The spoken structure is: contract, data structure, build and ranking, serving path, then the cost.
Common mistakes
- "I would search all queries that start with the prefix" (wrong). That cost grows with the number of queries (right: precompute the top-k list at each node so a lookup costs the prefix length).
- "Rank by total count" (wrong). Old queries then beat trending ones (right: decay the counts or add a trending signal).
- "Update the trie on every search" (wrong). Writes at that rate contend with reads (right: aggregate in a batch job and swap in new lists).
- "Skip the filter because the logs are clean" (wrong). Policy-violating text can still be a frequent query, and Google says it blocks such predictions (right: filter at build and at serve).
- "One server holds everything" (wrong). The peak in our example is about 41,667 requests per second (right: replicate the servers and cache the hot short prefixes for the request rate; shard by prefix when the lists outgrow one machine's memory).
Follow-up questions
Design a solution for dynamically displaying filters based on the searched product?
Reuse the pipeline with a different payload. For each query, count how often each attribute value appears among the products people clicked or bought, and store the highest-share attributes as the filter list for that query. Fall back to category-level defaults for new queries, as in a cold start, and refresh on a schedule.
How would you design an auto-complete feature that shows job postings in the user's city based on their previous searches?
Key the stored lists by prefix and city, so the node for "eng" in one city holds that city's top postings and queries. Build them in the batch job from logs grouped by city, and mix in a short list from the user's own recent searches at serving time. Fall back to the global list for cities with too little data.
How would you build a search suggestion system?
State the contract (prefix in, top five out, latency target), then the trie with a precomputed top-k list per node, the batch job with decayed counts, and the serving path of cache, shard and filter. Close with the cost: memory.
Why store the top results at every node instead of searching below it?
Because the subtree can hold a very large number of queries, and a search of it makes the lookup cost grow with the corpus. Storing k entries per node makes lookup cost equal the prefix length, and memory the price.
How do you keep suggestions fresh?
Run a batch job on a schedule and a faster path for trending queries, then merge them at serving time. The Elasticsearch reference notes its suggestions are near real time, which shows what a managed option offers.
What changes if traffic grows ten times?
The illustrative peak of 41,667 requests per second becomes about 416,670. Add replicas and a larger cache for the hot short prefixes first, since throughput is a replica question; shard by prefix only if the lists outgrow one machine's memory, partitioning by the first one or two characters and balancing by traffic, since some letters are far more common1.
- Autocomplete system design maps a prefix to a short ranked list computed before the request arrives.
- A trie with a top-k list per node makes lookup cost equal the prefix length; memory is the price.
- Build the lists in a batch job, rank by decayed counts, and add a fast path for trending queries.
- Serve through a cache, a prefix-sharded trie and a safety filter, with debouncing on the client.
- State your assumptions: in our illustrative case 50 million users give about 13,889 requests per second on average and 41,667 at peak.
Sources
- How Google autocomplete predictions work (Search Help; undated page, read 2026-10-24) — Google Search Help, 24 Oct 2026
- How Google autocomplete predictions work (Google blog, Danny Sullivan) — Google, 8 Oct 2020
- Suggesters: the completion suggester, Elasticsearch reference (page shows no version; read 2026-10-24) — Elastic, 24 Oct 2026
- AmazonQAC: A Large-Scale, Naturalistic Query Autocomplete Dataset (Everaert et al., EMNLP 2024; arXiv 2411.04129v1) — arXiv, 22 Oct 2024
- A Survey of Query Auto Completion in Information Retrieval (Foundations and Trends in Information Retrieval 10(4)) — Cai and de Rijke (year 2016; month approximate), 1 Sep 2016
