Lesson 45Advanced1hAssessment-backed

Trie and Prefix Systems

Build prefix-aware lookup for autocomplete, command palettes, dictionaries, URL routing, and search suggestions.

What you will be able to do

Explain why prefix search needs structure beyond hash lookup.

Implement insert and prefix lookup in a trie.

Connect trie design to autocomplete, command palettes, routing, and dictionaries.

Compare trie memory cost with sorted arrays and hash maps.

Handle normalization, ranking, and product limits in prefix systems.

A hash map can answer exact lookup. A trie answers prefix intent: what completions are possible from this partial input?

Prefix Intent

A trie stores shared prefixes once. Each edge represents a character or token, and each node represents the prefix formed by the path from the root.

Shared prefixes make autocomplete and prefix validation direct.

Scenario: Command Palette

A developer tool command palette needs fast suggestions as the user types. Exact lookup cannot answer 'all commands beginning with deploy'. A trie can find the prefix node, then collect ranked candidates below it.

Need	Structure	Trade-off
Exact key lookup	Hash map	Fast exact match, no prefix traversal.
Prefix suggestions	Trie	Fast prefix path, higher memory.
Sorted suggestions	Sorted array + binary search	Simple and compact, updates cost more.
Ranked search	Trie + top-k metadata	Faster reads, harder updates.

Autocomplete flow using prefix node and ranked candidates — Production autocomplete usually combines prefix lookup with ranking metadata.

Same Pattern in Java, Python, and JavaScript

Implement a trie that supports word insertion and prefix lookup.

import java.util.*;

class Trie {
    static class Node { Map<Character, Node> child = new HashMap<>(); boolean word; }
    private final Node root = new Node();
    void insert(String word) {
        Node cur = root;
        for (char ch : word.toCharArray()) cur = cur.child.computeIfAbsent(ch, k -> new Node());
        cur.word = true;
    }
    boolean startsWith(String prefix) { return node(prefix) != null; }
    boolean search(String word) { Node n = node(word); return n != null && n.word; }
    private Node node(String s) { Node cur = root; for (char ch : s.toCharArray()) { cur = cur.child.get(ch); if (cur == null) return null; } return cur; }
}

Assessment trap

A trie is not automatically better than a sorted array. Mention update frequency, alphabet size, normalization, ranking, and memory.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

Implement insert, search, and startsWith.
Return up to three lexicographically smallest product suggestions for each search prefix.
Support addWord and search where '.' matches any one character.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Example	Brute-force approach	Stronger solution	Production notes
Command palette	Filter every command string on each keystroke.	Use trie or sorted-prefix lookup for prefix navigation.	Ranking and keyboard latency matter.
API route matching	Scan every registered route.	Use token trie/radix tree for path segments.	Dynamic params and precedence must be explicit.
Dictionary validation	Hash full words only.	Trie enables prefix pruning during board/search traversal.	Memory can dominate for large alphabets.

Solved modelInterview Question Solutions

Question 1: Implement Trie

Implement insert, search, and startsWith. Walk one character per level. A terminal marker distinguishes a full word from a prefix.

import java.util.*;

class Trie {
    static class Node { Map<Character, Node> child = new HashMap<>(); boolean word; }
    private final Node root = new Node();
    void insert(String word) {
        Node cur = root;
        for (char ch : word.toCharArray()) cur = cur.child.computeIfAbsent(ch, k -> new Node());
        cur.word = true;
    }
    boolean startsWith(String prefix) { return node(prefix) != null; }
    boolean search(String word) { Node n = node(word); return n != null && n.word; }
    private Node node(String s) { Node cur = root; for (char ch : s.toCharArray()) { cur = cur.child.get(ch); if (cur == null) return null; } return cur; }
}

Question 2: Search Suggestions System

Return up to three lexicographically smallest product suggestions for each search prefix. Sort products once, then binary-search the prefix range for each typed prefix. This is often simpler than a trie for static catalogs.

import java.util.*;
class Suggestions { static List<List<String>> suggestedProducts(String[] products, String searchWord) { Arrays.sort(products); List<List<String>> ans = new ArrayList<>(); String prefix = ""; int start = 0; for (char ch : searchWord.toCharArray()) { prefix += ch; start = lowerBound(products, prefix, start); List<String> cur = new ArrayList<>(); for (int i = start; i < products.length && cur.size() < 3 && products[i].startsWith(prefix); i++) cur.add(products[i]); ans.add(cur); } return ans; } static int lowerBound(String[] a, String target, int lo) { int hi = a.length; while (lo < hi) { int mid = (lo + hi) / 2; if (a[mid].compareTo(target) < 0) lo = mid + 1; else hi = mid; } return lo; } }

Question 3: Word Dictionary With Wildcard

Support addWord and search where '.' matches any one character. Trie search becomes DFS only at wildcard positions. Non-wildcard characters still follow one edge.

import java.util.*;
class WordDictionary { static class Node { Map<Character, Node> child = new HashMap<>(); boolean word; } Node root = new Node(); void addWord(String w) { Node cur = root; for (char ch : w.toCharArray()) cur = cur.child.computeIfAbsent(ch, k -> new Node()); cur.word = true; } boolean search(String w) { return dfs(w, 0, root); } boolean dfs(String w, int i, Node node) { if (i == w.length()) return node.word; char ch = w.charAt(i); if (ch != '.') return node.child.containsKey(ch) && dfs(w, i + 1, node.child.get(ch)); for (Node next : node.child.values()) if (dfs(w, i + 1, next)) return true; return false; } }

Solved modelWorked Interview Answer

Implement a trie with insert, exact search, and prefix search. The trie walks one character at a time, stores shared prefixes once, and uses a terminal marker to distinguish complete words from prefixes.

import java.util.*;

class Trie {
    static class Node { Map<Character, Node> child = new HashMap<>(); boolean word; }
    private final Node root = new Node();
    void insert(String word) {
        Node cur = root;
        for (char ch : word.toCharArray()) cur = cur.child.computeIfAbsent(ch, k -> new Node());
        cur.word = true;
    }
    boolean startsWith(String prefix) { return node(prefix) != null; }
    boolean search(String word) { Node n = node(word); return n != null && n.word; }
    private Node node(String s) { Node cur = root; for (char ch : s.toCharArray()) { cur = cur.child.get(ch); if (cur == null) return null; } return cur; }
}

Hands-on drillTry It Yourself

Practice task

Insert team, test, tea, and teach into a trie. Mark which nodes are full words and which are only prefixes.

Failure patternsCommon Mistakes to Avoid

Using hash map exact lookup for prefix suggestions.
Forgetting end-of-word markers.
Ignoring normalization and case folding.
Returning every descendant without ranking or limits.
Using trie despite tiny static data where sorting is simpler.

Execution guardrailQuick-Start Checklist

Normalize input.
Define node children.
Track end-of-word.
Walk prefix node.
Limit/rank collected results.
State memory trade-off.

Recall drillKnowledge Check

Question	Strong answer
Why is a trie useful?	It shares prefixes and can navigate by partial input.
Why need word marker?	A prefix node may not itself be a complete word.
What is the main trie cost?	Many nodes/maps can use more memory than compact arrays.

VocabularyKey Terms

Term	Meaning
Trie	Tree keyed by characters or tokens.
Prefix node	Node reached after reading a prefix.
Terminal marker	Flag that path is a complete key.
Autocomplete	Returning likely completions for a prefix.

Next practiceFurther Reading

Practice implement trie, search suggestions, word dictionary with wildcards, and word search II.
Compare tries with sorted arrays and inverted indexes.
Review string normalization.

Union Find

Segment Tree and Range Queries