Trie Interview Patterns: Autocomplete, Word Search, and Prefix Problems (2025)

By /

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 (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

Scroll to Top