What is a trie, and how would you code prefix autocomplete in Java?

Structure. The root is the empty string. Each node maps a character to a child and has a flag for "a word ends here". Insert walks the characters, creating nodes as needed. Prefix search walks the prefix, then collects words below that node.

Costs. Insert and lookup are proportional to the word length. Collecting K completions costs the prefix length plus the nodes visited, so stop as soon as you have K. Memory is the weakness: one object per character with a child map. Shared prefixes help; unrelated words do not.

import java.util.*;

public class Autocomplete {
    private static final class Node {
        final TreeMap<Character, Node> children = new TreeMap<>(); // sorted, so results come out in order
        boolean word;
    }
    private final Node root = new Node();

    void insert(String w) {
        Node n = root;
        for (char c : w.toLowerCase(Locale.ROOT).toCharArray()) n = n.children.computeIfAbsent(c, k -> new Node());
        n.word = true;
    }

    List<String> complete(String prefix, int k) {
        Node n = root;
        String p = prefix.toLowerCase(Locale.ROOT);
        for (char c : p.toCharArray()) {
            n = n.children.get(c);
            if (n == null) return List.of();              // no word has this prefix
        }
        List<String> out = new ArrayList<>();
        collect(n, new StringBuilder(p), k, out);
        return out;
    }

    private void collect(Node n, StringBuilder sb, int k, List<String> out) {
        if (out.size() == k) return;                       // stop early: O(prefix + visited nodes)
        if (n.word) out.add(sb.toString());
        for (var e : n.children.entrySet()) {
            sb.append(e.getKey());
            collect(e.getValue(), sb, k, out);
            sb.deleteCharAt(sb.length() - 1);
            if (out.size() == k) return;
        }
    }

    public static void main(String[] args) {
        var t = new Autocomplete();
        for (String w : List.of("sneaker", "sneakers", "snow boots", "sandals", "Sneaker socks")) t.insert(w);
        System.out.println(t.complete("sne", 2));          // [sneaker, sneaker socks]
        System.out.println(t.complete("x", 3));            // []
    }
}

Verified with OpenJDK 21.0.13: it prints [sneaker, sneaker socks] and []. Using a TreeMap for children returns completions in alphabetical order; a HashMap would be faster per step but unordered.

Follow-ups to expect.

• Ranking: real autocomplete returns the most popular completions, not alphabetical ones. Store the top K completions, by query frequency, at each node, and update them offline.
• Case and Unicode: normalise case with a fixed locale. char is a UTF-16 code unit, not a full code point; use codePoints() if the input can contain characters outside the Basic Multilingual Plane.
• Production: Lucene's suggesters and terms dictionary use finite-state transducers, which share both prefixes and suffixes in a compact byte array. See What is an FST?.

Alternate interview scenarios

"Design typeahead search for millions of queries per second." The trie is the data structure; the design is about never computing completions at request time.

• Precompute: aggregate query logs offline, or in a streaming job, into the top K completions for each prefix, ranked by frequency and freshness, and filter unsafe or zero-result queries.
• Serve from memory: load a prefix-to-top-K map, or a compact trie or FST, into every serving node; a lookup is one in-memory read. Elasticsearch's completion suggester follows the same idea: its docs say it uses data structures that "enable fast lookups, but are costly to build and are stored in-memory".
• Cache short prefixes: one- and two-character prefixes take most traffic and change slowly, so cache them at the edge or in the client with a short time to live. Debounce keystrokes in the client.
• Scale and freshness: replicate the read-only index widely, shard by prefix if it does not fit on one node, and rebuild periodically with a blue-green swap. Add a small real-time layer only if trending queries must appear within minutes.
• Per market and language: keep separate indexes per locale, which a multi-market shop needs anyway.