Interview Guide: Tries Problems and Solutions

Understanding Tries

A trie, pronounced "try" or "tree", is a tree-like data structure used to store an associative array where the keys are usually strings. Unlike a binary search tree, nodes in a trie do not store the entire key directly. Instead, each node represents a single character, and the path from the root to a node spells out a prefix of a key. A node that marks the end of a valid word is often flagged with a boolean or a special marker.

Core Concepts

The trie consists of:

• A root node that is typically empty or represents an empty string.
• Each node contains a map/dictionary of children, where each key is a character and the value is another node.
• A flag (e.g., is_end) indicating whether the node represents the end of a complete word.
• Optionally, nodes can store additional information like frequency counts or values associated with the word.

The primary operations are insertion, search, and prefix lookup, all running in O(k) time where k is the length of the key. Space complexity is O(ALPHABET_SIZE * average_word_length * n) but can be optimized.

Why Tries Matter in Interviews

Tries appear frequently in coding interviews, especially at top-tier companies. They test your understanding of tree traversal, recursion, and space-time tradeoffs. Problems involving dictionaries, autocomplete, spell checkers, IP routing (longest prefix matching), and word games like Boggle are classic trie scenarios. Mastering tries demonstrates a strong grasp of advanced data structures.

Implementing a Trie from Scratch

Let’s build a basic trie in Python. We'll define a TrieNode class and a Trie class with insertion, search, and prefix methods.

Trie Node Definition

class TrieNode:
    def __init__(self):
        self.children = {}  # dictionary mapping character -> TrieNode
        self.is_end = False  # True if the node marks the end of a word

