Cruxly › Low-level design › LLD Exercises

Search Autocomplete (LLD)

a trie gets you the matches; ranking the top few is the actual exercise

Prompt: design a search-autocomplete system. Given a prefix typed so far, return the top K most popular completions in real time as the user types, updating popularity as searches happen.

45 minutes. Retrieving every completion for a prefix is the easy half — a trie does that directly. Returning only the top K by popularity without re-sorting on every keystroke is the actual exercise.

Applying the five moves: nouns are TrieNode, Query (the completion string), and a per-node topK cache — that cache is the noun the naive model leaves out, and adding it is the entire design. The invariant is "every node's cached top-K is consistent with the popularity scores of the subtree beneath it" — stating it immediately raises the real question, which is when that cache is refreshed on a popularity update and what staleness is acceptable in between. The interface seam worth naming is the ranking function itself (popularity today, but "popularity" is exactly the kind of thing a follow-up redefines — recency-weighted, personalized, trending), so keeping scoring behind a small interface is justified by a predictable variation rather than invented. Concurrency: reads (keystrokes) vastly outnumber writes (popularity updates), which is the classic read-heavy shape — say that the cache refresh can be asynchronous and slightly stale without breaking the product, because a suggestion list being a few seconds behind is invisible, and that observation is what buys the whole performance story.

Scope, and why the trie alone doesn't answer the actual question

In scope: prefix-based retrieval, ranking completions by a popularity/frequency score, updating popularity as queries happen, returning top K per prefix in real time. Out of scope (say it): typo-tolerance/fuzzy matching (a genuinely different, much harder retrieval problem — name it and move on), personalized-per-user ranking, multi-language tokenization.

A trie answers "what words exist under this prefix," not "what are the top K most popular words under this prefix" — these are different questions, and conflating them is the most common shallow answer. A prefix like "a" in a search engine might have millions of completions in the trie; returning "the top 5 by popularity" from a subtree of millions, computed fresh on every keystroke by walking the whole subtree, is far too slow for something the user experiences as instant.

The actual exercise is deciding when the top-K computation happens — at query time (too slow for a large subtree, as above), or precomputed and cached ahead of time so a query is a cheap lookup. Precomputing means every trie node needs to know its own top K, and that cached list has to be kept current as popularity scores change underneath it — which is where this problem actually lives.

The classes: a trie node that caches its own top K

public class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    // Cached top-K completions FOR THIS NODE'S SUBTREE, kept sorted by score.
    // This is what turns a query into an O(K) lookup instead of a subtree walk.
    List<ScoredTerm> topK = new ArrayList<>();
}

public record ScoredTerm(String term, long score) {}

public class AutocompleteSystem {
    private final TrieNode root = new TrieNode();
    private final int K;
    private final Map<String, Long> termScores = new HashMap<>();

    public List<String> getSuggestions(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            node = node.children.get(c);
            if (node == null) return List.of();       // no completions for this prefix at all
        }
        return node.topK.stream().map(ScoredTerm::term).toList();
    }

    /** Called when a search term is actually chosen/completed — updates the
     *  term's score, then propagates the new top-K up through every prefix
     *  node the term passes through on its way from the root. */
    public void recordSearch(String term) {
        long newScore = termScores.merge(term, 1L, Long::sum);
        TrieNode node = root;
        for (char c : term.toCharArray()) {
            node = node.children.computeIfAbsent(c, k -> new TrieNode());
            updateTopK(node, term, newScore);
        }
    }

    private void updateTopK(TrieNode node, String term, long score) {
        node.topK.removeIf(t -> t.term().equals(term));    // remove stale entry for this term, if present
        node.topK.add(new ScoredTerm(term, score));
        node.topK.sort((a, b) -> Long.compare(b.score(), a.score()));
        if (node.topK.size() > K) node.topK.remove(node.topK.size() - 1);  // keep bounded at K
    }
}

Every node from the root down to a completed term's last character gets its cached topK updated on every search — this is the actual cost of the design, and it's worth stating as a deliberate trade explicitly: writes (recording a search) become more expensive (touch every prefix node of the term, O(word length) nodes, each doing an O(K log K) re-sort), so that reads (autocomplete queries, which happen far more often — once per keystroke) become cheap, O(K) lookups. This read-heavy, write-amortized shape is exactly right for autocomplete, where a query happens on every keystroke and a search-completion event happens once per search.

Why per-node top-K beats re-ranking at query time, and what it costs

Real-time popularity updates create a staleness/cost trade the design has to name. Updating every ancestor node's top-K on every single search event, synchronously is correct but potentially expensive at very high query volume — a real system often batches popularity updates (aggregate counts over a short window, then update the trie's cached top-K periodically) rather than updating on every individual search, trading a small amount of ranking staleness for a much lower write amplification. Naming this as a deliberate choice, not an oversight, is what separates a considered design from one that just happens to work at low volume.

Cold-start for a brand-new term with zero search history is a real, nameable gap — a genuinely novel search term won't appear in any node's cached top-K until it accumulates enough score to displace an existing entry, which means a new but increasingly popular term can be invisible in autocomplete for a period even as real users start searching for it. This is the same cold-start problem the feed-ranking exercise elsewhere in this track names for new content, applied to search terms instead of posts.

Follow-ups they will ask

"Add typo tolerance — the user types 'gogle' and should still see 'google' suggested." Name this as a genuinely different retrieval problem, not a small addition to the trie: exact-prefix matching via a trie doesn't tolerate character-level edits at all, and fuzzy matching needs a different structure entirely (a BK-tree indexed by edit distance, or precomputed common-typo mappings) layered alongside, not inside, the prefix trie.

"Personalize suggestions per user — a user's own search history should influence their ranking." This can't live in the shared per-node topK cache, because that cache is global by construction — personalization needs either a per-user re-ranking pass applied to the global top-K candidates (cheap, approximate) or a separate per-user signal blended into the score at query time, and naming that global caching and personalization are in tension (the whole point of caching was avoiding per-query computation) is the honest trade to raise.

"The trie for a large vocabulary doesn't fit in memory on one machine." This forces sharding the trie itself — commonly by first character or a hash of the prefix — and getSuggestions for a prefix becomes a single-shard lookup (the prefix determines which shard owns it), while a fully generic "any prefix, any shard" design would need a routing layer that knows the sharding scheme, the same shard-ownership-by-key principle as the consistent-hashing material elsewhere in this track.

How to say it in the interview

"A trie gets me every word under a prefix, but the prompt asks for the top K by popularity, not all of them, and re-collecting and re-sorting every completion on every keystroke is too slow for something that has to feel instant - so the real design decision is precomputing and caching the top K at every trie node, and deciding how that cache gets updated as popularity changes without becoming stale."

Checklist

Distinguished 'all completions exist' (what a trie gives) from 'top K by popularity' (what's actually asked)
Precomputed and cached each node's top K rather than ranking fresh at query time
Propagated a search-completion event's score update through every prefix node the term passes through
Named the read-heavy, write-amortized trade explicitly as the right shape for this access pattern
Proposed batching popularity updates rather than updating every ancestor synchronously on every search
Named cold-start for a brand-new, increasingly popular term as a real, visible gap
Named typo-tolerance as a genuinely different retrieval problem, not a small trie extension
Sharded the trie by prefix/first-character when it doesn't fit one machine

Practice this interactively