Coding Interview: How Would You Implement a Mutable Priority Queue with Update and Remove?

Prompt and scope

Implement a priority queue with add(task, priority), update(task, priority), remove(task), and pop(). Equal priorities must be returned in insertion order; update and remove should be amortized O(log n). Explain how stale heap entries are handled.

This tests correctness of a mutable priority queue, not only whether you can call a heap API. Python’s heapq documentation highlights stable ordering, non-comparable tasks, priority updates, and pending removal as the hard parts. A common design uses a counter for ties, a map for location, and lazy deletion to preserve the heap invariant.

What the interviewer is testing

First, can you write the complete heap key: priority, insertion sequence, and task? Second, can updates and removals avoid directly corrupting the heap? Third, can you handle duplicate tasks, an empty queue, a stale root, and long-lived garbage entries?

Questions to clarify before answering

• Are priorities numbers or comparable objects? Assume comparable integers, with smaller values first.
• Are task IDs unique? Assume yes; duplicate add is either an update or an explicit error.
• Is stable ordering required? Assume equal priorities use first-insertion order.
• May lazy deletion retain memory temporarily? Yes, with a cleanup and rebuild policy.
• Are calls concurrent? Assume one thread; concurrency needs an external lock or safe container.

A 30-second answer framework

“I would store [priority, sequence, task] in a min-heap and map each task ID to its current valid entry. An update marks the old entry removed and inserts a new entry with a new sequence; remove also marks an entry stale. pop skips stale entries until it finds the current one. The sequence gives stable ties, the map gives O(1) lookup, heap operations are O(log n), and periodic rebuilding bounds lazy-entry space.”

Step-by-step deep dive

Step 1: Define invariants and operation contracts

The root must be the smallest (priority, sequence) among valid entries. The map stores the current entry for each task. A task has at most one valid entry; stale entries may remain in the heap but can never be returned. Define whether an empty pop raises an error or returns an empty value.

Step 2: Choose comparable heap entries

Use [priority, sequence, task]. The monotonic sequence makes equal priorities comparable without comparing task objects. If the business priority direction is reversed, negate it or wrap a comparator consistently; do not mix rules between operations.

Step 3: Implement add and update

The first add allocates a sequence and writes the entry to both map and heap. update verifies existence, marks the old entry REMOVED, inserts a new entry, and replaces the map pointer. There is no heap search or manual sift, so the operation remains O(log n).

add(task, priority):
    if task is active: mark old entry removed
    entry = [priority, next(sequence), task]
    current[task] = entry
    heappush(heap, entry)

Step 4: Implement remove with lazy deletion

remove deletes the task from the map and replaces the task field in its heap entry with REMOVED. Removing from the array directly would break the heap and require extra repair. Lazy deletion touches one known entry per mutation, at the cost of temporary garbage.

Step 5: Make pop skip stale entries

Repeatedly pop the root. If it is marked REMOVED, continue. If the map does not point to the exact entry being popped, it was superseded by an update, so skip it. For a valid entry, delete the map key and return the task. Raise the empty-queue error only after the heap is exhausted.

Step 6: Prove complexity and amortized bounds

add, update, and remove perform one heap insertion or a constant-time mark, giving O(log n) or O(1) marking. Each stale entry is popped at most once, so skipped work amortizes to the update or removal that created it. If updates continue without pops, space grows and a rebuild is required.

Step 7: Design rebuilding and space control

When heap length exceeds a fixed multiple of valid entries, such as 2x, or stale entries pass a threshold, retain current entries from the map and rebuild the heap. Rebuild costs O(n), but low-frequency triggers keep amortized cost bounded. With a known task limit, cleanup can also run after a batch of updates.

Step 8: Cover boundary tests

Test an empty queue, stable equal priorities, repeated updates, remove-then-pop, an old updated entry reaching the root, all entries becoming stale, non-comparable task objects, and identical results before and after rebuild. Differential-test random operations against a simple dictionary plus sorted-list model.

Trade-offs and boundaries

Trade-off 1: Lazy deletion or indexed heap

Lazy deletion is short and low-risk for a general implementation. An indexed heap removes immediately and controls space, but maintaining positions during swaps is more bug-prone. Choose an indexed heap only when delete rate and memory limits justify it.

Trade-off 2: Can the sequence overflow?

Fixed-width integers can wrap and break stable ordering. Use an unbounded integer or renumber all active entries during a safe rebuild. Never reset the counter while active entries still depend on old values.

Trade-off 3: Error or empty value

Libraries commonly raise a clear empty-queue exception, allowing callers to distinguish “no task” from a task whose value is null. If an API returns an empty value, document the ambiguity and disallow a conflicting task value.

Failure drills and evolution plan

Drill 1: Repeatedly update one task

Update one task 10,000 times, then pop and verify the latest priority is returned exactly once. Observe stale-entry growth, trigger a rebuild, and recheck the heap invariant.

Drill 2: Random mixed operations

Generate random add, update, remove, and pop operations and compare with a dictionary plus sorted-list model. Focus on equal-priority sequence order and ensuring old updated entries never leak.

Drill 3: Errors and resource limits

Call update/remove for missing tasks, pop an empty queue, and trigger rebuild at a memory threshold. Verify stable error types, no lost tasks, and no partially rebuilt state exposed to callers.

Common mistakes and follow-ups

Mistake 1: Storing only priority and task

Task objects may not be comparable, causing equal-priority comparisons to fail. Add a stable sequence or a non-comparable wrapper.

Mistake 2: Mutating a heap entry in place for update

The entry may no longer be in the correct position, violating the heap invariant. Mark the old entry stale and insert a new one.

Mistake 3: Calling array remove for deletion

The search is O(n), followed by heap repair. Use the map to locate the entry and mark it stale.

Mistake 4: Checking only the task field in pop

An old updated entry can still carry the same task ID. Confirm that the popped object is the current map entry.

Mistake 5: Ignoring stale-entry space

Lazy deletion still consumes memory. Set a rebuild threshold and monitor heap length, valid-entry count, and stale ratio.

Mistake 6: Leaving priority direction implicit

A min-heap returns the smallest value first. If larger numbers mean higher business priority, define the conversion in the contract so add and pop agree.