Design Search Autocomplete: System Design Interview Guide

"Design search autocomplete" looks like a data structure question, and candidates often spend the whole interview on the trie. The trie is ten minutes of it. The real design is about a latency budget smaller than the gap between two keystrokes, traffic that multiplies with every character typed, and suggestions that keep up with what people search for today.

The problem it solves

Start with requirements and numbers. The lesson's illustrative assumptions:

• Ten ranked suggestions per keystroke, back on screen within 100 ms end to end.
• 10,000 queries a second at peak, over about 50 million distinct prefixes.
• Ranking by popularity, recent searches weighted more than old ones.
• Eventual freshness is fine. A query that starts trending can appear minutes or an hour later, not instantly.

Running a real search and ranking the matches on every request cannot fit that budget. The whole design follows from one decision: compute the answers before anyone asks, so a request is a lookup.

The intuition

Split the system into a read path and a build path.

The read path must be as short as possible:

1. The client debounces. It waits for a short pause in typing before sending, and cancels any request still in flight when a newer prefix replaces it. Fast typists stop generating a request per character.
2. The edge cache answers popular prefixes. Short prefixes are shared by millions of users, so a CDN or regional cache keyed by the exact prefix serves them without touching your servers. Short TTLs keep them reasonably fresh.
3. The suggest service does one lookup. It holds a prefix structure in memory, a trie whose nodes carry their own top 10, or the same thing flattened into a prefix → list table. The algorithmic detail is in autocomplete with a trie; here it only matters that a lookup does no ranking.

The build path runs offline. Search logs flow into a batch job that aggregates counts per query, applies time decay so last week's spike fades, drops queries that are rare, unsafe or personal, and computes the top 10 for every prefix. The job writes a new versioned snapshot; servers load it and swap atomically, keeping the old one for rollback.

Sizing, still illustrative: if each suggestion is stored as a 4-byte query id, 50 million prefixes times ten ids is 2 GB before keys and overhead. That fits in one large server's memory, so you replicate for throughput and availability before you need to shard. If it ever outgrows a box, shard by prefix range, and watch the hot shard holding the most common first letters.

Watch it run

The animation starts from the load: ten thousand queries a second, and every keystroke is a candidate request, so cut them first. Debounce, and cancel whatever is still in flight: five keystrokes, one request. The prefix "sys" goes to the edge cache before it goes anywhere expensive. Nobody nearby has typed it yet, a miss, so it travels on to the suggest service. The service walks the trie a character at a time, and no ranking happens there. Three hops down, s, sy, sys, and the walk is the whole lookup. That node already holds its own top ten, so answering is a read, not a search: 8 ms. The edge keeps the list, so the next person typing "sys" gets it in a millisecond and never reaches the origin. Popularity keeps moving, so an offline job recounts the logs and rebuilds; it runs hourly, and until the next build lands, suggestions can be an hour old. That lag is what precomputing costs. Last, a prefix no node covers falls back to a real search: correct, but 240 ms instead of 8.

The code

A toy model of both paths. First the client: a trailing debounce on simulated keystroke times, with a pause after each word, sending only when the user stops for 150 ms:

import random

def debounce(times_ms, wait_ms):
    """Send a request only after the user pauses for wait_ms; earlier ones never leave."""
    sent = []
    for i, t in enumerate(times_ms):
        nxt = times_ms[i + 1] if i + 1 < len(times_ms) else None
        if nxt is None or nxt - t >= wait_ms:
            sent.append(i + 1)                       # length of the prefix that gets sent
    return sent

rng = random.Random(34)
typed = "system design"
t, times = 0, []
for ch in typed:
    t += 400 if ch == " " else rng.randint(60, 140)  # a pause after each word
    times.append(t)
print(len(typed), debounce(times, 150))              # 13 [6, 13]

Thirteen keystrokes, two requests: "system" during the pause, then the full query. Next, the offline build. Each log entry is a query and the hour it was searched; popularity halves every 24 hours, and every prefix keeps its top k:

