Implement an in-memory job queue with priorities, retries and a dead-letter list.

How to answer

A priority heap is quick. Spend the time on what happens when a job or a worker fails.

1. Pin the interface and the promise. “enqueue(payload, priority), lease() returns a job and token, ack(id, token), nack(id, token, error). Lower numbers run first, first in first out within a priority.” Then say the delivery promise: at least once. A worker can finish the work and die before it acks, so handlers must be safe to run twice.
2. Choose the structures aloud. A heap of (priority, seq, job_id): the counter keeps FIFO order within a priority, and holding the id rather than the payload means the heap never compares payloads. A second heap holds retries waiting out their backoff, keyed by ready time. A third holds lease deadlines. Stale heap entries are skipped when popped, not removed from the middle, so each heap operation stays O(log n).
3. Count an attempt when the job is handed out. A job that crashes its worker never calls nack. If only failures count, it loops forever.
4. Make leases expire, and check tokens. An expired lease returns the job to the queue. The late worker’s ack must then be refused, or it deletes a job another worker is running.
5. Bound the retries, then keep the evidence. Back off between attempts, stop at a limit, and move the job to the dead-letter list with every error and its time. Offer a redrive for after the cause is fixed.
6. Test with a fake clock. Priority order, backoff, a lease timeout, a stale ack and a poison job that ends in dead letters, all without sleeping.

The trap is a dead-letter list that holds only job ids. Whoever reads it needs the payload, the attempts and the errors to decide whether a replay is safe.