How would you implement a stable bounded priority queue?

1. Problem

Implement StableBoundedPriorityQueue. Each entry has priority, sequence, and value; compare priority first and sequence second. With capacity C, push keeps at most C entries. A new entry replaces the current worst entry only when it is better; otherwise it is rejected. pop returns the best entry.

2. Constraints and clarifications

• C is a positive integer; with C=0, every insertion is rejected without touching an array boundary.
• A lower number means higher priority; equal priorities must leave in insertion order.
• Rejecting the worst item when full requires finding that item. A single min-heap cannot expose it directly in O(log C), so use a second index, a max-heap, or accept a linear scan.
• Start with a single-threaded implementation. Concurrent producers and consumers need an external lock or a dedicated concurrent queue.

3. Core approach

Use a min-heap for the next item, ordered by (priority, sequence). Use a max-heap for the worst item, ordered so larger priority and later sequence are worse. Both heaps point to the same entry record. Removal marks an entry alive=false; each heap discards dead nodes when they reach its root. This lazy deletion avoids arbitrary-position heap deletion.

For small capacities, a linear scan for the worst item is simpler: pop remains O(log C), while a full-queue push costs O(C). State this trade-off before presenting the two-heap optimization.

4. Reference implementation

record Entry(priority, sequence, value, alive=true)

push(priority, value):
  if capacity == 0: return false
  candidate = Entry(priority, nextSequence(), value)
  if size < capacity:
    add candidate to minHeap and maxHeap
    size += 1
    return true
  discard dead nodes from maxHeap
  worst = maxHeap.peek()
  if (priority, candidate.sequence) >= (worst.priority, worst.sequence):
    return false
  worst.alive = false
  pop maxHeap
  add candidate to both heaps
  return true

pop():
  discard dead nodes from minHeap
  if minHeap is empty: return EMPTY
  entry = pop minHeap
  entry.alive = false
  size -= 1
  return entry.value

The max-heap key means “larger is worse”: a larger priority is worse, and for equal priority a larger sequence is later and therefore worse. If a language has no max-heap, negate the key or provide a comparator. nextSequence must be monotonic; use a wide integer or reset it only when the queue is empty.

5. Complexity and trade-offs

An accepted insertion adds one node to each heap, so it costs O(log C); pop costs O(log C). Replacement is also O(log C). Lazy deletion can leave dead nodes temporarily, but each dead node is popped once, giving amortized O(log C) operations and O(C) space with a constant-factor increase. A linear-scan variant uses less space and shorter code but costs O(C) for a full-queue insertion.

6. Verification and observability

• Cover C=0, C=1, an empty queue, repeated rejection, and repeated replacement.
• Insert several equal-priority entries and verify FIFO order by sequence.
• Test a worse, equal, and better candidate against a full queue; expect reject, reject, and replace.
• Compare random operation traces with a reference model that sorts all live entries by (priority, sequence) and truncates to C.
• Record queue length, rejection count, and lazy-node cleanup count. A rising rejection rate can trigger upstream throttling or load shedding.

7. Common mistakes

• Sorting only by priority, which loses FIFO stability for ties.
• Assuming a larger numeric priority is more important without confirming the direction.
• Popping the heap root before admission, which discards the best task when the queue is full.
• Failing to discard dead nodes, so peek returns an entry already replaced or cancelled.
• Using wall-clock timestamps for sequence numbers; clock rollback or same-tick inserts can break FIFO.

8. Follow-up questions

How would you enforce per-tenant quotas?

Keep a count and limit for each tenant. Check both the global capacity and the tenant quota before insertion, and count the two rejection reasons separately so hot tenants are visible.

How would you cancel or reprioritize an entry?

Give each entry an ID and use lazy deletion. Cancellation marks it dead; reprioritization creates a new entry and invalidates the old one. Clean dead nodes while peeking or popping instead of deleting arbitrary heap positions.

When should you use a library concurrent priority queue?

Use a tested concurrent implementation when multiple threads or processes produce and consume, blocking waits are required, or memory limits are strict. A custom two-heap design is appropriate only with a clear single-threaded boundary and a testable lifecycle.