Radix Cache

Implement a prefix radix cache over integer sequences, including compressed-edge insertion, edge splitting, exact search, longest-prefix match, and sequence enumeration. Radix Cache Implement a prefix radix cache over integer sequences, including compressed-edge insertion, edge splitting, exact search, longest-prefix match, and sequence enumeration. SWE Infra Eng MLE trie data-structure kv-cache design-implementation hard Frequency Single report Last asked 2026-01-24 Stage onsite-coding · tech-screen Radix Cache Problem Summary You need to build a Prefix Radix Cache. This data structure saves lists (sequences) of numbers efficiently using a "radix tree." A normal trie stores one number per node. A radix tree is different. It compresses the tree by putting chains of single-child nodes into one edge. This is very useful for: LLM KV caching: Sharing the start of prompts between requests. IP routing: Matching network prefixes (CIDR). String indexing: Grouping words with the same start. What You Need to Build Your code must support: insert(sequence): Add a list of numbers to the tree. If two lists start with the same numbers, they should share those nodes. Example tree = RadixCache() tree.insert([10, 20]) tree.insert([1, 2, 3]) tree.insert([1, 2, 3, 4, 5, 6]) What the tree looks like: Root ├── [1, 2, 3] │ └── [4, 5, 6] └── [10, 20] Key details: [1, 2, 3] is the start (prefix) for [1, 2, 3, 4, 5, 6]. They share the first node. [10, 20] is totally different. It gets its own branch. Part 1: Basic Tree Setup Task Requirements Write a RadixCache class. It needs to accept a list of numbers and build the tree. class RadixCache: def __init__(self): """Start with an empty cache.""" pass def insert(self, sequence: list[int]) -> None: """ Add a list of numbers to the tree. Args: sequence: A list of integers to add. """ pass def __str__(self) -> str: """Show the tree structure as a string.""" pass Test Examples # Test 1: Simple adds tree = RadixCache() tree.insert([10, 20]) tree.insert([1, 2, 3]) tree.insert([1, 2, 3, 4, 5, 6]) # Tree should look like: # Root # ├── [1, 2, 3] # │ └── [4, 5, 6] # └── [10, 20] # Test 2: No matching starts tree = RadixCache() tree.insert([1, 2, 3]) tree.insert([4, 5, 6]) tree.insert([7, 8, 9]) # All three are separate branches. # Test 3: Adding a shorter list after a longer one tree = RadixCache() tree.insert([1, 2, 3, 4, 5]) tree.insert([1, 2, 3]) # The long edge [1, 2, 3, 4, 5] must split. # Root # └── [1, 2, 3] # └── [4, 5] Part 2: Breaking Edges (Splitting) Task Requirements You must handle splitting an edge. This happens when you add a new list that matches only part of an existing edge. Example tree = RadixCache() tree.insert([1, 2, 3]) tree.insert([1, 2, 3, 4, 5, 6]) # Current Tree: # Root # └── [1, 2, 3] # └── [4, 5, 6] # Now insert a list that matches [1, 2, 3] but changes after [40, 50, 60] tree.insert([1, 2, 3, 40, 50, 60, 70, 80]) tree.insert([1, 2, 3, 40, 50, 60, 700, 800]) Final Tree: Root └── [1, 2, 3] → Internal1 ├── [4, 5, 6] → Leaf1 └── [40, 50, 60] → Internal2 ├── [70, 80] → Leaf2 └── [700, 800] → Leaf3 What happened: The edge [40, 50, 60, 70, 80] existed. We added [... 700, 800]. They both share [40, 50, 60]. We split the edge there. [70, 80] and [700, 800] became children. How to Split Logic When adding a list that conflicts with an existing edge: Find the shared numbers (the common prefix). Cut the old edge at that point. The top part keeps the shared numbers. The bottom part becomes a child. Add the rest of the new list as a second child. Test Examples for Splitting # Test 1: Split at the very first number tree = RadixCache() tree.insert([1, 2, 3, 4, 5]) tree.insert([1, 100, 200]) # Edge [1, 2, 3, 4, 5] becomes [1]. # Children are [2, 3, 4, 5] and [100, 200]. # Test 2: Multiple splits tree = RadixCache() tree.insert([1, 2, 3, 4, 5, 6, 7, 8]) tree.insert([1, 2, 3, 4, 5, 60, 70, 80]) # Splits at 6 vs 60. Common is [1...5]. tree.insert([1, 2, 30, 40]) # Splits again at 3 vs 30. Common is [1, 2]. Part 3: Search and Match Tools Task Requirements Add these three helper methods to your class: class RadixCache: # ... old methods ... def search(self, sequence: list[int]) -> bool: """ Check if this EXACT list is in the cache. Returns True or False. """ pass def prefix_match(self, sequence: list[int]) -> list[int]: """ Find the longest part of the input list that is already stored. Returns that matching list. """ pass def get_all_sequences(self) -> list[list[int]]: """ Get every full list stored in the cache. Returns a list of lists. """ pass Test Examples # Setup tree = RadixCache() tree.insert([1, 2, 3]) tree.insert([1, 2, 3, 4, 5]) tree.insert([10, 20]) # Test search assert tree.search([1, 2, 3]) == True assert tree.search([1, 2]) == False # It's in the tree, but not a full entry assert tree.search([1, 2, 3, 4]) == False assert tree.search([10, 20]) == True # Test prefix_match assert tree.prefix_match([1, 2, 3, 4, 5, 6, 7]) == [1, 2, 3, 4, 5] assert tree.prefix_match([1, 2, 3]) == [1, 2, 3] assert tree.prefix_match([1, 2]) == [] assert tree.prefix_match([99, 100]) == [] # Test get_all_sequences sequences = tree.get_all_sequences() # Should return [1, 2, 3], [1, 2, 3, 4, 5], and [10, 20] How to Solve It Questions to Ask the Interviewer Can we delete items later? What if I add the same list twice? Do we need to count how many times a prefix is used? Are the numbers always positive integers? Do we need a strict search function? Solution Strategy (Part 1 & 2) Node Structure: Each node has a dictionary. The key is the first number of the edge. The value is the full edge list and the next node. Terminals: Mark nodes where a sequence officially ends (so we know [1, 2] is distinct from [1, 2, 3]). Insert Logic: No Match: Make a new child edge. Partial Match: Split the current edge into two parts. Full Match: Walk down the tree to the next node. Code Implementation class RadixNode: def __init__(self): # Dictionary: first_number -> (full_edge_list, next_node) self.children = {} # True if a list officially ends at this node self.is_terminal = False class RadixCache: def __init__(self): self.root = RadixNode() def insert(self, sequence: list[int]) -> None: if not sequence: return self._insert_helper(self.root, sequence) def _insert_helper(self, node: RadixNode, sequence: list[int]) -> None: if not sequence: node.is_terminal = True return first_elem = sequence[0] # Case 1: No match found. Create a new edge. if first_elem not in node.children: new_node = RadixNode() new_node.is_terminal = True node.children[first_elem] = (list(sequence), new_node) return # Found a match. Get the edge and the child node. edge_seq, child_node = node.children[first_elem] # Calculate how much of the prefix matches. common_len = 0 min_len = min(len(edge_seq), len(sequence)) while common_len < min_len and edge_seq[common_len] == sequence[common_len]: common_len += 1 # Case 2: The new sequence matches the edge completely (or is shorter). if common_len == len(sequence): if common_len == len(edge_seq): # Exact match. Just mark the end. child_node.is_terminal = True else: # The new list is shorter than the edge. We must split. split_node = RadixNode() split_node.is_terminal = True # The rest of the old edge becomes a child of the split. remainder = edge_seq[common_len:] split_node.children[remainder[0]] = (remainder, child_node) # Update the parent to point to the split node. node.children[first_elem] = (list(sequence), split_node) return # Case 3: The edge matches completely, but the new list is longer. if common_len == len(edge_seq): # Keep going down the tree with the rest of the list. self._insert_helper(child_node, sequence[common_len:]) return # Case 4: Partial match. They differ in the middle. We must split. split_node = RadixNode() # 1. Attach the rest of the old edge to the split node. edge_remainder = edge_seq[common_len:] split_node.children[edge_remainder[0]] = (edge_remainder, child_node) # 2. Attach the rest of the NEW list to the split node. seq_remainder = sequence[common_len:] new_node = RadixNode() new_node.is_terminal = True split_node.children[seq_remainder[0]] = (seq_remainder, new_node) # 3. Update the parent to point to the shared prefix. common_prefix = edge_seq[:common_len] node.children[first_elem] = (common_prefix, split_node) def __str__(self) -> str: lines = ["Root"] self._str_helper(self.root, "", lines, is_last=True) return "\n".join(lines) def _str_helper(self, node: RadixNode, prefix: str, lines: list, is_last: bool) -> None: children = sorted(node.children.items()) for i, (first_elem, (edge_seq, child_node)) in enumerate(children): is_child_last = (i == len(children) - 1) connector = "└── " if is_child_last else "├── " terminal_marker = " *" if child_node.is_terminal else "" lines.append(f"{prefix}{connector}{edge_seq}{terminal_marker}") extension = " " if is_child_last else "│ " self._str_helper(child_node, prefix + extension, lines, is_child_last) Complexity Analysis Operation Time Complexity Notes insert O(L) L is the length of the list. We traverse and maybe split. search O(L) Depends on list length. prefix_match O(L) Depends on list length. Space Complexity: Worst case: O(N × L) (if nothing matches). Real world: Much better because prefixes are shared. Solution for Part 3 Here is the code for the extra search tools. class RadixCache: # ... previous methods ... def search(self, sequence: list[int]) -> bool: """Check if exact sequence exists.""" if not sequence: return False node = self.root remaining = sequence while remaining: first_elem = remaining[0] if first_elem not in node.children: return False edge_seq, child_node = node.children[first_elem] # Does the remaining list start with this edge? edge_list = list(edge_seq) if len(remaining) < len(edge_list): return False if list(remaining[:len(edge_list)]) != edge_list: return False # Move forward remaining = remaining[len(edge_seq):] node = child_node # We matched everything, but is this a valid ending point? return node.is_terminal def prefix_match(self, sequence: list[int]) -> list[int]: """Find longest matching prefix that is a complete sequence.""" if not sequence: return [] node = self.root remaining = sequence matched = [] last_terminal_match = [] while remaining: first_elem = remaining[0] if first_elem not in node.children: break edge_seq, child_node = node.children[first_elem] # Check how much of the edge matches our input match_len = 0 while match_len < len(edge_seq) and match_len < len(remaining): if edge_seq[match_len] != remaining[match_len]: break match_len += 1 if match_len < len(edge_seq): # Only part of the edge matches. Stop here. break # The whole edge matches. Add to our result. matched.extend(edge_seq) remaining = remaining[len(edge_seq):] node = child_node # If this is a valid stopping point, save it. if node.is_terminal: last_terminal_match = matched.copy() return last_terminal_match def get_all_sequences(self) -> list[list[int]]: """Return all complete sequences.""" result = [] self._collect_sequences(self.root, [], result) return result def _collect_sequences(self, node: RadixNode, current: list[int], result: list[list[int]]) -> None: if node.is_terminal and current: # Only add if it's not empty result.append(current.copy()) for first_elem, (edge_seq, child_node) in node.children.items(): self._collect_sequences(child_node, current + list(edge_seq), result) Discussion and Real-World Use Why use Radix Trees for LLM KV Caching? When Large Language Models (LLMs) run, they calculate a "Key-Value (KV) cache" for the text. If you send two prompts that start the same way, we can reuse that work. Request 1: "You are a helpful assistant. User: What is 2+2?" Request 2: "You are a helpful assistant. User: Tell me a joke." The phrase "You are a helpful assistant" creates the exact same KV cache. Memory: Store it once, not twice. Speed: Don't calculate it again. Things to Consider in Production Reference Counting: Keep track of how many active requests use a node. If the count hits zero, you might delete it to save space. Eviction Policies: If memory is full, what do you delete? You might remove the "Least Recently Used" (LRU) branches. Thread Safety: In a real server, many requests hit the cache at once. You need "Locks" to stop them from breaking the tree structure. Comparison Table Structure How it shares prefixes Insert Speed Search Speed Space Usage Hash Map None (Stores full copies) O(L) O(L) High Trie One node per number O(L) O(L) Very High Radix Tree Compressed Edges O(L) O(L) Low Suffix Tree Stores all suffixes O(L) O(P) Complex (L = list length, P = pattern length) Alternative Ideas 1. Hash-based Prefixing: Instead of a tree, you hash the prefix (like a fingerprint). It's fast, but you can't easily see the structure or share parts of prefixes. 2. Segment Caching: Split long lists into chunks (blocks). You cache the blocks. It is simpler to code but less flexible than a Radix Tree.