Design Search Autocomplete System

Design Search Autocomplete System is a classic "design" trie problem. It is the engine behind the dropdown that appears under a search box: as you type each character, it instantly offers the most popular things people typed before that start with what you have so far.

The slow way first

The brute-force idea: keep every past sentence in a list. On each keystroke, scan the whole list, filter to the ones starting with the current prefix, then sort them by count. If there are n stored sentences this is O(n) filtered work plus an O(n log n) sort on every single character. For a real search bar with millions of sentences that is hopeless.

The question to ask: the prefix only grows by one character at a time — can I reuse the work from the previous keystroke instead of rescanning everything? A trie does exactly that.

The idea: a trie where each node remembers its sentences

Store the history in a trie (prefix tree): one edge per character. The trick is that each node carries a small map of sentence -> count for every full sentence that passes through it. Now typing a character is just walking one edge down. The node you land on already holds every candidate that matches the prefix — no scanning. Rank that node's map by (count desc, then lexicographic) and take the first 3.

The key insight: the prefix never resets, so we never restart the walk from the root for nothing — each keystroke advances the same path one node deeper, and the candidate set only shrinks.

Walk through it

Step through the animation. We type 'i', then a space, then 'l'. Each character lights up one edge and moves us one node down. At each node the top-3 panel re-ranks the sentences stored beneath it: 'island' falls out the moment we type the space (it has no space in it), and the list keeps narrowing. When we type 'a' after 'i l', node l has no a child — the walk falls off the trie and we return an empty list.

Pseudocode

keyword = keyword + c               # grow the typed prefix
node = root
for each character ch in keyword:
    if ch is not a child of node:
        return []                   # nothing matches this prefix
    node = node.children[ch]
candidates = every (sentence, count) stored at node
sort candidates by count descending, then sentence ascending
return the first 3 sentences

The Python solution

def input(self, c):
    self.keyword += c
    node = self.root
    for ch in self.keyword:
        if ch not in node.children:
            return []          # fell off the trie
        node = node.children[ch]
    # rank sentences stored under this node
    cands = node.counts.items()
    ranked = sorted(cands, key=lambda kv: (-kv[1], kv[0]))
    return [s for s, _ in ranked[:3]]

• self.keyword accumulates everything typed since the last #; we re-walk it from the root.
• The for loop walks one node per character; in practice you cache node between calls so each keystroke is a single hop.
• Line 5 to 6 is the fall-off case: if the current character has no edge, no stored sentence matches, so return [].
• node.counts is this node's map of every full sentence passing through it to its hot count.
• The sort key (-count, sentence) ranks by count descending, then sentence ascending for ties; ranked[:3] keeps the top 3.

Complexity

Here N is the total length of all stored sentences (the trie size) and k is usually tiny — only the sentences sharing this prefix. We replace an O(n) rescan with a single edge walk plus a sort over a small candidate set.

When this pattern shows up

Practice