Interview Guide: Patricia Tries Problems and Solutions

Introduction to Patricia Tries

A Patricia Trie (Practical Algorithm to Retrieve Information Coded in Alphanumeric) is a space-optimized variant of a standard trie. Instead of storing one character per node, edges store entire substrings (or "runs") that are shared among keys. The nodes themselves only contain the branching points — the exact positions where keys diverge. This drastically reduces the number of nodes and memory consumption, especially for sparse keysets with long common prefixes. Patricia tries are also known as radix trees or compressed prefix trees. They are widely used in file systems, routing tables, and high-performance string matching libraries.

Why Patricia Tries Matter in Interviews

Interviewers love Patricia tries because they combine multiple algorithmic concepts into a single data structure: trees, string manipulation, recursion, and space optimisation. A candidate who can implement a Patricia trie demonstrates:

• Understanding of basic trie structures and their limitations.
• Ability to design space-efficient data structures.
• Comfort with edge cases like splitting nodes, handling variable-length keys, and managing partial matches.
• Practical knowledge of real-world applications such as IP routing (longest prefix match) and autocomplete engines.

Many classic interview questions—longest common prefix, prefix-based search, dictionary implementation—can be solved with a standard trie, but a Patricia trie shows a deeper level of mastery and often leads to better follow-up discussions about complexity and trade-offs.

How a Patricia Trie Works

Unlike a standard trie where each edge carries exactly one character, a Patricia trie allows edges to carry substrings that are common to all descendant keys. A node stores:

• A substring segment (the edge label from its parent).
• A map of children indexed by the next distinguishing character.
• A flag or value indicating if a key ends at this node.

The root node typically has an empty label. When inserting a new key, the algorithm walks down the tree, matching as many characters as possible against the current edge's substring. If a mismatch occurs inside an edge, the edge is split at the mismatch point, creating a new branching node and two children: one for the remaining part of the original edge, and one for the new key's suffix. Search follows the same matching logic, returning true only if the entire key is consumed exactly at an end-of-word node.

Key Operations

• Insert(word): Traverse matching characters. If a partial match occurs within an edge, split that edge, insert new branching node, and attach the remainder.
• Search(word): Traverse by matching edge substrings. Return true if after consuming the word we are at a terminal node and no extra characters remain unmatched.
• Delete(word): Find the node, unmark it. If it becomes a non-terminal leaf, remove it and possibly compress the parent edge with its sibling (optional).
• Collect all keys: Perform a DFS, concatenating edge labels from root to terminal nodes.

Common Interview Problems

Below are typical Patricia trie problems you might encounter in a coding interview, along with complete, runnable solutions in Python.

Problem 1: Insert and Search (Full Implementation)

Task: Implement a PatriciaTrie class with insert(word) and search(word) methods. Words consist of lowercase letters only. The trie must support splitting nodes and correctly marking word boundaries.

class PatriciaTrieNode:
    def __init__(self, prefix=""):
        self.prefix = prefix          # substring from parent to this node
        self.children = {}           # key: first char of child's edge, value: child node
        self.is_word = False         # True if a word ends exactly at this node

class PatriciaTrie:
    def __init__(self):
        self.root = PatriciaTrieNode()

    def _common_prefix_len(self, a, b):
        # Returns length of common prefix between two strings
        i = 0
        while i < len(a) and i < len(b) and a[i] == b[i]:
            i += 1
        return i

    def insert(self, word):
        node = self.root
        remaining = word
        while True:
            # Find child whose first char matches remaining's first char (if any)
            if remaining == "":
                # word fully consumed, mark node
                node.is_word = True
                return
            first_char = remaining[0]
            if first_char not in node.children:
                # No matching child, create new child holding entire remaining
                node.children[first_char] = PatriciaTrieNode(remaining)
                node.children[first_char].is_word = True
                return
            child = node.children[first_char]
            # Compare remaining with child.prefix
            cpl = self._common_prefix_len(remaining, child.prefix)
            if cpl == len(child.prefix):
                # Entire child prefix matches part of remaining
                # Move down to child
                node = child
                remaining = remaining[cpl:]  # skip matched part
                # If remaining becomes empty, mark this child as word
                if remaining == "":
                    child.is_word = True
                    return
            else:
                # Partial match: need to split the child node
                # Common prefix part becomes a new intermediate node
                common_prefix = remaining[:cpl]  # or child.prefix[:cpl]
                # Split child.prefix into [common_prefix + suffix]
                old_suffix = child.prefix[cpl:]
                new_suffix = remaining[cpl:]

                # Create new intermediate node with common_prefix
                inter = PatriciaTrieNode(common_prefix)
                # Reassign in parent: replace child with inter
                node.children[first_char] = inter

                # Old child becomes a child of inter, holding old_suffix
                child.prefix = old_suffix
                inter.children[old_suffix[0]] = child

                # If new_suffix is non-empty, create new child for it
                if new_suffix:
                    new_child = PatriciaTrieNode(new_suffix)
                    new_child.is_word = True
                    inter.children[new_suffix[0]] = new_child
                else:
                    # The new word ends exactly at the split point
                    inter.is_word = True
                return

    def search(self, word):
        node = self.root
        remaining = word
        while True:
            if remaining == "":
                return node.is_word
            first_char = remaining[0]
            if first_char not in node.children:
                return False
            child = node.children[first_char]
            if not remaining.startswith(child.prefix):
                return False
            # Move down
            node = child
            remaining = remaining[len(child.prefix):]  # skip matched part
            # Loop continues; remaining may become empty inside loop

