Basics
The idea behind the pattern, why it is correct, and the clues in a question that point to it.
1.1Core idea
What the pattern does, in plain words.
Each node is a Map of next characters plus an end-of-word flag. Inserting or searching a word costs its length, independent of how many words are stored.
A trie stores words character by character along shared paths, so all words with the same prefix share the same first nodes. Looking up a prefix costs its length, however many words are stored.
Typical cost: O(L) per insert or lookup, O(total characters) space
1.2Recognition signals
If a question has one of these clues, try this pattern first.
Question
A classic interview problem from this family. Read it carefully and plan the approach before writing any code.
2.1Search Suggestions System
The problem statement, then the plan you would say out loud.
After each typed character, return up to three products with that prefix, alphabetically.
Plan before you code
- Sort products once.
- For each prefix, binary search the first match and take up to three that still match.
- A trie works too; sorting + binary search is shorter in an interview.
Detailed answer
First the reusable template, then the worked solution built from it and a walk through it one step at a time.
3.1Template
Memorise this shape. Most problems in this family are this code plus one twist.
Insert and prefix search
1class TrieNode {2 children = new Map<string, TrieNode>();3 end = false;4}5 6class Trie {7 root = new TrieNode();8 insert(word: string): void {9 let node = this.root;10 for (const ch of word) {11 if (!node.children.has(ch)) node.children.set(ch, new TrieNode());12 node = node.children.get(ch)!;13 }14 node.end = true;15 }16 startsWith(prefix: string): boolean {17 let node = this.root;18 for (const ch of prefix) {19 const next = node.children.get(ch);20 if (!next) return false;21 node = next;22 }23 return true;24 }25}1class TrieNode {2 val children = HashMap<Char, TrieNode>()3 var end = false4}5 6class Trie {7 private val root = TrieNode()8 9 fun insert(word: String) {10 var node = root11 for (ch in word) node = node.children.getOrPut(ch) { TrieNode() }12 node.end = true13 }14 15 fun startsWith(prefix: String): Boolean {16 var node = root17 for (ch in prefix) node = node.children[ch] ?: return false18 return true19 }20}1class TrieNode {2 Map<Character, TrieNode> children = new HashMap<>();3 boolean end = false;4}5 6class Trie {7 TrieNode root = new TrieNode();8 9 void insert(String word) {10 TrieNode node = root;11 for (char ch : word.toCharArray()) {12 node = node.children.computeIfAbsent(ch, c -> new TrieNode());13 }14 node.end = true;15 }16 17 boolean startsWith(String prefix) {18 TrieNode node = root;19 for (char ch : prefix.toCharArray()) {20 node = node.children.get(ch);21 if (node == null) return false;22 }23 return true;24 }25}- The root is an empty node; each node maps a character to its child.
- Walk or create one node per character, then mark the end of the word.
- A prefix exists if every character has a node.
3.2Solution
Strict TypeScript, type-checked and tested.
Search Suggestions System
1function suggestedProducts(products: string[], word: string): string[][] {2 products.sort();3 const out: string[][] = [];4 let prefix = "";5 for (const ch of word) {6 prefix += ch;7 let lo = 0, hi = products.length; // first product >= prefix8 while (lo < hi) {9 const mid = (lo + hi) >> 1;10 if (products[mid] < prefix) lo = mid + 1;11 else hi = mid;12 }13 out.push(products.slice(lo, lo + 3).filter((p) => p.startsWith(prefix)));14 }15 return out;16}1fun suggestedProducts(products: Array<String>, word: String): List<List<String>> {2 products.sort()3 val out = mutableListOf<List<String>>()4 var prefix = ""5 for (ch in word) {6 prefix += ch7 var lo = 08 var hi = products.size // first product >= prefix9 while (lo < hi) {10 val mid = (lo + hi) ushr 111 if (products[mid] < prefix) lo = mid + 112 else hi = mid13 }14 out.add(products.slice(lo until minOf(lo + 3, products.size)).filter { it.startsWith(prefix) })15 }16 return out17}1static List<List<String>> suggestedProducts(String[] products, String word) {2 Arrays.sort(products);3 List<List<String>> out = new ArrayList<>();4 StringBuilder prefix = new StringBuilder();5 for (char ch : word.toCharArray()) {6 prefix.append(ch);7 String p = prefix.toString();8 int lo = 0, hi = products.length; // first product >= prefix9 while (lo < hi) {10 int mid = (lo + hi) >>> 1;11 if (products[mid].compareTo(p) < 0) lo = mid + 1;12 else hi = mid;13 }14 List<String> hits = new ArrayList<>();15 for (int i = lo; i < Math.min(lo + 3, products.length); i++) {16 if (products[i].startsWith(p)) hits.add(products[i]);17 }18 out.add(hits);19 }20 return out;21}Step by step
- Sort once: words sharing a prefix sit together.
- Binary search the first word ≥ the prefix.
- Take up to three that still match.
Complexity: O(n log n + L log n) time
Q&A
What interviewers ask once your code works, and problems to try on your own.
4.1Interview questions
Answer out loud, then open.
Trie or hash set?
How much memory does it use?
How do you return the top suggestions quickly?
4.2Solo practice
Try these without looking; open the hint only when stuck.
Hint
Walk each word until you hit an end flag.
Extra depth
More fully worked problems in the same family, and the mistakes that cost offers.
5.12 more worked problems
Each one: the problem, the plan, the code and its cost.
Show detailsHide details
Implement Trie
Support insert, search (whole word) and startsWith.
- Nested dicts, one level per character.
- A '$' key marks the end of a word.
- search and startsWith share one walk.
1class TrieNode {2 children = new Map<string, TrieNode>();3 end = false;4}5 6class Trie {7 private root = new TrieNode();8 insert(word: string): void {9 let node = this.root;10 for (const ch of word) {11 if (!node.children.has(ch)) node.children.set(ch, new TrieNode());12 node = node.children.get(ch)!;13 }14 node.end = true;15 }16 private walk(s: string): TrieNode | null {17 let node: TrieNode | undefined = this.root;18 for (const ch of s) {19 node = node.children.get(ch);20 if (!node) return null;21 }22 return node;23 }24 search(word: string): boolean {25 return this.walk(word)?.end === true;26 }27 startsWith(prefix: string): boolean {28 return this.walk(prefix) !== null;29 }30}Complexity: O(L) per operation
Word Search II
Find every dictionary word that can be traced in a letter grid.
- Build a trie of the words.
- DFS from every cell, following trie edges only.
- Remove found words and dead branches to prune later searches.
1type WordNode = { kids: Map<string, WordNode>; word?: string };2 3function findWords(board: string[][], words: string[]): string[] {4 const root: WordNode = { kids: new Map() };5 for (const w of words) {6 let node = root;7 for (const ch of w) {8 if (!node.kids.has(ch)) node.kids.set(ch, { kids: new Map() });9 node = node.kids.get(ch)!;10 }11 node.word = w;12 }13 const rows = board.length, cols = board[0].length, found: string[] = [];14 const dfs = (r: number, c: number, parent: WordNode): void => {15 const ch = board[r][c];16 const node = parent.kids.get(ch);17 if (!node) return;18 if (node.word !== undefined) {19 found.push(node.word);20 node.word = undefined; // collect each word once21 }22 board[r][c] = "#";23 for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {24 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== "#") dfs(nr, nc, node);25 }26 board[r][c] = ch;27 if (node.kids.size === 0 && node.word === undefined) parent.kids.delete(ch);28 };29 for (let r = 0; r < rows; r++) {30 for (let c = 0; c < cols; c++) dfs(r, c, root);31 }32 return found;33}Complexity: O(cells · 4^L) worst case; pruning makes it fast in practice
5.2Traps
Bugs and misreadings that come up again and again with this pattern.
Show detailsHide details
- Forgetting the end-of-word marker
- Rebuilding the trie per query