Practice/xAI/Radix Cache

Radix Cache

CodingMust

Problem Overview

Design and implement a Prefix Radix Cache that efficiently stores sequences of numbers using a radix tree (also known as a prefix tree or compressed trie). Unlike a standard trie where each node represents a single element, a radix tree compresses chains of single-child nodes into single edges containing multiple elements.

This data structure is commonly used in:

• LLM KV caching to share prompt prefixes across requests
• IP routing tables (CIDR prefix matching)
• String indexing with common prefixes
• Token sequence caching in language models

Part 1: Basic Radix Tree with Insert

Implement a RadixCache class that can insert sequences and build a proper radix tree structure.

Example

` tree = RadixCache() tree.insert([10, 20]) tree.insert([1, 2, 3]) tree.insert([1, 2, 3, 4, 5, 6])

Tree Structure:

Root

├── [1, 2, 3]

│ └── [4, 5, 6]

└── [10, 20]

`

Notice how:

• [1, 2, 3] and [1, 2, 3, 4, 5, 6] share the prefix [1, 2, 3]
• [10, 20] is a separate branch (no common prefix with [1, ...])

Requirements

• Each node contains children as a dictionary mapping the first element of an edge to (edge_sequence, child_node)
• Terminal nodes are marked with a flag to indicate a complete sequence ends there
• On insert, traverse the tree and handle: no match (create new child), partial match (split edge), full match (continue to child)

Clarification Questions to Ask

• Should we support deletion of sequences?
• What should happen if the same sequence is inserted twice?
• Should we track how many times each prefix has been inserted (reference counting)?
• Are the numbers guaranteed to be positive integers?
• Is there a maximum sequence length or maximum number of sequences?

Part 2: Edge Splitting

Handle the case where inserting a new sequence requires splitting an existing edge. This happens when a new sequence shares only a partial prefix with an existing edge.

Example

` tree = RadixCache() tree.insert([1, 2, 3]) tree.insert([1, 2, 3, 4, 5, 6]) tree.insert([1, 2, 3, 40, 50, 60, 70, 80]) tree.insert([1, 2, 3, 40, 50, 60, 700, 800])

Final Tree Structure:

Root

└── [1, 2, 3]

├── [4, 5, 6]

└── [40, 50, 60]

├── [70, 80]

└── [700, 800]

`

When inserting [1, 2, 3, 40, 50, 60, 700, 800] and edge [40, 50, 60, 70, 80] already exists:

1. Find the common prefix: [40, 50, 60]

2. Split the existing edge into:

   • New edge with common prefix: [40, 50, 60]
   • Child edge with remainder: [70, 80]

3. Add new child edge for the new sequence's remainder: [700, 800]

Requirements

• Find the common prefix length between the new sequence and existing edge
• Create a split node at the common prefix point
• Move the original edge's remainder to a child of the split node
• Add the new sequence's remainder as another child

Part 3: Additional Operations

Extend your implementation with search, prefix matching, and sequence retrieval operations.

Example

` tree = RadixCache() tree.insert([1, 2, 3]) tree.insert([1, 2, 3, 4, 5]) tree.insert([10, 20])

Search exact sequences

tree.search([1, 2, 3]) # True (complete sequence) tree.search([1, 2]) # False (prefix exists but not complete) tree.search([10, 20]) # True

Find longest matching prefix

tree.prefix_match([1, 2, 3, 4, 5, 6, 7]) # Returns [1, 2, 3, 4, 5] tree.prefix_match([1, 2]) # Returns [] (not a complete sequence)

Get all sequences

tree.get_all_sequences() # Returns [[1, 2, 3], [1, 2, 3, 4, 5], [10, 20]] `

Requirements

• search(sequence): Check if exact sequence exists (must be a terminal node)
• prefix_match(sequence): Find longest prefix that is a complete sequence
• get_all_sequences(): Return all complete sequences via DFS traversal