Design Search Autocomplete

Precompute top-k per prefix

Requirements: as the user types, return the top few suggestions for the prefix within tens of milliseconds; ranking by popularity, maybe personalised; data refreshed periodically. Core structure: a trie where each node stores the precomputed top-k completions for that prefix, so a lookup is O(length of prefix) with no subtree traversal. Build it offline: aggregate query logs (for example, daily or hourly with a batch or streaming job), compute frequencies, build the trie, and ship snapshots to serving nodes. Serve from memory, shard by prefix range if it is too large for one node, and put a cache (and even the browser or CDN, for very short prefixes) in front. Filter offensive terms before publishing, and debounce requests on the client.

Trie with top-k at each node

Python; built offline from (query, count) pairs.

import heapq

class TrieNode:
    __slots__ = ("children", "top")
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.top: list[tuple[int, str]] = []    # (count, query)

class Autocomplete:
    def __init__(self, k: int = 5):
        self.root = TrieNode()
        self.k = k

    def build(self, counts: dict[str, int]) -> None:
        for query, count in counts.items():
            node = self.root
            for ch in query:
                node = node.children.setdefault(ch, TrieNode())
                node.top.append((count, query))
        self._trim(self.root)

    def _trim(self, node: TrieNode) -> None:
        node.top = heapq.nlargest(self.k, node.top)
        for child in node.children.values():
            self._trim(child)

    def suggest(self, prefix: str) -> list[str]:
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return []
        return [q for _, q in node.top]

Separate build from serve

Rebuilding the trie offline and swapping snapshots keeps the read path simple and fast; real-time trending terms can be merged from a small separate index.

Quick check: Why store top-k completions at each trie node?

• To support exact-match search only
• To reduce the number of prefixes
• So a lookup does not need to traverse the whole subtree
• To make writes faster than reads