Design a search autocomplete/typeahead service — how do you return suggestions in milliseconds?

#The constraint that shapes everything: the query happens on every keystroke

A search box firing a request after every keystroke means a user typing "chicago" generates seven requests in roughly two seconds, and each one needs to come back before the user has typed the next letter or the UI feels laggy. That rules out anything that touches a general-purpose search index or scans a table at request time — the budget is single-digit milliseconds of server-side work, which means the answer has to be looked up, not computed, when the request arrives.

The client side matters too, and it's often where the interview starts: debounce keystrokes (wait ~100-150ms after the user stops typing before firing a request, so "united" doesn't send seven requests when the user types fast), cancel in-flight requests that are no longer for the current input value (an older, slower response for "c" can otherwise arrive after the newer response for "ch" and flash the wrong list), and cache recent prefix results on the client so backspacing doesn't re-hit the network.

#Server side: precompute, don't search

The core idea is a trie (prefix tree): each node represents one character, and a path from the root spells out a prefix. Instead of walking the trie at query time and then ranking whatever full words hang below a node — which is exactly the slow part — each node precomputes and stores its own top-K suggestions, sorted by a popularity/relevance weight, built during an offline or periodic indexing job. A query then does nothing more than walk to the node for the typed prefix and return a list that's already sorted.

type Suggestion = { term: string; weight: number };

const TOP_K = 8;

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  // Precomputed, weight-sorted suggestions for the prefix ending at this node.
  topSuggestions: Suggestion[] = [];
}

class AutocompleteTrie {
  private root = new TrieNode();

  insert(term: string, weight: number): void {
    let node = this.root;
    this.updateTopK(node, term, weight);
    for (const ch of term.toLowerCase()) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch)!;
      this.updateTopK(node, term, weight);
    }
  }

  private updateTopK(node: TrieNode, term: string, weight: number): void {
    const existing = node.topSuggestions.find((s) => s.term === term);
    if (existing) {
      existing.weight = weight;
    } else if (node.topSuggestions.length < TOP_K) {
      node.topSuggestions.push({ term, weight });
    } else if (weight > node.topSuggestions[TOP_K - 1].weight) {
      node.topSuggestions[TOP_K - 1] = { term, weight };
    } else {
      return; // not popular enough to displace anything at this node
    }
    node.topSuggestions.sort((a, b) => b.weight - a.weight);
  }

  suggest(prefix: string): string[] {
    let node = this.root;
    for (const ch of prefix.toLowerCase()) {
      const next = node.children.get(ch);
      if (!next) return [];
      node = next;
    }
    return node.topSuggestions.map((s) => s.term);
  }
}

// Built (or rebuilt) periodically from aggregated query-log weights.
const trie = new AutocompleteTrie();
trie.insert("chicago bulls", 9800);
trie.insert("chicago weather", 15200);
trie.insert("chick-fil-a near me", 42000);

console.log(trie.suggest("chi"));
// -> ["chick-fil-a near me", "chicago weather", "chicago bulls"]

A lookup is now O(L + K log K) where L is the length of the typed prefix and K is the small constant number of suggestions kept per node — effectively O(L), independent of how many total terms the system knows about. That's the whole trick: pay the ranking cost once, offline, per prefix, instead of once per keystroke, per user.

#The request path end to end

Short-TTL edge caching absorbs the fact that common prefixes ("a", "the", "how") are requested constantly and identically by many users — a cache hit there costs nothing and never touches the trie service at all.

#Keeping the trie fresh, and the parts that are genuinely hard

The trie above is a read-optimized snapshot; it isn't meant to be updated transactionally per query. In practice, a background job rebuilds it (or rebuilds just the affected subtrees) periodically — every few minutes for a fast-moving trending-topics feed, hourly or daily for a stable product catalog — from an aggregated weight source: raw search-click logs, sales counts, or a manually curated boost? list. Serving continues from the previous snapshot while the next one builds, then the service atomically swaps to the new one, so users never see a half-built trie.

The genuinely hard parts, roughly in the order interviewers probe them: typo tolerance (the trie as described here requires an exact-prefix match; fuzzy matching needs a separate edit-distance layer or an n-gram index, and is usually a distinct, slower fallback path rather than baked into the hot path); personalization (a user's own history reordering or injecting suggestions on top of the global ranking, usually blended client-side or in a thin per-request layer rather than by maintaining one trie per user); multi-word and out-of-order matching ("nyc pizza" should probably also surface "pizza in nyc," which a pure prefix trie cannot do without additional indexing by each word, not just the whole string); and memory at genuine web scale (a trie over billions of distinct queries doesn't fit on one box, so it gets sharded, commonly by first character or a hash of the first few characters, with a routing layer in front).

🧠 Check your understanding
0/2 · 0/2 answered
1. Why does each trie node store its own precomputed top-K suggestions instead of ranking on every request?
It allows the trie to also support fuzzy typo matchingIt removes the need for a query logIt uses less memory than storing the terms onceIt moves the expensive ranking work offline, so a live query is just an O(L) lookup
2. A plain prefix trie, as described, struggles most with which requirement?
Handling millions of distinct search termsMatching a query where the words are typed in a different order, like "nyc pizza" vs "pizza in nyc"Returning results in under 50msStoring a popularity weight per term