A merchant-onboarding console checks SKU stems as ops types. pay might already be a live code, or only the start of payload. Staging kept every code in a HashSet; exact search was a lookup. startsWith still scanned every stored key. A few hundred codes in the sandbox tenant returned in milliseconds. The live catalog made every keystroke a full pass, and the typeahead timed out.

Implement a prefix tree with insert, exact search, and prefix check. This is an interview writeup, not a sharing lecture. A trie already gives the layout: a node is children plus an end mark. Java does not ship java.util.Trie. Here we only care about walking characters, creating missing edges, and asking the end mark on exact search. Cost tracks key length L, not how many keys you stored.

The problem

Build a class that stores lowercase words: insert(word) adds it, search(word) is true only if that exact word was inserted, and startsWith(prefix) is true if some inserted word begins with that prefix. Keep those three names — this prompt is not the tutorial’s contains / hasPrefix API.

insert("code")
insert("coder")
search("code")        →  true
search("cod")         →  false
startsWith("cod")     →  true
search("coder")       →  true
startsWith("codex")   →  false
insert("cod")
search("cod")         →  true

Note: ca is a prefix of cat, not a word, unless ca was also inserted. search reads the end mark; startsWith only needs the node to exist.

A HashSet of whole words is the honest brute force

Store every inserted string in a HashSet: search is contains, while startsWith still walks every stored key. Exact lookup is cheap. Prefix still pays the catalog size n.

class TrieSet {
    final Set<String> words = new HashSet<>();

    void insert(String word) {
        words.add(word);
    }

    boolean search(String word) {
        return words.contains(word);
    }

    boolean startsWith(String prefix) {
        for (String w : words) {
            if (w.startsWith(prefix)) {
                return true;
            }
        }
        return false;
    }
}

At a few hundred SKUs this is a rounding error. At a live catalog you paid a scan of n for a question a character walk answers in time that depends on the key, not the catalog: does this path already exist, and did a word end here?

Walk characters, create missing edges, mark the last node

An inner Node holds Node[] children = new Node[26] and boolean endOfWord. Index is c - 'a'; a null slot means no edge. Insert walks one character at a time, allocates a node when the slot is empty, and marks endOfWord on the last node.

insert("code")
  create c → o → d → e    mark e

insert("coder")
  reuse c → o → d → e     create r, mark r

search("cod")
  walk to d; end mark off → false

startsWith("cod")
  node d exists → true

insert("cod")
  reuse c → o → d         mark d

search("cod")             → true

The Java is that class. walk returns the node for a string, or null when an edge is missing. search reads the end mark; startsWith only needs the node to exist.

class Trie {
    static final class Node {
        final Node[] children = new Node[26];
        boolean endOfWord;
    }

    final Node root = new Node();

    void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Node();
            }
            node = node.children[idx];
        }
        node.endOfWord = true;
    }

    boolean search(String word) {
        Node node = walk(word);
        return node != null && node.endOfWord;
    }

    boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }

    Node walk(String s) {
        Node node = root;
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            node = node.children[idx];
            if (node == null) {
                return null;
            }
        }
        return node;
    }
}

Time is O(L) per operation — one step per character of that key, independent of how many words you already stored. Space is the nodes you allocated — one per distinct prefix along inserted keys. A recursive walk of a million-character key is a million frames; the iterative walk above is the same bound without blowing the JVM stack. Do not re-lecture prefix sharing or the map-versus-array shopping list at the board unless they ask; the trie post already owns both.

Note: Inserting a word that is already present only sets the end mark again. It does not allocate a second path.

What interviewers usually poke next

  • Delete. Clearing endOfWord unmarks a word and leaves longer keys intact — after insert("code") then insert("coder"), unmarking "code" still lets startsWith("code") succeed. Pruning nodes that have no children and no end mark is optional cleanup, not the default.
  • Unicode, mixed case, punctuation. Node[26] is for a–z. A Map of children is the honest default for a wider alphabet — the trie post owns that choice; do not paste a second class here.
  • Longest Common Prefix. Shared prefix of a list of strings is a column walk. It does not need a trie.
  • Word Break. Segment s with a dictionary. The default is DP plus a set. A trie of the dict is a follow-up on that prompt, not a second file.
  • Add and Search Words. Same insert; search treats . as any letter.
  • Search Suggestions. Walk the prefix; each node already holds three lex-smallest hits. Query does not DFS the subtree.

You are done with this problem when you can say, out loud, why the HashSet is correct for search and too slow for startsWith, why search reads the end mark, and why a recursive walk of a huge key is a stack of frames you did not need.