Design Typeahead / Autocomplete — Cracking the System Design Interview

“Design the search box that suggests queries as you type” looks deceptively simple, but it is one of the best interview questions for separating candidates. The naive answer — run a LIKE 'prefix%' query on every keystroke — collapses instantly at scale. A good answer shows you understand precomputation, the split between online serving and offline indexing, and the brutal latency budget.

We will design a typeahead system like the one behind Google Search or Amazon’s search box: billions of queries a day, suggestions returned in well under 100ms, ranked by popularity.

Understanding the Problem

Functional Requirements

Prefix suggestions: Given a prefix (e.g. "sys"), return the top 5–10 most relevant complete queries ("system design", "system design interview", …).
Ranking: Suggestions are ordered by popularity (how often a query has been searched), ideally blended with recency.
Fresh-enough results: A query trending today should start appearing within hours, not weeks.

Non-Functional Requirements

Low latency: p99 under ~100ms end to end. Every keystroke fires a request, so the budget is tiny.
High read throughput: If 1 billion searches/day average 20 characters each and we query every few keystrokes, we are serving on the order of 100K+ suggestion requests per second.
Read-heavy: Reads outnumber writes (new queries) by many orders of magnitude.
Scalable vocabulary: Hundreds of millions of distinct historical queries.

Estimation

With ~1 billion searches a day and roughly 4–6 suggestion lookups per search (one every few characters, after debouncing), we expect ~5 billion lookups/day ≈ 60K QPS average, with peaks of 2–3× that. Each lookup must return in a few milliseconds of server time to keep the end-to-end budget. This throughput plus the latency target is the entire reason we precompute: there is no room to rank at query time.

Core Entities and APIs

Data Model

The heart of the system is a trie (prefix tree). Each node represents a prefix; crucially, each node also stores a precomputed list of its most popular completions.

interface TrieNode {
  children: Map<char, TrieNode>;
  isWord: boolean;
  topK: Suggestion[];      // Precomputed top-K completions under this prefix
}

interface Suggestion {
  query: string;
  score: number;           // popularity blended with recency
}

Alongside the trie, a separate store holds raw query frequencies, updated by the offline pipeline:

interface QueryStat {
  query: string;
  count: number;           // searches in the aggregation window
  lastSeen: number;        // for recency weighting
}

API Design

GET /suggest?q={prefix}&limit=10
  → 200 { "suggestions": ["system design", "system design interview", ...] }

That is the entire public surface. The write path — recording which queries people actually search — is implicit: it flows through the normal search logs, not a synchronous API call to the typeahead service.

High-Level Design

The decisive insight is that typeahead is two systems glued together: a blazing-fast read-only serving path, and a slow, batch-oriented build path. Conflating them is the classic mistake.

Online serving path — The client (with debouncing) hits a Suggestion Service, which walks an in-memory trie and returns the node’s precomputed top-K. It is read-only, stateless between requests, and trivially replicated behind a load balancer.
Offline build path — Search logs stream into a data store. A batch job (hourly or daily) aggregates query frequencies, computes a ranking score, builds a fresh trie with top-K baked into every node, and publishes it to the serving fleet.

We never mutate the trie on a keystroke. Writes are the firehose of search logs; the trie is rebuilt from them out of band.

Deep Dive: The Trie with Precomputed Top-K

A plain trie answers “is this a prefix?” in O(prefix length). But we need the top-K completions of a prefix, and there can be millions of completions under a short prefix like "a". Ranking them at query time is far too slow.

The fix: store the top-K completions directly on each node.

Trie with cached top-K completions at each prefix node

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
        self.top_k = []        # List[(score, query)], precomputed, length <= K

def search(root, prefix, k=10):
    """O(prefix length) lookup — no ranking at query time."""
    node = root
    for ch in prefix:
        if ch not in node.children:
            return []          # No completions for this prefix
        node = node.children[ch]
    return [q for _, q in node.top_k[:k]]

A lookup is now just walking down the prefix and reading a cached list — O(length of prefix), independent of how many completions exist. Typing "sys" touches 3 nodes and returns instantly.

Building the top-K lists

During the offline build, we insert every query with its score, then propagate top-K upward so each node holds the best completions beneath it. A node’s top-K is the merge of its children’s top-K lists (plus the word ending at the node), truncated to K.

