Radix Cache

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 character, in a radix tree, each node represents a range of characters (e.g., 0-9 for digits). This allows for more efficient storage and retrieval of sequences.

Problem Statement

Implement a Prefix Radix Cache class with the following methods:

1. insert(key: List[int]): Insert a sequence of numbers into the radix tree.
2. search(key: List[int]): Search for a sequence of numbers in the radix tree and return True if found, False otherwise.
3. start_with(prefix: List[int]): Return a list of all sequences in the radix tree that start with the given prefix.

Constraints

• The input sequences are non-empty and consist of integers between 0 and 9.
• The length of the input sequences can vary.

Examples

`python

Initialize the Prefix Radix Cache

cache = PrefixRadixCache()

Insert sequences

cache.insert([1, 2, 3]) cache.insert([1, 2, 4]) cache.insert([1, 3])

Search for a sequence

print(cache.search([1, 2, 3])) # Output: True print(cache.search([1, 2, 5])) # Output: False

Find sequences starting with a prefix

print(cache.start_with([1, 2])) # Output: [[1, 2, 3], [1, 2, 4]] `

Hints

1. Use a trie-like data structure to store the sequences, where each node represents a range of characters (0-9).
2. To efficiently store and retrieve sequences, consider using a compressed trie approach where nodes with only one child are merged.
3. For the start_with method, perform a depth-first search from the root node and collect all sequences that match the prefix.

Solution

`python class Node: def init(self): self.children = {} self.is_end = False self.seqs = []

class PrefixRadixCache: def init(self): self.root = Node()

def insert(self, key):
    node = self.root
    for num in key:
        if num not in node.children:
            node.children[num] = Node()
        node = node.children[num]
    node.is_end = True
    node.seqs.append(key[:])
    return

def search(self, key):
    node = self.root
    for num in key:
        if num not in node.children:
            return False
        node = node.children[num]
    return node.is_end

def start_with(self, prefix):
    node = self.root
    for num in prefix:
        if num not in node.children:
            return []
        node = node.children[num]
    return self.dfs(node, prefix)

def dfs(self, node, prefix):
    res = []
    if node.is_end:
        res.append(prefix[:])
    for num, child in node.children.items():
        res.extend(self.dfs(child, prefix + [num]))
    return res

Example usage

cache = PrefixRadixCache() cache.insert([1, 2, 3]) cache.insert([1, 2, 4]) cache.insert([1, 3]) print(cache.search([1, 2, 3])) # Output: True print(cache.search([1, 2, 5])) # Output: False print(cache.start_with([1, 2])) # Output: [[1, 2, 3], [1, 2, 4]] `

This solution implements a Prefix Radix Cache class using a radix tree data structure. The insert, search, and start_with methods efficiently store, retrieve, and find sequences based on the given constraints.