Coding Interview: How Would You Implement an Adaptive Radix Tree?

Prompt and context

Implement an ART storing variable-length byte keys and values with insertion, exact lookup, longest-prefix matching, and deletion. Nodes adapt among Node4, Node16, Node48, and Node256; path compression must preserve key semantics. This is a coding question about compressed trees, indexes, and memory layout.

What the interviewer evaluates

1. Handle compressed paths, key termination, and arbitrary bytes rather than only characters.
2. Maintain upgrades and downgrades among all four node types.
3. Implement longest-prefix matching and distinguish exact hits from ancestor values.
4. Prove deletion preserves compression invariants.
5. Explain complexity, memory trade-offs, and concurrency.

Clarifying questions to ask

• Are keys opaque byte strings and may they contain zero bytes?
• Can an internal node hold a value, or only leaves?
• What prefix length and remainder should longest-prefix lookup return?
• Must deletion shrink immediately, or may reclamation be deferred?
• Is lock-free reading or snapshot publication required?

A 30-second answer

“I compare opaque bytes and store a compressed prefix plus a termination value at internal nodes. Sparse nodes use Node4/16; dense nodes upgrade to Node48/256. Deletion downgrades and merges a valueless single-child path. Exact lookup consumes the complete key; longest-prefix lookup records the nearest valued node. I would prove single-threaded invariants against a reference map before adding locks or immutable snapshots.”

Deep-dive answer

Step 1: Define nodes and leaves

An internal node stores a compressed prefix, its length, an optional value, and children indexed by the next byte. A leaf stores the complete key or a unique value reference, which handles one key being a prefix of another.

Node { prefix, prefixLen, hasValue, value, children }
Leaf  { key, value }

Prefix length is explicit because keys are arbitrary bytes, not null-terminated strings.

Step 2: Insert and split

Compare the node prefix with the remaining key. If it matches, continue or update the value. If it diverges, create a parent containing the common prefix and attach the old node and new leaf under their differing bytes. If the new key ends at the common prefix, set the parent’s value flag.

Step 3: Choose adaptive layouts

Node4 and Node16 keep compact key and pointer arrays; lookup can scan them or use vector comparison. Node48 maps all 256 possible bytes to 48 pointer slots, avoiding 256 resident pointers. Node256 indexes directly by byte. Upgrade by copying children without losing prefix or value state.

Step 4: Exact and longest-prefix lookup

Exact lookup must consume every key byte and hit hasValue or an equal leaf key. Longest-prefix lookup records a candidate whenever a node has a value, then continues through the next byte until failure or exhaustion and returns the last candidate and its length.

Step 5: Delete and shrink

After deleting a value, remove a node with no children. If a valueless node has one child, merge its prefix and edge byte into the child. Downgrade Node256, Node48, Node16, and Node4 at documented child-count thresholds. Preserve the leaf’s complete key during merges.

Step 6: Invariants and complexity

Concatenating prefixes, edge bytes, and a leaf along any root-to-leaf path must reproduce the original key. An internal node cannot have duplicate edge bytes; hasValue means a key ends exactly there. With key length L, lookup is O(L); adaptive layouts avoid allocating 256 slots for sparse nodes.

Step 7: Test and add concurrency

Compare randomized insert, lookup, delete, and longest-prefix operations with a reference map. Include empty keys, zero bytes, prefix keys, and all 256 branches. Start concurrent versions with a read-write lock; only then consider copy-on-write, epochs, or RCU, because reclamation must be safe before lock-free pointers are exposed.

Model answer

“I treat keys as opaque byte strings. Nodes carry compressed prefixes, optional termination values, and children. Partial matches split a common-prefix parent; child counts upgrade Node4, 16, 48, and 256, while deletion downgrades and merges single-child paths. Exact lookup consumes the whole key; longest-prefix lookup remembers the nearest valued node.

Every path must reconstruct the original key. Randomized tests compare against a map and cover zero bytes, empty keys, prefix keys, and dense branches. After single-threaded correctness, use a lock; a copy-on-write or lock-free design also needs epoch or equivalent safe reclamation.”

Common mistakes

• Treating keys as characters → binary keys and zero bytes fail → compare byte lengths and values.
• Forgetting internal values → prefix keys cannot match → keep hasValue.
• Giving Node48 256 pointers → loses sparse-memory savings → use an index map.
• Clearing values without merging → leaves empty paths → shrink at thresholds.
• Ignoring ancestor candidates → longest-prefix lookup misses matches → remember the last valued node.
• Publishing raw pointers without reclamation → readers use freed memory → start with locks, then epochs/RCU.

Follow-up questions and responses

Follow-up 1: Why not always use Node256?

Most nodes are sparse, so 256 slots waste memory. Adaptive layouts balance sparse and dense regions.

Follow-up 2: What if one key prefixes another?

Store the shorter key’s value at the internal node and keep children for the longer key.

Follow-up 3: When do you merge after deletion?

Merge a valueless node with one child by concatenating its prefix and edge byte, preserving the leaf key.

Follow-up 4: How would you publish concurrent snapshots?

Use copy-on-write for a new immutable root and reclaim old trees with epochs or reference counting.