This implementation handles all edge cases: inserting a word that is a prefix of an existing key, splitting nodes when a mismatch occurs mid-edge, and correctly marking is_word at the precise node.

Problem 2: Autocomplete (Collect All Keys with Prefix)

Task: Given a Patricia trie and a prefix, return all stored words that start with that prefix. This is a classic interview follow-up.

class PatriciaTrie:
    # ... (previous insert/search methods)

    def _collect_words(self, node, prefix_so_far, result):
        # prefix_so_far is the string built from root to current node (excluding node.prefix)
        full_path = prefix_so_far + node.prefix
        if node.is_word:
            result.append(full_path)
        for first_char, child in node.children.items():
            self._collect_words(child, full_path, result)

    def autocomplete(self, prefix):
        # Navigate to the node representing the given prefix (if possible)
        node = self.root
        remaining = prefix
        while remaining:
            first_char = remaining[0]
            if first_char not in node.children:
                return []  # prefix not in trie
            child = node.children[first_char]
            if len(child.prefix) > len(remaining):
                # child.prefix might be longer than remaining; check if remaining is prefix of child.prefix
                if child.prefix.startswith(remaining):
                    # The prefix ends inside this child's edge, we can start collecting from here
                    # but we need to adjust the path to include only the matched part
                    matched_part = remaining
                    # The node we land on is the child, but its prefix includes extra chars
                    # We can treat it as a virtual node with prefix = matched_part
                    # Collect words by considering that we are at a node with prefix = matched_part
                    # We'll simulate by traversing from this child with a reduced remaining = ""
                    # Better: just call a helper that collects from child with prefix_so_far = prefix
                    result = []
                    self._collect_words_from_edge(child, prefix, result)
                    return result
                else:
                    return []
            # remaining is longer or equal to child.prefix
            if not remaining.startswith(child.prefix):
                return []
            remaining = remaining[len(child.prefix):]
            node = child
        # If remaining exhausted, we landed exactly on 'node'
        result = []
        self._collect_words(node, "", result)  # prefix_so_far will be prefix (we'll rebuild)
        # Actually need to prepend the prefix. Better: use a helper with base string.
        # We'll reconstruct using a separate method that passes accumulated string.
        # For clarity, we'll implement a dedicated helper.
        return self._collect_with_prefix(node, prefix)

    def _collect_words_from_edge(self, node, base_prefix, result):
        # Node's prefix contains the matched prefix part. We need to extract keys starting with base_prefix.
        # Since base_prefix is a prefix of node.prefix, we can split node.prefix into (base_prefix + remainder)
        remainder = node.prefix[len(base_prefix):]
        # Build a temporary node structure? Simpler: collect all words from this node but prepend base_prefix
        # We can traverse normally but prefix_so_far = base_prefix
        full_path = base_prefix + remainder
        if node.is_word and full_path.startswith(base_prefix):
            result.append(full_path)
        for first_char, child in node.children.items():
            self._collect_words(child, full_path, result)

    def _collect_with_prefix(self, node, prefix):
        result = []
        # node is exactly at prefix endpoint (its prefix combined with ancestors = prefix)
        # But node.prefix may be non-empty if prefix ends at node. We need to pass accumulated string.
        # Actually, after navigation, if remaining becomes empty, we are at a node whose prefix (from parent) combined with ancestors equals prefix.
        # To collect, we need to know the full string from root to this node. We'll store it during traversal or recompute.
        # Simpler: modify autocomplete to keep track of built string.
        # We'll rewrite autocomplete with explicit path tracking.
        pass  # See revised implementation below

The above snippet illustrates the logic. For a complete, clean solution, we track the accumulated string during navigation and then collect all descendants. Here is a concise, full method:

    def autocomplete(self, prefix):
        node = self.root
        built = ""          # exact string from root to current node (excluding node.prefix)
        remaining = prefix
        while remaining:
            first_char = remaining[0]
            if first_char not in node.children:
                return []
            child = node.children[first_char]
            cpl = self._common_prefix_len(remaining, child.prefix)
            if cpl < len(child.prefix):
                # prefix ends inside child's edge
                if cpl == len(remaining):
                    # entire remaining matched a prefix of child.prefix
                    # The landing point is inside child's edge
                    matched = remaining
                    # Collect all words starting with (built + matched)
                    return self._collect_from_edge(child, built + matched)
                else:
                    return []
            # Full child prefix matched
            built += child.prefix
            remaining = remaining[cpl:]
            node = child
        # If remaining exhausted, we landed exactly on 'node'
        return self._collect_from_node(node, built)

    def _collect_from_node(self, node, base):
        result = []
        if node.is_word:
            result.append(base)
        for first_char, child in node.children.items():
            result.extend(self._collect_from_node(child, base + child.prefix))
        return result

    def _collect_from_edge(self, node, base):
        # node.prefix starts with the matched prefix; we need to collect all words under this node
        # base is exactly the matched part (prefix) ending somewhere inside node.prefix
        # We'll traverse normally but prepend base for any collected word
        result = []
        # The node's full path from root: base + node.prefix[len(base):]
        suffix = node.prefix[len(base):]
        full_node_str = base + suffix
        if node.is_word and full_node_str.startswith(base):
            result.append(full_node_str)
        for first_char, child in node.children.items():
            result.extend(self._collect_from_node(child, full_node_str))
        return result

