Durable Work Queue with Dependencies
Problem statement
Simulate an at-least-once work queue with retry limits, reservation timeouts, preemption cooldowns, a dead-letter queue, and job dependencies. Start at time zero with no jobs, and return one result string for every operation.
ENQUEUE id timeout maxRetries dependencies: create a job. Dependencies is-or a comma-separated list of already-enqueued IDs. ReturnOK, orINVALIDfor a duplicate ID, unknown dependency, or self-dependency.RESERVE id: among queued jobs whose dependencies have passed, find the earliest queued entry. Reserve it only when its ID equalsid; returnOKorUNAVAILABLE. The reservation expires at current time plus timeout.PASS id: mark a running job passed; returnOK, otherwiseINVALID.FAIL id: fail a running job; returnOK, otherwiseINVALID.PREEMPT id cooldown: end a running reservation without recording a failure. The job cools down until preemption time pluscooldown; returnOK, otherwiseINVALID.ADVANCE_TIME delta: advance time, process every reservation whose deadline is at or before the new time, and release every completed cooldown; returnOK.GET_DLQ: return dead-lettered IDs in arrival order joined by commas, orEMPTY.
A failure or timeout increments the job's failure count and requeues it at the tail while another retry remains. A job with maxRetries = r enters the dead-letter queue after its r + 1-th failure or timeout. Preemption does not increment this count.
Before each non-time operation, process all due time transitions. Expirations are processed by deadline and then original enqueue order. Jobs whose cooldown has ended are processed by original enqueue order and reinserted before the first currently queued job with a later original enqueue order, or at the tail if none exists. A dependent job is reservable only after every dependency has passed; a dead-lettered dependency leaves it blocked.
Function
simulateDurableQueue(operations: String[]) → String[]Examples
Example 1
operations = ["ENQUEUE a 5 1 -","ENQUEUE b 3 0 a","RESERVE b","RESERVE a","ADVANCE_TIME 5","RESERVE a","PASS a","RESERVE b","PASS b","GET_DLQ"]return = ["OK","OK","UNAVAILABLE","OK","OK","OK","OK","OK","OK","EMPTY"]Job a times out once, succeeds on its retry, and then unlocks dependent job b.
Example 2
operations = ["ENQUEUE a 1 0 -","RESERVE a","ADVANCE_TIME 1","GET_DLQ","RESERVE a"]return = ["OK","OK","OK","a","UNAVAILABLE"]With no retries, the first expired reservation sends a to the dead-letter queue.
Example 3
operations = ["ENQUEUE a 10 0 -","ENQUEUE b 10 0 -","ENQUEUE c 10 0 -","RESERVE a","PREEMPT a 5","ADVANCE_TIME 5","RESERVE b","RESERVE a","PASS a","RESERVE b"]return = ["OK","OK","OK","OK","OK","OK","UNAVAILABLE","OK","OK","OK"]When a's cooldown ends, its original enqueue order places it before b and c, so requesting b first is unavailable.
Constraints
1 <= operations.length <= 10000.- Accepted job IDs are unique nonempty alphanumeric strings.
1 <= timeout, cooldown, delta <= 1000000000and0 <= maxRetries <= 100.- Every dependency list contains distinct IDs and refers only to earlier accepted jobs.
- Every operation has one of the documented shapes, and time fits in a signed 64-bit integer.