def build_top_k(node, k=10):
    """Post-order: a node's top-K is the merge of its children's top-K."""
    candidates = []
    if node.is_word:
        candidates.append((node.score, node.word))
    for child in node.children.values():
        build_top_k(child, k)
        candidates.extend(child.top_k)
    candidates.sort(reverse=True)         # by score
    node.top_k = candidates[:k]

The memory trade-off

Caching top-K on every node costs memory: with K=10 and hundreds of millions of nodes, the trie can be tens of gigabytes. Two mitigations:

Only cache on nodes above a popularity threshold — rare deep prefixes can fall back to a small on-the-fly search.
Shard the trie by first 1–2 characters across a fleet of servers. The "a*" shard lives on one set of machines, "b*" on another. A lightweight router sends each prefix to the right shard. This keeps each machine’s trie in RAM and scales the vocabulary horizontally.

Deep Dive: Online Serving vs. Offline Build

This separation is what makes the latency budget achievable.

Serving (online)

The serving fleet holds the trie in memory and never writes to it. Because it is immutable between publishes, we can:

Replicate it to dozens of identical nodes behind a load balancer (reads scale linearly).
Avoid all locking — immutable data is trivially thread-safe.
Swap in a new trie atomically (build the new one in memory, flip a pointer).

Building (offline)

Updating the trie on every search would be a write storm and would require locking a structure that is being read 100K times a second. Instead:

Search logs  →  Aggregate (count per query, last 7–30 days)
             →  Score (count blended with recency / decay)
             →  Build trie with top-K on each node
             →  Publish snapshot to serving fleet (hourly/daily)

A reasonable scoring function decays old popularity so trending queries surface and stale ones fade:

score = count * exp(-lambda * age_in_days)

The cadence is a freshness-vs-cost trade-off: rebuild hourly for fast-moving domains (news, shopping), daily where the vocabulary is stable. Breaking news can be handled by a small, fast “trending” overlay merged on top of the base trie.

Why not just update incrementally?

You can maintain approximate counts online (e.g. with a count-min sketch) and nudge rankings, and large systems do blend a real-time layer. But the authoritative ranked index is always rebuilt in batch. Trying to keep an exact, globally ranked, concurrently mutated trie hot under full read load is a losing fight — the batch rebuild sidesteps it entirely.

Deep Dive: The Client and the Edge

A surprising amount of the latency budget is won or lost on the client.

Debouncing: Do not fire a request on every keystroke. Wait ~200ms after the user stops typing. This alone can cut request volume by 3–5× and avoids showing suggestions for prefixes the user has already typed past.
Client-side caching: If the user types "sys" then backspaces to "sy", the result for "sy" is already in hand. Cache recent prefixes in the browser.
Prefix request coalescing / prefetch: The result for "sys" is a strict subset of what was returned for "sy" in many cases; clients can often filter locally for one more character before hitting the server.
CDN / edge caching: Popular short prefixes ("a", "the", "amazon") are requested constantly and change slowly. Cache them at the edge with a short TTL to shave round-trip time and offload the serving fleet.

Briefly worth mentioning if time allows: personalization (blend a user’s own history on top of global suggestions, usually client-side or in a thin per-user layer) and spell correction (map "systim" → "system" via edit-distance expansion before the trie walk).

Key Takeaways

Precompute, do not rank at query time. Each trie node caches its top-K completions, turning a lookup into an O(prefix length) tree walk. The latency budget leaves no room for anything else.
Typeahead is two systems. A read-only, replicated, in-memory serving path and a slow, batch offline build path. Keeping them separate is the core design decision.
Rebuild the trie in batch from query logs. Aggregate counts, apply a recency-decayed score, build top-K into every node, and publish an immutable snapshot every few hours. Do not mutate the trie per keystroke.
Shard the trie by prefix to fit hundreds of millions of queries in RAM and scale horizontally; cache top-K only on popular nodes to bound memory.
Win latency at the client and edge. Debounce (~200ms), cache recent prefixes, and edge-cache hot short prefixes. Much of the p99 budget is spent before the request reaches your service.

The pattern here — serve from a precomputed, immutable, in-memory structure while a batch pipeline rebuilds it offline — recurs across ranking, feed generation, and recommendation systems. Typeahead is the cleanest place to demonstrate you understand it.