You're twenty minutes into a system design round. The prompt was "design search autocomplete," there's a box on the whiteboard labelled Trie Service, and the interviewer asks the question that decides the hour: "The user types p. What does your service do?"

The losing answer goes like this. Walk down to the p node, collect every query in its subtree, sort them by count, return the first ten. It is correct. It is also the wrong design. A 2013 paper on top-k completion from Microsoft Research and the University of Pisa states the problem plainly: for large string sets, short prefixes can match millions of strings, and enumerating and sorting them per request "is prohibitive in terms of speed." Your service does that on every keystroke.

Requirements, and the 100 ms that drives everything

State the functional scope out loud. Given a prefix, return up to 10 completions ranked by popularity. Popularity comes from what people actually searched, which is how Google describes its own predictions: drawn from "the real searches that happen on Google," showing "common and trending ones" for the characters typed. New trends should surface within hours. Personalization stays out of scope unless the interviewer pulls it in.

The non-functional requirement that shapes the design is latency. Jakob Nielsen's response-time limits put 0.1 seconds as "about the limit for having the user feel that the system is reacting instantaneously." Facebook's engineers landed on the same number in their 2010 write-up of the typeahead rebuild: more than 100 msec to retrieve a result and the typeahead stutters. That budget includes the network round trip, so the server only gets part of it.

Then the capacity math. These are illustrative assumptions, and saying so is part of the answer:

  • 10M daily active users, 6 searches each: 60M searches a day.
  • Average query length of 20 characters. One request per keystroke is 1.2B requests a day, about 13,900 per second on average and around 42,000 at a 3× peak.
  • Client-side debouncing and caching (last section) cutting that to roughly 5 requests per search: 300M a day, about 3,500 per second, around 10,400 at peak.
  • 10M distinct queries worth keeping after you prune the long tail. At 20 characters each, that's at most 200M trie nodes before shared prefixes collapse them.

Two conclusions fall out. Reads outnumber writes by orders of magnitude, so you can precompute aggressively. And the client controls a 4× swing in your traffic, so it belongs in the design.

Put the answer at every node

The fix for the subtree walk is to move the work from query time to build time. Every node stores the top 10 completions for the prefix it represents. A lookup walks len(prefix) edges and returns a list that already exists. No subtree, no sort.

A trie drawn as a branching tree, each node holding a small stack of ranked cards
Each node carries its own short ranked list, so a lookup never descends below the prefix.

Here is a short Python version. It runs on the standard library:

from collections import Counter K = 10 class Node: __slots__ = ("children", "top") def __init__(self): self.children = {} self.top = [] # (count, query) pairs, best first  def _path(root, query): node, nodes = root, [root] for ch in query: node = node.children.setdefault(ch, Node()) nodes.append(node) return nodes def _offer(node, count, query, k): node.top = [t for t in node.top if t[1] != query] node.top.append((count, query)) node.top.sort(key=lambda t: (-t[0], t[1])) del node.top[k:] def build(counts, k=K): root = Node() for query, count in counts.items(): for node in _path(root, query): _offer(node, count, query, k) return root def suggest(root, prefix): node = root for ch in prefix: node = node.children.get(ch) if node is None: return [] return [query for _, query in node.top]

Feed it a toy log and pin the ranking:

if __name__ == "__main__": log = ["pytorch", "pytorch", "pytorch", "python list", "python list", "python", "python dict", "pyramid"] counts = Counter(q.strip().lower() for q in log) trie = build(counts, k=3) assert suggest(trie, "py") == [ "pytorch", "python list", "pyramid"] assert suggest(trie, "pyt") == [ "pytorch", "python list", "python"] assert suggest(trie, "pyth") == [ "python list", "python", "python dict"] assert suggest(trie, "pz") == []

The build offers each query to every node on its path, and each node keeps only its best k. Ties break alphabetically so results are deterministic. The asserts pin the behaviour: pytorch was searched three times, so it leads every prefix it belongs to, and pyramid drops out once the prefix becomes pyt.

Raise the probe yourself before the interviewer does: what does this cost in memory? With the numbers above, 200M nodes times 10 query IDs at 4 bytes each is up to 8 GB for the lists alone. The same paper calls precomputing top-k at every node "space inefficient" and points out it needs k fixed in advance. So store query IDs in the lists, never strings, and name the mitigations: compact single-child chains into a radix trie, skip the list at any node whose subtree holds k or fewer queries (a walk there is bounded), and cap the prefix length you serve.

Then give the alternative. The paper's Completion Trie stores only the highest score in each node's subtree and finds the top k with a best-first search over a priority queue. On the AOL query log with 10M unique queries, it took 120 bits per query including scores (which works out to about 150 MB) and averaged 3.7 μs per top-10 completion on a simulated workload. Precomputed lists are the simplest to explain and the cheapest per lookup. The max-score trie is what you reach for when the interviewer pushes on memory. Naming both and picking one for your numbers is the answer that scores.

Rebuild offline, patch online

