# Advanced Trie Interview Patterns: Word Search, Autocomplete, and XOR Maximum (2025)

Source: https://www.techinterview.org/post/3233466455/tries-advanced-patterns/
Updated: 2026-04-17 · techinterview.org

## Trie Fundamentals and Implementation

A trie (prefix tree) stores strings character by character, sharing prefixes among strings. Each node represents one character; the path from root to a node spells a prefix. A node marked as end_of_word indicates a complete word ends there. Time complexity: insert, search, startsWith — all O(L) where L is the string length. Space: O(total characters across all words) — efficient when many strings share prefixes. Use cases: autocomplete (find all words with a prefix), spell checking, IP routing (longest prefix match), word search in a grid, XOR maximum (binary trie).


```
class TrieNode:
    def __init__(self):
        self.children = {}  # char -> TrieNode
        self.is_end = False
        self.count = 0  # how many words pass through this node

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
            node.count += 1
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix: str) -> bool:
        return self._find(prefix) is not None

    def _find(self, prefix: str):
        node = self.root
        for c in prefix:
            if c not in node.children:
                return None
            node = node.children[c]
        return node
```


## Word Search II (LC 212) — DFS + Trie

Find all words in a 2D grid. Naive: run DFS from each cell for each word. With Trie: insert all words into a trie. DFS from each cell, following the trie — prune when no trie path matches. Pruning: when a trie node has no children, no word can extend from this path.


```
def find_words(board: list[list[str]], words: list[str]) -> list[str]:
    trie = Trie()
    for w in words:
        trie.insert(w)

    rows, cols = len(board), len(board[0])
    result = set()

    def dfs(node, r, c, path):
        if node.is_end:
            result.add(path)
        board[r][c], temp = '#', board[r][c]  # mark visited
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                ch = board[nr][nc]
                if ch != '#' and ch in node.children:
                    dfs(node.children[ch], nr, nc, path + ch)
        board[r][c] = temp  # restore

    for r in range(rows):
        for c in range(cols):
            ch = board[r][c]
            if ch in trie.root.children:
                dfs(trie.root.children[ch], r, c, ch)
    return list(result)
```


## Design Search Autocomplete System (LC 642)

Each trie node stores the top-3 hottest sentences (by frequency) that pass through it. On insert: update frequencies, propagate top-3 up the trie. On search prefix: traverse to the prefix node, return its stored top-3.


```
import heapq

class AutocompleteSystem:
    def __init__(self, sentences: list[str], times: list[int]):
        self.root = TrieNode()
        self.freq = {}
        self.prefix = ""
        for s, t in zip(sentences, times):
            self.freq[s] = t
            self._add(s, t)

    def _add(self, sentence: str, freq: int):
        node = self.root
        for c in sentence:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
            # Maintain top-3 by frequency
            node.top = sorted(
                set(node.top + [(freq, sentence)]),
                key=lambda x: (-x[0], x[1])
            )[:3]

    def input(self, c: str) -> list[str]:
        if c == '#':
            self.freq[self.prefix] = self.freq.get(self.prefix, 0) + 1
            self._add(self.prefix, self.freq[self.prefix])
            self.prefix = ""
            return []
        self.prefix += c
        node = self.root
        for ch in self.prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]
        return [s for _, s in node.top]
```


## XOR Maximum with Binary Trie (LC 421)

Maximum XOR of two numbers in an array. Insert all numbers into a binary trie (bit by bit, from MSB to LSB). For each number, greedily find the number in the trie that maximizes XOR (always try to take the opposite bit).


```
def find_maximum_xor(nums: list[int]) -> int:
    # Build binary trie
    root = [None, None]  # [bit=0 child, bit=1 child]
    for n in nums:
        node = root
        for i in range(31, -1, -1):
            bit = (n >> i) & 1
            if node[bit] is None:
                node[bit] = [None, None]
            node = node[bit]

    max_xor = 0
    for n in nums:
        node = root
        curr_xor = 0
        for i in range(31, -1, -1):
            bit = (n >> i) & 1
            want = 1 - bit  # prefer opposite bit for max XOR
            if node[want] is not None:
                curr_xor |= (1 << i)
                node = node[want]
            else:
                node = node[bit]
        max_xor = max(max_xor, curr_xor)
    return max_xor
```


See also: [Meta Interview Prep](https://techinterview.org/meta/)

See also: [Atlassian Interview Prep](https://techinterview.org/atlassian/)

See also: [Databricks Interview Prep](https://techinterview.org/databricks/)