Design the data structure behind a search box's autocomplete. Why a trie, and when would you not use one?

Settle the access pattern first

Autocomplete is not one operation, and which one you are being asked for decides the structure. "Does this exact term exist" is a lookup. "Give me every term starting with str" is a range enumeration. "Give me the ten most searched terms starting with str, in under twenty milliseconds, while the dictionary is rebuilt nightly" is the real requirement, and it contains three constraints a lookup structure does not address: ordering, truncation, and whether writes happen at all.

Ask before you draw. Is the dictionary static between builds or mutated live? How large is the alphabet — twenty-six letters, or Unicode? Is ranking by frequency, by recency, or personalised? Each of those answers eliminates a candidate structure, and eliminating structures out loud is most of what is being scored.

The trie itself

A trie spends one node per character position, with the edges labelled by character, so a path from the root spells a prefix and the node at its end owns every term extending it. Finding the node for a prefix of length k costs k steps and does not depend on how many terms the dictionary holds. Terms sharing a prefix share the path, which is where the structure earns its name and its only real advantage.

class TrieNode {
    // 26 references per node is the central memory decision, not a detail.
    final TrieNode[] next = new TrieNode[26];
    boolean terminal;
    // Best completions for this subtree, precomputed so a query never walks it.
    final List<String> top = new ArrayList<>();
}

The top list is what makes the structure usable, and it is worth writing before anyone asks. Insert the dictionary in descending order of popularity, and push each term into the top list of every node along its path until that list holds k entries. The first k terms to reach a node are, by construction, its k most popular completions.

static void insert(TrieNode root, String word, int k) {
    TrieNode node = root;
    for (int i = 0; i < word.length(); i++) {
        int c = word.charAt(i) - 'a';
        if (node.next[c] == null) {
            node.next[c] = new TrieNode();
        }
        node = node.next[c];
        if (node.top.size() < k) {   // words arrive most-popular-first
            node.top.add(word);
        }
    }
    node.terminal = true;
}

A query is now k pointer hops and one list read: O(k + result size), independent of dictionary size. Without the cached list, a query walks the entire subtree, which for the prefix a means visiting a substantial fraction of the whole dictionary on every keystroke. That is the difference between a structure that works and one that only works in the examples you tested.

What it costs, from stated assumptions

Take a million terms averaging twenty characters over a twenty-six-letter alphabet. The characters themselves are about twenty megabytes. Prefix sharing collapses the node count well below the twenty million characters — the early levels are shared by almost everything — but the tail of each term is usually unique, so suppose you end up with something on the order of eight million nodes.

Each of those nodes carries a twenty-six-slot reference array. On a JVM with compressed references that array alone is over a hundred bytes, before the object header, the boolean, and the cached list. Eight million of them is comfortably into the hundreds of megabytes, for twenty megabytes of strings. The numbers depend entirely on the assumptions above, and the point of deriving them is not the total: it is that a trie's memory is dominated by empty pointer slots in nodes that have one or two children.

The standard mitigations are worth naming. A HashMap<Character, TrieNode> per node pays per-entry overhead instead of per-alphabet-slot waste, which wins for sparse nodes and loses for dense ones. A radix or PATRICIA tree merges each non-branching chain into a single node holding a string, which typically removes most of the nodes in a dictionary of natural-language words. And a minimal-acyclic-automaton representation shares common suffixes as well as prefixes, at the cost of no longer being able to attach per-term data to a node or to mutate the structure.

Where a hash map is simply better

The claim to be careful with is that a trie gives faster lookup. It does not. Hashing a k-character key also reads all k characters, and then the map performs one probe into a contiguous array. The trie performs k dependent pointer dereferences into nodes scattered across the heap, and each one is a potential cache miss that the previous one had to complete before it could be issued. For exact membership, a hash set is faster in practice and vastly smaller.

You can even serve autocomplete from a hash map, by keying every prefix directly to its precomputed top-k list. With the assumptions above that is twenty million keys, so it costs more memory than the trie, but every query becomes one probe with no traversal at all. That is a legitimate design for a hot, small, read-only dictionary, and offering it shows you are choosing rather than reciting.

Where a sorted array beats both

If the dictionary is rebuilt in batch and never mutated between builds, the strongest answer is often not a tree at all. Sort the terms once. Every prefix then occupies a contiguous range, so a binary search finds the range's start in O(log n) and you scan forward while the prefix still matches.

static List<String> complete(String[] sorted, String prefix, int k) {
    int lo = 0, hi = sorted.length;
    while (lo < hi) {                       // lower bound: first index >= prefix
        int mid = (lo + hi) >>> 1;
        if (sorted[mid].compareTo(prefix) < 0) lo = mid + 1; else hi = mid;
    }
    List<String> out = new ArrayList<>();
    // One forward scan over contiguous memory - no pointer chasing at all.
    while (lo < sorted.length && out.size() < k && sorted[lo].startsWith(prefix)) {
        out.add(sorted[lo]);
        lo++;
    }
    return out;
}

If you need ordering and mutation, a NavigableSet such as TreeSet gives the same prefix range through ceiling and subSet in O(log n), trading the array's locality for the ability to insert.

This holds the strings and nothing else, it is trivially memory-mappable and shareable between processes, and its scan is the most cache-friendly access pattern available. What it gives up is cheap insertion and deletion, and ranking within the prefix range — the scan returns terms in lexicographic order, so getting the most popular ten means examining the whole range or storing a precomputed ranked list alongside it. That trade is exactly the one the interview is about: the trie buys you incremental mutation and per-node precomputation, and you pay for both in memory and locality whether or not you use them.

How to close the answer

Give a recommendation, not a survey. For a nightly-rebuilt dictionary serving prefix queries, a sorted array plus precomputed ranked lists for short prefixes is the smallest thing that meets the requirement. For a dictionary mutated continuously — a user's own history, a live catalogue — the trie's cheap insertion is worth its memory, and a radix variant recovers most of it. For exact-match lookup, use a hash set and say so.

The trie's advantage is not lookup speed, it is that a prefix is a place you can stand and precompute from; if nothing in your requirement needs that place, a sorted array and a binary search will beat it on both memory and cache behaviour.