The counts come from query logs. The offline path aggregates a window of logs (say seven days, older days weighted less), drops junk and anything your content policy blocks, builds a fresh trie, and ships it as a snapshot. Serving nodes load the new snapshot next to the old one and swap a pointer. Run it hourly or daily.

The interviewer's probe here: "A query starts trending at 9:00. When does it show up?" With a daily rebuild, tomorrow. That's too slow for news, so add an online path. Add this to the same file:

def bump(root, counts, query, delta=1, k=K): # Increments only. Decrements need a rebuild.  counts[query] += delta for node in _path(root, query): _offer(node, counts[query], query, k) # usage, after build(): # bump(trie, counts, "pyramid", delta=3, k=3) # assert suggest(trie, "py")[0] == "pyramid"

An increment touches one node per character and re-sorts at most k + 1 entries at each. Decrements are the trap. When a query's count drops and it falls out of a node's top 10, the 11th-best query was never stored, so the node can't fill the gap without walking its subtree. That's why a common split is: the offline rebuild owns decay and deletions, the online path only adds. On a read-heavy service you'd also buffer bumps and apply them in batches, or keep a small delta index that gets merged with the snapshot at read time.

One exception to "wait for the rebuild": removing a harmful suggestion. That can't wait an hour, so keep a blocklist that every read checks before returning results.

Sharding by prefix, and the keystroke that melts one shard

Even the 8 GB version fits in one machine's memory, so the first answer is replication, not sharding. Shard when the index or the QPS outgrows a node.

The obvious scheme is range sharding on the leading characters: a to f on one shard, g to m on the next. It keeps each subtree together, which you need if lookups walk the trie. It also puts the load where the alphabet puts it, and first letters are not evenly distributed. Worse, every search starts with a one-character prefix, so a handful of tiny keys take a share of total traffic far out of proportion to their size. That's the hot-prefix problem, and the interviewer will ask what you do about it.

Several server racks in a row, one overwhelmed by a swarm of arrows while the others sit idle
Range sharding by first letter sends the busiest prefixes to the same few machines.

Three moves, in the order you'd say them:

  1. Drop the trie at serving time. Once every node's top-k is precomputed, a lookup is a key-value read: prefix in, list out. The trie becomes a build artifact. Hash-shard the prefix keys and no shard owns a whole letter anymore, so load spreads across prefixes. A single hot key like p still lands on one shard, which is what the next move is for.
  2. Cache the hottest keys everywhere. There are only 26 one-letter and 676 two-letter lowercase prefixes. Keep their lists in every application server's memory, or at the CDN.
  3. Split by measured traffic. If you keep range sharding, cut ranges by observed QPS.

The client does half the work

The capacity math assumed the browser cuts requests by 4×. Three techniques do it: wait until typing pauses, remember answers per prefix, and cancel requests the user has already typed past. Facebook's typeahead went further, loading the user's connections into the browser cache when the search box gets focus and only going to the server when the cache can't fill the list.

Here's the client in TypeScript, using fetch and AbortController:

const cache = new Map<string, string[]>(); let inflight: AbortController | null = null; let timer: ReturnType<typeof setTimeout> | undefined; export function onInput( text: string, render: (items: string[]) => void, ): void { clearTimeout(timer); const key = text.trim().toLowerCase(); if (key === "") { inflight?.abort(); return render([]); } const hit = cache.get(key); if (hit) { inflight?.abort(); return render(hit); } timer = setTimeout(async () => { inflight?.abort(); const ctrl = new AbortController(); inflight = ctrl; try { const url = `/suggest?q=${encodeURIComponent(key)}`; const res = await fetch(url, { signal: ctrl.signal }); if (!res.ok) return; const items: string[] = await res.json(); cache.set(key, items); render(items); } catch (err) { if ((err as Error).name !== "AbortError") throw err; } }, 150); }

Treat the 150 ms delay as a starting point and tune it against your own keystroke data. Aborting the previous request also fixes out-of-order responses: an answer for py can't land on top of the answer for pyth. One more trick worth saying out loud: if the response for pyt held fewer than 10 results, it was the complete set, so every longer prefix is a local filter over that list and needs no request. That inference breaks once the read-time blocklist can strip results, so have the server send an explicit complete: true flag instead of letting the client guess from the length.

On the HTTP side, non-personalized suggestions can carry Cache-Control: max-age so browsers and the CDN absorb repeats. If you later add personalization, the same MDN page is blunt about the risk: without private, a personalized response can be stored in a shared cache and "end up being reused for multiple users."

Each step in this round has a probe waiting behind it, and you score by raising it first.

If this was useful

Typeahead is one of those designs where the data structure is the easy half and the trade-offs are the interview. If walking from requirements to numbers to the probe behind each choice helped here, System Design Pocket Guide: Interviews takes 15 real system designs through step by step, so you can rehearse that rhythm on more than one prompt before the real round.

System Design Pocket Guide: Interviews — 15 Real System Designs, Step by Step