Level 1 A compressed trie of integer sequences
LLM servers cache work for token sequences that often share long prefixes (the same system prompt, the same conversation so far). Build RadixCache, a radix tree (compressed trie) over sequences of integers:
- Each edge is labelled with a non-empty run of integers, not a single one.
- The children of a node start with different first integers.
- Compression: every node except the root either ends a stored sequence or has at least two children. (A chain of single-child nodes must be merged into one edge.)
Implement:
insert(seq: list[int]) -> bool: storeseq(length >= 1). ReturnTrueif it was new,Falseif it was already stored.contains(seq) -> bool: is exactlyseqstored?node_count() -> int: the number of nodes in the tree, not counting the root. The tests use this to check that your tree really is compressed.
rc = RadixCache()
rc.insert([1, 2, 3, 4]) # True root -[1,2,3,4]-> A nodes: 1
rc.insert([1, 2, 9]) # True root -[1,2]-> B, B -[3,4]-> A, B -[9]-> C nodes: 3
rc.insert([1, 2]) # True B now also ends a sequence nodes: 3
rc.insert([1, 2, 9]) # False
rc.contains([1, 2, 3]) # False (only a prefix of a stored sequence)
rc.node_count() # 3
Sequences can be long (thousands of integers) and share long prefixes. insert and contains must cost about O(len(seq)) (plus the size of any label you split), not O(total stored).
Show hint
Store at each node children: dict[first_int -> child], and at each child its label (a tuple or list) and an end flag. To insert, walk down; at a child, measure how much of its label matches the rest of seq. Full match: descend. Partial match of length c: split the child into a new middle node with label[:c], whose child is the old node with label[c:]; then either mark the middle as end or hang a new leaf off it.