Coding interview: Implement a monotone integer radix heap

Prompt and use cases

A radix heap is an integer structure for monotone priority queues, useful in algorithms such as Dijkstra where extracted keys are nondecreasing. It uses the last extracted key as a boundary and buckets by the highest differing bit.

What the interviewer evaluates

• Whether inserted keys are constrained by the last extracted key.
• Whether the highest differing bit and bucket range are correct.
• Whether the smallest nonempty bucket is redistributed with a new base.
• Whether bucket and minimum-key invariants hold.
• Whether empty queues, overflow, and backward keys are handled.
• Whether redistribution and amortized complexity are explained honestly.

Clarifications before answering

• Are keys fixed-width unsigned integers or arbitrary precision?
• May an inserted key be smaller than the last extracted key?
• Should equal-key payloads be stable?
• Is only pop-min required, or also decrease-key and deletion?
• What should empty pop and overflow return?
• Is clarity, low constant factor, or asymptotic bound the priority?

30-second answer framework

“I maintain last, the most recently extracted key, and W+1 buckets. A key equal to last goes to bucket 0; otherwise its bucket is bit_length(key XOR last). If bucket 0 is empty, I find the smallest nonempty bucket, scan its minimum key as the new last, redistribute that bucket, and pop from bucket 0. A key below last is rejected.”

Step-by-step deep dive

Step 1: State invariants. last never decreases, every pending key satisfies key >= last, and bucket i contains keys whose highest differing bit from last is i.

Step 2: Compute the bucket. The index is 0 when key == last; otherwise use bit_length(key XOR last). A W-bit key needs W+1 buckets.

Step 3: Implement push. Check non-negativity, width, and key >= last, then place (key, value) in its bucket; equal keys may coexist.

Step 4: Implement pop. Return from bucket 0 when nonempty. Otherwise find the lowest nonempty bucket, scan its minimum key, and assign it to last.

Step 5: Redistribute. Empty that bucket and recompute each item's index against the new last; indices decrease and at least one item reaches bucket 0.

Step 6: Handle boundaries. Return the defined empty result; reject keys outside the width or below last to avoid undefined XOR and index behavior.

Step 7: State complexity. Each item is redistributed a number of times bounded by word size W; common amortized cost is O(W), space is O(n + W), and it is not universally faster than a binary heap.

Model high-quality answer

“I use 64-bit unsigned keys and 65 buckets. last starts at zero; a key below last is rejected, otherwise bit_length(key XOR last) selects its bucket. pop takes bucket 0, or finds the lowest nonempty bucket, scans its minimum key into last, and redistributes. Equal keys keep separate payloads. Empty pop returns an empty value, and overflow or backward keys fail. Each item is redistributed only a word-size-bounded number of times, with space for items plus buckets.”

Common mistakes

• Allow backward keys → bucket invariants fail → reject key < last.
• Use log2(key) for the bucket → the current base is ignored → use key XOR last.
• Keep last unchanged after redistribution → extraction can be wrong → scan the minimum first.
• Take the first item in a bucket → it may not be minimal → scan for the minimum key.
• Claim every operation is O(1) → word size and redistribution vanish → state the W and amortization assumptions.

Follow-up questions and responses

Follow-up 1: Why does it fit Dijkstra?

Extracted distances are nondecreasing, and new candidate distances are not below the current minimum, satisfying the monotone-key requirement.

Follow-up 2: What if arbitrary decrease-key is required?

A radix heap is not suitable for backward keys. Use a binary or pairing heap, or keep versions and lazily discard stale entries.

Follow-up 3: Why can bucket 0 pop directly?

Every key in bucket 0 equals last, so all are current minimum keys.

Follow-up 4: Why do redistributed indices decrease?

The new last is the bucket minimum; every other item's highest differing bit is no larger than the old bucket index, and at least one reaches bucket 0.

Follow-up 5: How do you keep equal keys stable?

Add a monotone sequence number to the payload and choose (key, sequence) in bucket 0; stability is optional otherwise.

Follow-up 6: What about negative keys?

Map them into an unsigned ordered space or specify non-negative keys only. Signed XOR without an ordering definition is unsafe.

Follow-up 7: When is a binary heap better?

Use it when keys are not monotone integers, word size is large, updates are complex, or simplicity and generality matter more than the specialized bound.