Problem 3: Longest Common Prefix (LCP) Using a Patricia Trie

Task: Given a set of strings, build a Patricia trie and find the longest common prefix among all strings. This exploits the fact that the LCP is the path from root to the first branching point.

def longest_common_prefix(strings):
    if not strings:
        return ""
    trie = PatriciaTrie()
    for s in strings:
        trie.insert(s)
    # Walk down the trie while there is exactly one child and not a word end
    node = trie.root
    lcp = []
    while not node.is_word and len(node.children) == 1:
        # There's only one edge to follow
        first_char = list(node.children.keys())[0]
        child = node.children[first_char]
        lcp.append(child.prefix)
        node = child
    return "".join(lcp)

This method works because until we encounter a word boundary (is_word) or multiple children, the path is common to all inserted strings. Note that if the LCP ends exactly at a node that is a word, we still stop.

Problem 4: IP Routing Table (Longest Prefix Match)

Task: Given a list of IP prefixes (like "192.168.0.0/16", "192.168.1.0/24") and an incoming IP address, find the most specific matching prefix. This is the classic longest prefix match used in routers. We convert IPs to binary strings and use a Patricia trie.

def ip_to_binary(ip):
    parts = ip.split('.')
    return ''.join(f'{int(p):08b}' for p in parts)

class IPRouter:
    def __init__(self):
        self.trie = PatriciaTrie()
        self.next_hop = {}  # mapping from prefix string -> next hop info

    def add_route(self, prefix_cidr, next_hop):
        ip, cidr = prefix_cidr.split('/')
        length = int(cidr)
        binary = ip_to_binary(ip)[:length]  # truncate to prefix length
        self.trie.insert(binary)
        self.next_hop[binary] = next_hop

    def longest_prefix_match(self, ip_address):
        binary_ip = ip_to_binary(ip_address)
        node = self.trie.root
        remaining = binary_ip
        best_match = None
        built = ""
        while True:
            if node.is_word:
                best_match = built  # update best match (more specific)
            if remaining == "":
                break
            first_char = remaining[0]
            if first_char not in node.children:
                break
            child = node.children[first_char]
            cpl = self.trie._common_prefix_len(remaining, child.prefix)
            if cpl < len(child.prefix):
                # Partial match; the IP diverges inside this edge
                # We can't go deeper, break and use best_match so far
                break
            # Full match of child prefix
            built += child.prefix
            remaining = remaining[cpl:]
            node = child
        return best_match  # prefix string that matched

This demonstrates how Patricia tries naturally handle variable-length prefixes and allow fast longest-prefix lookups, a favourite topic in networking interviews.

Best Practices for Patricia Trie Implementations

• Use a clean node structure: Keep prefix as a string (or byte array) and children as a dictionary keyed by the first character of the child's edge. Avoid storing redundant information.
• Split carefully: When inserting, always compute the common prefix length between the remaining string and the child's prefix. Handle the three cases: full match, partial match (split needed), and no match (new branch).
• Maintain is_word at the correct node: After splitting, the word may end at the intermediate node (if the remaining suffix is empty) or at a newly created leaf. Never forget to set the flag.
• Search must verify exact match: After traversing, ensure that the entire input has been consumed and the current node is marked. Do not return true prematurely.
• Consider iterative vs recursive: Iterative traversal is usually more interview-friendly for insertion/search because it avoids deep recursion on long strings. Recursion can be used for collection operations.
• Memory management: In production, nodes can be allocated in pools or use compact arrays for children. For interviews, a dictionary per node is acceptable.
• Test edge cases: Empty string, words that are prefixes of others, single-character words, very long strings, and non-matching prefixes should all be handled correctly.

Conclusion

Patricia tries offer a powerful blend of efficiency and elegance, making them a recurring topic in technical interviews. By compressing paths into single edges, they reduce memory overhead while retaining the speed of standard tries for prefix-based queries. Mastering the insertion-split logic, search traversal, and common applications like autocomplete and IP routing will not only help you ace your next coding interview but also give you a solid foundation for building real-world high-performance data structures. Remember to practise the full implementation, test against varied inputs, and understand the trade-offs between standard tries and Patricia tries. With the examples and best practices above, you're well-equipped to handle any Patricia trie challenge that comes your way.