Complete Trie Class

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

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

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def starts_with(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

This implementation uses a dictionary for children to support any character set. The starts_with method checks if any word exists that starts with the given prefix, but doesn't require that prefix to be a complete word.

Deletion Operation

Deletion is trickier. We must remove nodes that are no longer needed. A recursive approach works well:

def delete(self, word: str) -> bool:
    # Returns True if word existed and was deleted
    def _delete(node, word, depth):
        if depth == len(word):
            if not node.is_end:
                return False
            node.is_end = False
            # If no children, node can be removed
            return len(node.children) == 0
        char = word[depth]
        if char not in node.children:
            return False
        should_delete_child = _delete(node.children[char], word, depth + 1)
        if should_delete_child:
            del node.children[char]
            # Return True if current node has no other children and is not an end node
            return not node.is_end and len(node.children) == 0
        return False

    return _delete(self.root, word, 0)

This recursive function walks down, marks is_end as False at the word's end, then backtracks to delete nodes that have become leaf nodes and are not part of another word.

Common Interview Problems and Solutions

Now let’s tackle typical trie-based problems with complete solutions. Each problem includes the approach and code.

Problem 1: Autocomplete System

Description: Implement a function that, given a prefix, returns all words in the trie that start with that prefix, sorted lexicographically.

Solution: After reaching the node for the prefix, perform a DFS to collect all complete words.

class TrieWithAutoComplete(Trie):
    def get_words_with_prefix(self, prefix: str):
        node = self.root
        # Traverse to the end of prefix
        for char in prefix:
            if char not in node.children:
                return []  # prefix not found
            node = node.children[char]
        # Collect all words from this node
        result = []
        self._dfs_collect(node, prefix, result)
        return sorted(result)  # return lexicographically sorted

    def _dfs_collect(self, node, current_prefix, result):
        if node.is_end:
            result.append(current_prefix)
        for char, child_node in node.children.items():
            self._dfs_collect(child_node, current_prefix + char, result)

# Usage example
trie = TrieWithAutoComplete()
words = ["cat", "car", "cart", "dog", "cow", "carpet"]
for w in words:
    trie.insert(w)
print(trie.get_words_with_prefix("car"))  # ['car', 'carpet', 'cart']

Problem 2: Word Dictionary with Dot Wildcards

Description: Design a data structure that supports adding words and searching for words where dots '.' can match any letter. (LeetCode 211: Design Add and Search Words Data Structure).

Solution: Use a trie and for search with wildcards, perform a recursive DFS when encountering '.'.

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

    def add_word(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search_word(self, word: str) -> bool:
        def dfs(node, index):
            if index == len(word):
                return node.is_end
            char = word[index]
            if char == '.':
                # try all possible children
                for child in node.children.values():
                    if dfs(child, index + 1):
                        return True
                return False
            else:
                if char not in node.children:
                    return False
                return dfs(node.children[char], index + 1)
        return dfs(self.root, 0)

# Example
wd = WordDictionary()
wd.add_word("bad")
wd.add_word("dad")
wd.add_word("mad")
print(wd.search_word("pad"))   # False
print(wd.search_word("bad"))   # True
print(wd.search_word(".ad"))   # True (matches bad, dad, mad)
print(wd.search_word("b.."))   # True (matches bad)

Problem 3: Count Words with a Given Prefix

Description: Given a list of words, answer queries about how many words start with a certain prefix. Preprocess with a trie storing a count at each node.

Solution: Each node stores a counter of how many words pass through it (including itself if it's an end).

class TriePrefixCounter:
    def __init__(self):
        self.root = TrieNodeWithCount()

class TrieNodeWithCount:
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.prefix_count = 0  # number of words that have this prefix

class TrieWithCount:
    def __init__(self):
        self.root = TrieNodeWithCount()

    def insert(self, word: str):
        node = self.root
        node.prefix_count += 1
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNodeWithCount()
            node = node.children[char]
            node.prefix_count += 1
        node.is_end = True

    def count_words_with_prefix(self, prefix: str) -> int:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.prefix_count

# Example
tc = TrieWithCount()
words = ["apple", "app", "ape", "bat", "ball"]
for w in words:
    tc.insert(w)
print(tc.count_words_with_prefix("ap"))  # 3 (apple, app, ape)
print(tc.count_words_with_prefix("ba"))  # 2 (bat, ball)

Problem 4: Longest Common Prefix Among a Set of Strings

Description: Find the longest common prefix among an array of strings using a trie. (LeetCode 14 variant).

Solution: Insert all strings, then traverse while there is exactly one child and no end node (or end node is fine if we allow that). Alternatively, a simple trie approach: walk from root, if at any node there is more than one child or we hit a word end before processing all strings, stop.

def longest_common_prefix(strs):
    if not strs:
        return ""
    # Insert all words into trie
    trie = Trie()
    for word in strs:
        trie.insert(word)
    # Walk from root as long as there is exactly one child and node is not end
    node = trie.root
    prefix = []
    while True:
        # If node is end, we stop (but if there are more characters in other strings, it's not common anyway)
        # We consider: stop if node has != 1 child or node.is_end is True
        if node.is_end or len(node.children) != 1:
            break
        # There is exactly one child, move to it
        char, child = next(iter(node.children.items()))
        prefix.append(char)
        node = child
    return ''.join(prefix)

# Example
print(longest_common_prefix(["flower","flow","flight"]))  # "fl"
print(longest_common_prefix(["dog","racecar","car"]))    # ""

Note: This trie-based approach works well, but a simpler approach without trie (comparing characters) is more space-efficient. However, it demonstrates trie usage.

Best Practices for Trie Problems in Interviews

When tackling trie problems, keep these tips in mind:

• Understand the problem scope: Determine if the alphabet is small (e.g., lowercase English letters) – then you can use a fixed-size array (size 26) instead of a dictionary, which is faster and memory-efficient.
• Define node structure clearly: Always start by writing the node class. Interviewers appreciate clean separation of concerns.
• Use recursion for complex traversals: For wildcards, deletion, or collecting all words, recursion often simplifies the logic.
• Consider space optimizations: If only storing words with a limited character set, use arrays; consider compressing paths (radix tree/Patricia trie) if asked about memory.
• Edge cases: Empty string, empty input, prefix longer than any word, overlapping words (e.g., "app" and "apple").
• Time complexity: Mention O(k) for insert/search, O(prefix length + number of matching words) for autocomplete. Be ready to discuss worst-case scenarios.
• Test thoroughly: Demonstrate with examples, covering all methods.

Conclusion

Tries are a fundamental data structure that shines in string-based retrieval tasks. In interviews, they allow you to solve problems with prefix matching, wildcard search, and autocomplete efficiently. By mastering the basic implementation and common variations, you'll be prepared to handle any trie-related question with confidence. Remember to practice writing clean, modular code and to analyze trade-offs between time and space. With the patterns and solutions covered here, you have a solid foundation to excel in your next coding interview.