import heapq
from collections import defaultdict

HALF_LIFE_H = 24

def build_table(log, now_h, k=3):
    """Offline job: decayed popularity per query, then the top k for every prefix."""
    score = defaultdict(float)
    for query, at_h in log:
        score[query] += 0.5 ** ((now_h - at_h) / HALF_LIFE_H)   # yesterday counts half
    by_prefix = defaultdict(list)
    for query, s in score.items():
        for i in range(1, len(query) + 1):
            by_prefix[query[:i]].append((-s, query))
    return {p: [q for _, q in heapq.nsmallest(k, c)] for p, c in by_prefix.items()}

log = ([("system design", 0)] * 8 + [("sys admin", 47)] * 5 +
       [("syntax error", 47)] * 3 + [("symbol", 20)] * 2)
table = build_table(log, now_h=48)
print(table["sys"])          # ['sys admin', 'system design']
print(table["sy"])           # ['sys admin', 'syntax error', 'system design']
print(table.get("sz", []))   # []
print(len(table))            # 33

"system design" was searched eight times, but two days ago, so it decays to an effective 2 and drops below five searches from an hour ago. The serving side is now a dictionary lookup. Then a brute-force check on 300 seeded random logs: every prefix's list must equal a full scan of the log with startswith, decayed and sorted from scratch:

def brute_force(log, now_h, prefix, k=3):
    totals = {}
    for query, _ in log:
        if query.startswith(prefix):
            totals[query] = sum(0.5 ** ((now_h - a) / HALF_LIFE_H) for q, a in log if q == query)
    return sorted(totals, key=lambda q: (-totals[q], q))[:k]

rng = random.Random(34)
ok = True
for _ in range(300):
    words = ["".join(rng.choice("abc") for _ in range(rng.randint(1, 4))) for _ in range(8)]
    log = [(rng.choice(words), rng.randint(0, 72)) for _ in range(rng.randint(1, 40))]
    k = rng.randint(1, 4)
    table = build_table(log, now_h=72, k=k)
    for prefix in {w[:i] for w in words for i in range(1, len(w) + 1)} | {"cc", "d"}:
        ok &= table.get(prefix, []) == brute_force(log, 72, prefix, k)
print(ok)                    # True

The complexity

• Serve: one hash lookup or a walk of P trie hops for a prefix of length P, plus copying k results; no ranking.
• Build: each query contributes one entry per prefix, so O(total query length) entries, then a top-k selection per prefix.
• Space: one list of k per distinct prefix; store ids, not strings, and cap prefix length.
• Traffic: debouncing and edge caching remove most requests before they exist.

Where it goes wrong

• Ranking at request time. Correct and far too slow; precompute.
• No cancellation. Late answers for old prefixes can overwrite newer ones on screen; tag responses with their prefix and drop stale ones.
• No filtering in the build. Logs contain offensive, private and spam queries; suggestions amplify whatever passes.
• Treating freshness as free. A faster rebuild, or a small real-time trending layer merged at read time, buys freshness with complexity.
• Personalising everything. Per-user suggestions defeat the shared edge cache; blend a small personal list on the client.

When it shows up in interviews

As "design typeahead" or "design search autocomplete" in system design rounds, often after a trie coding question. Interviewers probe the latency budget, how the top 10 is kept fresh, how to cut request volume, and what happens at the edge cache. It pairs naturally with designing a web crawler as the other half of a search engine. The trie itself is listed with its siblings on the patterns cheat sheet.

How to say it in an interview

"The budget is under 100 ms per keystroke at 10,000 queries a second, so nothing is ranked at request time. The client debounces and cancels in-flight requests, popular prefixes come from an edge cache, and the suggest service does one in-memory lookup of a precomputed top 10. An offline job aggregates search logs with time decay, filters them, and ships a versioned snapshot that servers swap in. The cost is staleness of one rebuild, which a small real-time trending layer can reduce. The table fits in memory, so I replicate before I shard."