# Trie Interview Patterns: Autocomplete, Word Search, and Prefix Problems (2025) Source: https://www.techinterview.org/post/3233463531/trie-interview-patterns-autocomplete/ Updated: 2026-05-02 ยท techinterview.org ## Trie Interview Patterns: Autocomplete, Word Search, and Prefix Problems (2025) Tries (prefix trees) are the go-to data structure for string prefix problems, autocomplete systems, and dictionary lookups. They appear in Google, Meta, Amazon, and Microsoft interviews for both coding and system design rounds. ## Core Trie Implementation ``` class TrieNode: def __init__(self): self.children = {} # char -> TrieNode self.is_end = False # marks end of a word self.count = 0 # number of words with this prefix (optional) self.word = None # store word at leaf (optional) class Trie: def __init__(self): self.root = TrieNode() def insert(self, word): node = self.root for c in word: if c not in node.children: node.children[c] = TrieNode() node = node.children[c] node.count += 1 # track prefix count node.is_end = True node.word = word def search(self, word): node = self._find(word) return node is not None and node.is_end def starts_with(self, prefix): return self._find(prefix) is not None def _find(self, prefix): node = self.root for c in prefix: if c not in node.children: return None node = node.children[c] return node # Time: O(m) insert/search/prefix where m = word length # Space: O(ALPHABET_SIZE * m * n) worst case ``` ## Pattern 1: Autocomplete (Top-K with Trie) ``` # Return top-3 search suggestions for each prefix # LeetCode 1268 - Search Suggestions System def suggestedProducts(products, searchWord): products.sort() # sort lexicographically result = [] prefix = "" left, right = 0, len(products) - 1 for c in searchWord: prefix += c # Binary search: find left bound while left <= right and (len(products[left]) < len(prefix) or products[left][:len(prefix)] != prefix): left += 1 # Find right bound while left <= right and (len(products[right]) < len(prefix) or products[right][:len(prefix)] != prefix): right -= 1 result.append(products[left:min(left+3, right+1)]) return result # Alternative: build Trie, at each node store top-3 words (by frequency) # Update top-3 on insert: O(m * k) per insert, O(m) per query ``` ## Pattern 2: [Word Search II](https://www.techinterview.org/post/3233474786/word-search-ii-trie-pattern-recognition/) (Trie + DFS) ``` # Find all words from dictionary that exist in grid # LeetCode 212 - Word Search II def findWords(board, words): trie = Trie() for w in words: trie.insert(w) m, n = len(board), len(board[0]) result = set() def dfs(node, i, j): c = board[i][j] if c not in node.children: return next_node = node.children[c] if next_node.word: result.add(next_node.word) next_node.word = None # avoid duplicates, prune board[i][j] = '#' # mark visited for di, dj in [(0,1),(0,-1),(1,0),(-1,0)]: ni, nj = i+di, j+dj if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '#': dfs(next_node, ni, nj) board[i][j] = c # restore for i in range(m): for j in range(n): dfs(trie.root, i, j) return list(result) ``` ## Pattern 3: Replace Words (Trie + Sentence) ``` # Replace words in sentence with shortest root from dictionary # LeetCode 648 def replaceWords(dictionary, sentence): trie = Trie() for root in dictionary: trie.insert(root) def find_root(word): node = trie.root for i, c in enumerate(word): if c not in node.children: return word # no root found, use full word node = node.children[c] if node.is_end: return word[:i+1] # return shortest root return word return ' '.join(find_root(w) for w in sentence.split()) ``` ## Pattern 4: Word Break (Trie + DP) ``` # Can string be segmented into dictionary words? # LeetCode 139 def wordBreak(s, wordDict): trie = Trie() for w in wordDict: trie.insert(w) n = len(s) dp = [False] * (n + 1) dp[0] = True # empty string for i in range(n): if not dp[i]: continue node = trie.root for j in range(i, n): if s[j] not in node.children: break node = node.children[s[j]] if node.is_end: dp[j+1] = True return dp[n] ``` ## Pattern 5: XOR Maximum Pair (Binary Trie) ``` # Maximum XOR of two numbers in array - LeetCode 421 # Build binary trie (on bits), for each number find complement in trie def findMaximumXOR(nums): root = {} for num in nums: node = root for i in range(31, -1, -1): bit = (num >> i) & 1 if bit not in node: node[bit] = {} node = node[bit] max_xor = 0 for num in nums: node = root curr_xor = 0 for i in range(31, -1, -1): bit = (num >> i) & 1 want = 1 - bit # prefer opposite bit for max XOR if want in node: curr_xor = (curr_xor << 1) | 1 node = node[want] else: curr_xor = curr_xor << 1 node = node[bit] max_xor = max(max_xor, curr_xor) return max_xor ``` ## Trie Optimizations - **Compressed trie (Patricia trie)**: merge chains of single-child nodes into one node. Reduces node count drastically for sparse tries. Used in routing tables and text editors. - **Array children vs dict**: if alphabet is fixed (a-z), use `children = [None] * 26` and index by `ord(c) - ord('a')`. Faster than dict, fixed memory per node. - **Top-K at each node**: store top-K completions sorted by frequency at each node. O(m) autocomplete at cost of O(K) extra space per node. - **Lazy deletion**: mark deleted words with is_end=False rather than removing nodes. Clean up with background sweep. ## Key Problems - LeetCode 208 - Implement Trie - LeetCode 211 - Design Add and Search Words Data Structure (wildcard '.') - LeetCode 212 - Word Search II (Trie + DFS) - LeetCode 421 - Maximum XOR of Two Numbers (binary trie) - LeetCode 648 - Replace Words - LeetCode 1268 - Search Suggestions System (autocomplete) - LeetCode 720 - Longest Word in Dictionary