Trie (Prefix Tree) Interview Patterns: Autocomplete, Word Search, Wildcard

By /
⏱ 6 min read

Trie (Prefix Tree) Interview Patterns

A Trie (prefix tree) is a tree where each node represents a character in a string, and paths from root to leaf represent words. It enables prefix-based search in O(L) time (L = string length) regardless of dictionary size, making it ideal for autocomplete, spell checking, and IP routing.

  • Coinbase Interview Guide
  • Atlassian Interview Guide
  • Uber Interview Guide
  • LinkedIn Interview Guide
  • Apple Interview Guide
  • Meta Interview Guide

    • Basic Trie Implementation

    class TrieNode:
    def __init__(self):
        self.children = {}   # char → TrieNode
        self.is_end = False  # marks end of a word

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

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children: return False
            node = node.children[ch]
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children: return False
            node = node.children[ch]
        return True

    Time: O(L) for insert, search, and starts_with (L = length of word/prefix). Space: O(total characters across all inserted words). The dict-based children supports arbitrary alphabets; use a fixed array [None]*26 for lowercase English only (faster lookups).

    Pattern 1: Autocomplete with Top-K Cache

    class AutocompleteNode:
    def __init__(self):
        self.children = {}
        self.top_k = []  # cached top-K suggestions for this prefix

    def update_top_k(self, word, score, k=10):
        self.top_k.append((score, word))
        self.top_k.sort(reverse=True)
        self.top_k = self.top_k[:k]

def get_suggestions(root, prefix):
    node = root
    for ch in prefix:
        if ch not in node.children: return []
        node = node.children[ch]
    return [word for _, word in node.top_k]

    Each node caches the top-K most popular words with the given prefix. Lookup is O(L) — traverse to the prefix node, return cached results. Update on insert propagates scores up to ancestors, O(L * K log K).

    Pattern 2: Word Search II (Multiple Words)

    def find_words(board, words):
    trie = Trie()
    for w in words: trie.insert(w)
    result = set()
    rows, cols = len(board), len(board[0])

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

    for r in range(rows):
        for c in range(cols):
            dfs(trie.root, r, c, '')
    return list(result)

    Using a Trie instead of a set for word lookup lets us prune the DFS early: if the current path prefix is not in the Trie, stop immediately. This is significantly faster than checking each word individually for large word lists.

    Pattern 3: Replace Words (Prefix Replacement)

    def replace_words(dictionary, sentence):
    trie = Trie()
    for root_word in dictionary:
        trie.insert(root_word)

    def find_root(word):
        node = trie.root
        for i, ch in enumerate(word):
            if node.is_end: return word[:i]
            if ch not in node.children: return word
            node = node.children[ch]
        return word

    return ' '.join(find_root(w) for w in sentence.split())

    Pattern 4: Design Add and Search Words (Wildcard)

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

    def add_word(self, word):
        node = self.root
        for ch in word:
            node.children.setdefault(ch, TrieNode())
            node = node.children[ch]
        node.is_end = True

    def search(self, word):
        def dfs(node, i):
            if i == len(word): return node.is_end
            ch = word[i]
            if ch == '.':   # wildcard: try all children
                return any(dfs(child, i+1) for child in node.children.values())
            if ch not in node.children: return False
            return dfs(node.children[ch], i+1)
        return dfs(self.root, 0)

    When to Use a Trie

    • Prefix queries: autocomplete, IP routing (longest prefix match)
    • Multiple word search on a board (Word Search II)
    • Prefix replacement or word segmentation
    • Wildcard / regex matching against a dictionary

    Interview Tips

    • Trie beats hash set for prefix queries — hash set requires O(N) scan for prefix match.
    • Top-K cache at each node trades memory for O(L) autocomplete lookups.
    • Word Search II: the early pruning from Trie is the key optimization over brute force.
    Scroll to Top