How would you design a typeahead/autocomplete system?

Q: How would you design a typeahead/autocomplete system?

**Target Audience:** Engineers preparing for a system design round; you know what a server and a database are, and data structures like tries are explained from scratch. **Difficulty:** Hard **Verified with:** Node 22.22, Python 3.12, Go 1.24 and Java 21 (all four print identical output). The capacity figures are worked arithmetic from stated assumptions, not measurements of a real service. > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. The capacity numbers and the trie lookups come from the example program; the **Verified** section quotes its full output. ## 1. Why This Even Matters — A Story First Think of a librarian who has worked at the same desk for twenty years. You start to say "I am looking for a book about ca..." and before you finish she says "cars, cats or cameras?". She is not searching the shelves while you speak; she already knows, for every wa

The problem

Question presented to candidate: "As a user types into our search box, we want to show the five most popular completions for what they have typed so far, updated on every keystroke. We have about 100 million daily users. How would you design that?"

What a strong answer should cover:

A capacity estimate that starts from keystrokes, not searches (requests per second after debouncing), and the size of the suggestion data
The core structure: a trie (prefix tree) where every node stores its precomputed top-k completions, so a lookup is a walk of length equal to the prefix, not a search of the subtree
The data pipeline: query logs aggregated with time decay, filtered, built into tries offline, swapped in atomically; plus a fast path for trending queries
Serving: in-memory replicas, sharding by prefix and its hot-spot problem, caching of short prefixes at the edge and in the browser
Client behaviour (debounce, cancel stale requests, cache results) and extensions: personalization, typo tolerance, filtering offensive suggestions

Clarifying questions expected:

How fresh must suggestions be: is a daily rebuild acceptable, or must trending queries appear within minutes?
Ranking by global popularity only, or personalized, or by location and language?
Do we need typo tolerance, or prefix matching only?

Code / implementation expected: Optional — a trie with top-k cached per node and a comparison with searching the subtree; the example does both and shows a rebuild picking up a trending query.

autocomplete
trie

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Engineers preparing for a system design round; you know what a server and a database are, and data structures like tries are explained from scratch. Difficulty: Hard Verified with: Node 22.22, Python 3.12, Go 1.24 and Java 21 (all four print identical output). The capacity figures are worked arithmetic from stated assumptions, not measurements of a real service.

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. The capacity numbers and the trie lookups come from the example program; the Verified section quotes its full output.

1. Why This Even Matters — A Story First

Think of a librarian who has worked at the same desk for twenty years. You start to say "I am looking for a book about ca..." and before you finish she says "cars,

The solution is hidden so you can try first

14 min read · 16 sections

Read the code

Typeahead trie with top-k cached in every node vs searching the subtree on each keystroke

Open in playground

// Typeahead: a trie that stores the top-k completions in every node, versus searching the subtree per keystroke.
const K = 3;

console.log("== capacity estimate ==");
const dau = 100000000, searchesPerUser = 10, requestsPerSearch = 6; // after a 100 ms debounce
const perDay = dau * searchesPerUser * requestsPerSearch;
const avgQps = Math.ceil(perDay / 86400);
console.log("suggestion requests/day: " + perDay + ", avg " + avgQps + "/s, peak (x2) " + avgQps * 2 + "/s");
const queries = 10000000, avgLen = 20, bytesPerEntry = 8;
console.log("trie upper bound: " + queries * avgLen + " nodes, top-" + K + " lists: " + (queries * avgLen * K * bytesPerEntry) / 1000000 + " MB of pointers");

function better(a, b) { return a[1] !== b[1] ? b[1] - a[1] : a[0] < b[0] ? -1 : a[0] > b[0] ? 1 : 0; }

class Trie {
  constructor() { this.root = { kids: new Map(), top: [], end: 0 }; this.nodes = 1; }
  insert(word, count) {
    let node = this.root;
    const offer = (n) => { n.top.push([word, count]); n.top.sort(better); if (n.top.length > K) n.top.pop(); };
    offer(node);
    for (const ch of word) {
      if (!node.kids.has(ch)) { node.kids.set(ch, { kids: new Map(), top: [], end: 0 }); this.nodes++; }
      node = node.kids.get(ch);
      offer(node);
    }
    node.end = count;
  }
  walk(prefix) {
    let node = this.root, steps = 0;
    for (const ch of prefix) { node = node.kids.get(ch); steps++; if (!node) return [null, steps]; }
    return [node, steps];
  }
  fast(prefix) { const [n, steps] = this.walk(prefix); return [n ? n.top.map((e) => e[0]) : [], steps]; }
  slow(prefix) { // no cached lists: collect every completion below the prefix, then sort
    const [n, steps] = this.walk(prefix);
    if (!n) return [[], steps];
    const found = [];
    let visited = 0;
    const dfs = (node, path) => {
      visited++;
      if (node.end) found.push([path, node.end]);
      for (const [ch, kid] of node.kids) dfs(kid, path + ch);
    };
    dfs(n, prefix);
    found.sort(better);
    return [found.slice(0, K).map((e) => e[0]), steps + visited];
  }
  stored() { let s = 0; const go = (n) => { s += n.top.length; for (const kid of n.kids.values()) go(kid); }; go(this.root); return s; }
}

const log = [["car", 900], ["cat", 800], ["card", 700], ["camera", 650], ["dog", 600], ["chat", 550], ["call", 500],
  ["can", 450], ["care", 400], ["cake", 350], ["cart", 300], ["door", 300], ["carpet", 250], ["catalog", 200], ["cats", 150], ["dot", 100]];
const build = (entries) => { const t = new Trie(); for (const [w, c] of entries) t.insert(w, c); return t; };
let trie = build(log);
console.log("== built from " + log.length + " queries: " + trie.nodes + " nodes, " + trie.stored() + " cached suggestion entries ==");
for (const p of ["c", "ca", "car", "cat", "d", "do", "x"]) {
  const [f, fw] = trie.fast(p);
  const [s, sw] = trie.slow(p);
  console.log(JSON.stringify(p) + " -> [" + f.join(", ") + "]  nodes touched: cached " + fw + ", subtree search " + sw + " (same: " + (f.join() === s.join()) + ")");
}

console.log("== next rebuild: chatgpt trends with 5000 searches ==");
trie = build(log.concat([["chatgpt", 5000]]));
for (const p of ["c", "ch", "ca"]) console.log(JSON.stringify(p) + " -> [" + trie.fast(p)[0].join(", ") + "]");

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.