Design Search Autocomplete (Typeahead)

Autocomplete suggests completions as a user types into a search box. It looks small, and it is a demanding system: it is called on almost every keystroke, it must answer in a few tens of milliseconds, and the quality of its suggestions depends on data that changes all day. It is a good interview problem because it has a clean core idea, a data structure with a trade-off, and a split between an offline data pipeline and an online serving path.

The chapter follows the usual shape: understand the problem, set up the interface, build the high-level design, then go deep on the questions interviewers use to separate levels.

1. Understanding the problem

As the user types a prefix such as "ca", the system returns a short list of likely completions, such as "car insurance", "cat videos" and "cake recipe", ordered by how useful they are expected to be.

Functional requirements

Core:

1. Given a prefix, return the top suggestions, typically five to ten.
2. Suggestions are ranked, mainly by popularity.
3. Suggestions improve over time as people search, and new popular queries appear.

Confirm in or out: personalisation, spell correction, multiple languages, filtering offensive or sensitive suggestions, and geography. A sensible opening: "I will design global popularity-based suggestions with a freshness pipeline and a safety filter, and treat personalisation and spell correction as extensions."

Non-functional requirements

• Very low latency. Suggestions must appear as the user types, so the target is well under 100 milliseconds end to end, and the server work should take only a few milliseconds.
• High availability. The search box must always feel responsive, and a missing suggestion list is better than a slow one.
• Scale. A large search product handles billions of searches per day.
• Eventual consistency is fine. A new trend can take minutes to appear in suggestions.
• Relevance and safety. Suggestions must be useful and must not surface harmful content.

Estimation

Assume 1 billion searches a day, and an average of four typeahead requests per search, since the client usually waits for a pause before querying.

What the numbers say. The read rate is high, and each response is tiny. The dataset is large but bounded and read-mostly. This is the profile of a system you serve entirely from memory, with the heavy work done ahead of time.

2. The set up

Core entities

• Query: the full search string, with a popularity score.
• Prefix: every leading substring of a query.
• Suggestion list: the top completions for one prefix.

API

GET /v1/suggest?q=ca&limit=5
-> { "prefix": "ca", "suggestions": ["car insurance", "cat videos", "cake recipe", ...] }

Mention that the response is highly cacheable: the same prefix gives the same answer for everyone for a few minutes.

3. High-level design

The system splits cleanly into two parts with different needs.

Online serving. Given a prefix, look up the precomputed list of suggestions in memory and return it. There is no ranking or computation at request time.

Offline and near-real-time building. Search logs flow into an aggregator that counts how often each query is searched, weighting recent searches more heavily. A builder turns those counts into the data structure that serves, and publishes it as a versioned snapshot that the serving fleet loads.

The separation is the heart of the design: the part that must be fast does almost no work, and the part that does heavy work is not on the critical path.

The data structure: a trie with precomputed top-k

A trie (prefix tree) stores strings by their shared prefixes, one character per edge. Each node corresponds to a prefix. A lookup walks one edge per character of the prefix, which costs $O(L)$ for a prefix of length $L$ and does not depend on the number of stored queries.

The naive approach stores only the queries at the ends of paths and, to answer a prefix, collects all queries under that node and sorts them. That may mean scanning millions of descendants for a short prefix like "a", far too slow.

The fix is to store the top-k suggestions at every node. The ranking work is done once, at build time.

The lookup becomes: walk the prefix, then read the list stored on that node. The cost is extra memory for the lists, a worthwhile trade for constant-time answers.

4. Potential deep dives

Deep dive 1: How do you compute the top suggestions efficiently?

The challenge. For every prefix, you need the best few completions out of possibly millions of queries beneath it.

Weak: compute at request time. Walk to the node, gather every query below it and sort by popularity. For short prefixes this touches an enormous number of strings and cannot meet the latency target at 100,000 requests per second.

Solid: precompute top-k per node. Build the trie from query counts. At each node, keep the $k$ highest-scoring queries in its subtree. Build bottom-up: a node's list is the merge of its children's lists and the query ending at the node, truncated to $k$. Requests then read a stored list.

Excellent: precompute, and keep memory under control. Storing a list at every node can be large. Reduce the memory with several techniques:

• Store identifiers or pointers to shared query strings in the lists, not copies of the strings.
• Compress the trie by merging single-child chains into one edge, a radix tree.
• Cap the depth. Suggestions rarely need prefixes beyond a certain length, and long prefixes match few queries.
• Prune rare queries. Drop queries below a count threshold, since they would never reach a top-k list anyway.
• Alternatively, store a map from prefix to top-k list in a key-value store, one entry per prefix, which is simple to shard and cache, at the cost of repeating shared structure.

State the trade-off: a trie is compact and elegant, a precomputed prefix map is easier to distribute, and either serves the same fast answer.

Deep dive 2: How do you keep suggestions fresh?

The challenge. A sudden event makes a new query popular within minutes, and suggestions should reflect it soon without a full rebuild.

Weak: rebuild the whole structure once a day. Trending queries show up a day late, and old ones linger.

Solid: rebuild frequently and swap in the new version. Run the aggregation and build every few minutes or hours, publish a new versioned snapshot, and have the serving fleet load it and switch over atomically. Keep the old version for rollback.

