Trie Data Structure Interview Patterns: Autocomplete, Word Search & XOR

Trie Data Structure Interview Patterns: Autocomplete, Word Search & Prefix Problems

A Trie (prefix tree) is the go-to data structure for string prefix operations. It enables O(m) insert, search, and prefix queries where m is the word length—far faster than a hash set for prefix matching. Tries appear in autocomplete, spell checkers, IP routing, and word game problems.

Trie Fundamentals

• Structure — each node represents one character; root is empty; paths from root to leaf spell words
• Children — each node has up to 26 children (a-z) or a hash map for arbitrary character sets
• End marker — a boolean is_end flag marks complete words
• Time — O(m) insert, search, prefix check (m = word length)
• Space — O(n·m) worst case, but shared prefixes save memory

Trie Implementation

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False
        self.count = 0       # words ending here (optional)

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

    def insert(self, word: str) -> None:
        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: str) -> bool:
        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: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

Pattern 1: Autocomplete / Search Suggestions

Build a Trie, then DFS from the prefix node to collect all words:

def autocomplete(trie, prefix):
    node = trie.root
    for ch in prefix:
        if ch not in node.children:
            return []
        node = node.children[ch]
    # DFS to collect all words with this prefix
    results = []
    def dfs(cur, path):
        if cur.is_end:
            results.append(prefix[:-len(path)] + path if path else prefix)
        for ch, child in cur.children.items():
            dfs(child, path + ch)
    dfs(node, "")
    return results

Pattern 2: Word Search with Wildcards

Implement search with ‘.’ wildcard that matches any character:

def search_with_wildcard(node, word, i):
    if i == len(word):
        return node.is_end
    ch = word[i]
    if ch == '.':
        return any(search_with_wildcard(child, word, i+1)
                   for child in node.children.values())
    if ch not in node.children:
        return False
    return search_with_wildcard(node.children[ch], word, i+1)

Pattern 3: Word Break Problem

Use Trie with DP to check if a string can be segmented into dictionary words:

def word_break(s, word_dict):
    trie = Trie()
    for w in word_dict:
        trie.insert(w)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(n):
        if not dp[i]:
            continue
        node = trie.root
        for j in range(i, n):
            ch = s[j]
            if ch not in node.children:
                break
            node = node.children[ch]
            if node.is_end and dp[i]:
                dp[j+1] = True
    return dp[n]

Pattern 4: Maximum XOR (Bitwise Trie)

Binary Trie where each bit is a node. Find pair with maximum XOR in O(n·32):

class BitTrie:
    def __init__(self):
        self.root = {}

    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if bit not in node:
                node[bit] = {}
            node = node[bit]

    def max_xor(self, num):
        node = self.root
        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:
                xor |= (1 << i)
                node = node[want]
            else:
                node = node[bit]
        return xor

Classic Trie Interview Problems

Problem	Approach	Complexity
Implement Trie (Prefix Tree)	Standard trie	O(m) per op
Design Search Autocomplete	Trie + DFS + sort by frequency	O(m + k log k)
Word Search II (board)	Trie + DFS backtracking	O(M·N·4^L)
Add and Search Word	Trie + recursive wildcard	O(m) / O(26^m) worst
Replace Words (sentence)	Trie prefix replacement	O(n·m)
Maximum XOR of Two Numbers	Binary Trie	O(n·32)
Palindrome Pairs	Trie + reverse words	O(n·m²)

Interview Tips

• Recognize trie problems: “prefix,” “autocomplete,” “starts with,” “words sharing prefix”
• Dictionary (hash map) children is more flexible than array[26] for non-lowercase-alpha inputs
• Combine Trie with DFS for all-words-with-prefix; add a frequency counter for ranked autocomplete
• For Word Search II on a 2D board: build Trie from word list, DFS each cell, prune branches not in Trie
• Always mention the trade-off: Trie uses more memory than a hash set but enables O(m) prefix ops

Coinbase Interview Guide

Twitter Interview Guide

Atlassian Interview Guide

LinkedIn Interview Guide

Apple Interview Guide

Meta Interview Guide

🏢 Asked at: Uber Interview Guide 2026: Dispatch Systems, Geospatial Algorithms, and Marketplace Engineering

🏢 Asked at: Cloudflare Interview Guide 2026: Networking, Edge Computing, and CDN Design