System Design Interview: Design Search Autocomplete

In a nutshell

Serve from a trie where each node stores its top-k completions, so a lookup is one walk down the prefix.
Build the trie offline from aggregated query logs (hourly or daily), then swap it in; do not update it per keystroke.
Cache hot prefixes at the edge and in the browser; debounce keystrokes on the client.
Shard by prefix, and filter suggestions (offensive terms, removed content) before they ship.

Requirements

Functional: as the user types, return up to 5–10 suggestions for the prefix, ranked by popularity (optionally personalised or localised).
Non-functional: responses within about 100 ms end to end (so tens of ms on the server); highly available; suggestions can be hours old.

Estimates

Assume 10 million daily users each running 10 searches of about 15 characters, and one request per character typed after debouncing (say every other character): about 750 million requests a day, roughly 9,000 per second on average and a few times more at peak. A trie of the top tens of millions of queries with top-10 lists per node fits in the memory of a few servers.

API

One cacheable GET

Example

GET /suggest?q=sys&lang=en
-> 200 Cache-Control: public, max-age=300
   ["system design", "system design interview", "systemd", "sysadmin", "system of a down"]

Data model

Offline: a table of query → count for a recent window (for example the last 7 days, with older days weighted less). Online: an in-memory trie built from it, each node holding the top-k completions beneath it, serialised as a snapshot that servers load at start-up.

High-level design

Online serving and offline building

Searches are logged and aggregated offline into a new trie snapshot. Suggestion servers answer from memory.

Diagram as text

Users → CDN cache: GET /suggest
CDN cache → Suggest servers: miss
Users → Search logs: searches
Search logs → Aggregation job
Aggregation job → Trie snapshots: build
Trie snapshots → Suggest servers: load

Deep dive: the trie

Each node is a character; the path from the root spells a prefix. To answer quickly, every node stores the top-k completions of its prefix, computed when the trie is built, so a lookup is O(length of prefix). The version below computes the top-k on demand to keep it short; the build step would store each node's result.

A trie returning the most popular completions for a prefix

Java

import java.util.*;

class Autocomplete {
    private static class Node {
        final Map<Character, Node> children = new HashMap<>();
        long count = 0; // > 0 when a query ends here
    }

    private final Node root = new Node();

    void add(String query, long count) {
        Node n = root;
        for (char c : query.toCharArray()) {
            n = n.children.computeIfAbsent(c, k -> new Node());
        }
        n.count += count;
    }

    List<String> suggest(String prefix, int k) {
        Node n = root;
        for (char c : prefix.toCharArray()) {
            n = n.children.get(c);
            if (n == null) {
                return List.of();
            }
        }
        List<Map.Entry<String, Long>> found = new ArrayList<>();
        collect(n, new StringBuilder(prefix), found);
        found.sort((a, b) -> !a.getValue().equals(b.getValue())
            ? Long.compare(b.getValue(), a.getValue())
            : a.getKey().compareTo(b.getKey()));
        List<String> out = new ArrayList<>();
        for (int i = 0; i < Math.min(k, found.size()); i++) {
            out.add(found.get(i).getKey());
        }
        return out;
    }

    private void collect(Node n, StringBuilder sb, List<Map.Entry<String, Long>> out) {
        if (n.count > 0) {
            out.add(Map.entry(sb.toString(), n.count));
        }
        for (Map.Entry<Character, Node> e : n.children.entrySet()) {
            sb.append(e.getKey());
            collect(e.getValue(), sb, out);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

Python

class Autocomplete:
    def __init__(self):
        self.root = {}  # char -> child node; "$" holds the count where a query ends

    def add(self, query, count):
        node = self.root
        for ch in query:
            node = node.setdefault(ch, {})
        node["$"] = node.get("$", 0) + count

    def suggest(self, prefix, k):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return []
            node = node[ch]
        found = []
        stack = [(node, prefix)]
        while stack:
            current, text = stack.pop()
            for key, child in current.items():
                if key == "$":
                    found.append((child, text))
                else:
                    stack.append((child, text + key))
        found.sort(key=lambda item: (-item[0], item[1]))
        return [text for _, text in found[:k]]

Bottlenecks and trade-offs

Freshness vs cost: rebuilding hourly misses breaking news for up to an hour; add a small real-time layer of trending queries merged at serve time.
Size: keep only queries above a count threshold; shard the trie by first characters (with care, since "s" is far bigger than "x").
Client load: debounce (send after a short pause), cancel stale requests, and cache results per prefix in the browser.
Safety: filter offensive or legally removed suggestions in the build step and with a fast blocklist at serve time.

The last five minutes

Common mistakes

Querying the database with LIKE 'prefix%' on every keystroke.
Updating the serving trie synchronously with every search.
Sending a request on every keystroke with no debounce.

Interview questions

Try answering out loud before you open each one.

How do you make suggestions fast?

Precompute: each trie node stores its top-k completions, so serving is a walk of a few characters in memory. Cache popular prefixes at the CDN and in the browser, and debounce on the client. The heavy work (counting queries and building the trie) runs offline.

Your notes

Saved in this browser as you type.

Finished this topic?

Mark it read to track your progress, then carry on with the next one.

Next topic