Excellent: batch plus a fast layer for trends, with time decay. Run the heavy batch build for the stable bulk of queries, and add a streaming layer that tracks counts over short windows to detect rising queries, merging its results into the served data. Weight recent searches more by using time-decayed counts, for example an exponentially weighted count, so old popularity fades. Handle the cold start problem for brand-new queries with a minimum-evidence threshold that keeps one-off noise out. Always load a new snapshot completely, verify it, and then switch, so a half-built structure is never served.

Deep dive 3: How do you serve at 100,000 requests per second with low latency?

The challenge. Every keystroke is a request, and users expect instant feedback.

Weak: a central database queried per request. Network round trips and database load make the target unreachable.

Solid: in-memory serving and a cache. Load the precomputed data into the memory of the suggest servers, so a request is a memory lookup. Put a cache in front, since the same popular prefixes are asked constantly.

Excellent: layered caching and sharding, with client-side restraint. Layer the defences:

1. Client side: wait for a short pause (debounce) before sending, cancel outdated requests, and cache recent prefixes in the browser. A user typing "weather" quickly needs one answer, not seven. Also reuse earlier results: the answers for "wea" can often answer "weat" if the list is long enough.
2. CDN or edge cache for popular short prefixes, with a short time to live.
3. Suggest servers holding the data in memory.

If the data is too large for one machine, shard by prefix so that each server holds a range of prefixes, with replicas for availability and read capacity. Be aware of skew: popular first letters create hot shards, so split ranges by measured load, not by alphabet. Short prefixes such as single letters are the most cacheable, since there are few of them and they are requested constantly, so serve them from the edge.

Deep dive 4: Relevance, personalisation and safety

Relevance beyond popularity. Weak: rank only by global count. Solid: combine popularity with recency and, where available, the user's location and language. Excellent: blend a global ranking with a small number of personalised suggestions from the user's recent history, retrieved from a separate per-user store and merged at request time. Keep personalisation cheap and optional, and cacheable at the global level.

Safety. Suggestions appear before the user has decided what to search, which makes an offensive or sensitive suggestion more harmful than the same result on a results page. Apply a filter at build time, using blocklists, classifiers and review, and again at serving time so that new rules take effect immediately without a rebuild. Remove queries that expose private information. This is a policy area, so say that the rules need legal and trust-and-safety input.

Deep dive 5: Typos, languages and edge cases

Typos. A prefix with a mistake matches nothing. Handle it with a fallback to fuzzy matching, using edit distance over a limited candidate set, or spell correction suggestions. Keep this as a secondary path, since it is more expensive.

Languages and scripts. Normalise text (case, accents, Unicode forms), tokenise per language, and keep separate structures by language or locale. Scripts without spaces need different segmentation.

Multi-word queries and word-level matching. A user typing the second word of a phrase may want suggestions that match any word, not just the start. Index word-level prefixes as well, at the cost of more storage.

Quality of the data. Search logs are noisy: bots, repeated queries by one user and one-time queries. Filter by distinct users, not raw counts, so one person cannot push a query into suggestions.

Deep dive 6: Failure and operations

Suggestions are an enhancement. If the service is slow or down, the search box must still work, so the client treats suggestions as optional and times out quickly. Replicate serving nodes across zones, deploy snapshots gradually and monitor the click-through rate on suggestions and the latency, which tells you whether a new snapshot is better or worse. Roll back to the previous snapshot if quality drops.

5. What is expected at each level

Mid-level. You propose a trie, explain prefix lookup, and recognise that collecting and sorting descendants at request time is too slow. You mention caching.

Senior. You precompute top-k per node, separate the offline build from online serving, size the system from the estimates, and discuss sharding by prefix and snapshot rollout. You handle freshness with periodic rebuilds and decayed counts.

Staff. You reason about relevance and safety as product concerns, the streaming layer for trends, personalisation costs, evaluation of changes by click-through, multi-language support, abuse by bots and the operational model for rolling out data safely.

6. Interview questions and model answers

Q: Why a trie? It organises strings by shared prefix, so a lookup costs one step per character regardless of how many queries are stored. With the top-k suggestions stored at each node, a request is a short walk and one read.

Q: Why not compute suggestions per request? For a short prefix the node has millions of descendants, so sorting them per request cannot meet a latency target at 100,000 requests per second. Precomputing moves the cost offline.

Q: How do you keep it fresh? A frequent rebuild published as a versioned snapshot that servers swap in atomically, plus a streaming layer for rapidly rising queries, with time-decayed counts so old popularity fades.

Q: How do you shard the data? By prefix range, using measured load to set the ranges, because common first letters are hot. Short prefixes are cached at the edge.

Q: How do you reduce load from clients? Debounce keystrokes, cancel outdated requests, cache recent prefixes in the client and reuse earlier results where valid.

Q: How do you keep suggestions safe? Filter at build time and at serving time with blocklists and classifiers, so rule changes apply instantly, and monitor user reports.

7. Common mistakes

• Computing the ranking at request time.
• Querying a database for every keystroke.
• Sending a request for every character with no debounce.
• Rebuilding only daily, so trends are missed.
• Serving a half-loaded data snapshot.
• Ignoring safety and offensive suggestions.
• Sharding alphabetically and creating hot shards.