Durable Work Queue Operations
Problem statement
Simulate a durable work queue over an ordered batch. Operation i uses operations[i], literal taskIds[i], and nondecreasing time timestamps[i]. Before every operation at time t, expire active reservations with deadline at most t, ordered by deadline and then reservation token. A reservation is valid only while t < deadline.
Each successful reservation consumes one attempt and receives the next positive token globally across tasks. Retrying a task creates a new token; old tokens never become valid again.
ADD: add the unique nonempty task ID to the available tail; returnADDED. For the dependency follow-up,ADD j1,j2,...names distinct earlier ADD operation indices as prerequisites. Such a task staysBLOCKEDuntil all prerequisites complete successfully. A dependency already completed is satisfied immediately.RESERVE: reserve the oldest available task untilt + leaseDuration, increment its attempt count, and returntaskId:token. ReturnNONEwhen no task is ready; ignore this operation's taskIds entry.COMPLETE token: complete the named task only if the supplied token is its current valid reservation. ReturnCOMPLETEDorIGNORED. Append newly ready dependents in original ADD order.FAIL token: for a current valid reservation, append the task to the ready tail and returnREQUEUEDif attempts remain, or dead-letter it and returnDEADaftermaxAttemptsreservations. Otherwise returnIGNORED.STATUS: returnBLOCKED,AVAILABLE,RESERVED,COMPLETED,DEAD, orMISSING.DLQ: return a compact JSON-array string containing dead-letter task IDs in arrival order, or[]. Reading never removes tasks.
Expiry follows the valid-failure retry rule without its own output. Completed and dead-lettered tasks never re-enter the ready queue. Failure or expiry does not satisfy a dependency; a dead-letter prerequisite leaves its dependents blocked. A token-free COMPLETE or FAIL returns IGNORED. Return one result string per input operation.
For this exercise, operation strings carry tokens and optional dependency indices while retaining the five-argument batch interface. A sequence of initial ADD operations represents the constructor task list; later ADD operations represent enqueue calls. String IDs and STATUS remain part of the practice interface.
Function
runWorkQueue(operations: String[], taskIds: String[], timestamps: int[], leaseDuration: int, maxAttempts: int) → String[]Examples
Example 1
operations = ["ADD","ADD","RESERVE","FAIL 1","RESERVE","COMPLETE 2","RESERVE"]taskIds = ["a","b","","a","","b",""]timestamps = [0,0,1,2,2,3,4]leaseDuration = 3maxAttempts = 2return = ["ADDED","ADDED","a:1","REQUEUED","b:2","COMPLETED","a:3"]Retry moves behind the next ready task; each reservation returns its token.
Example 2
operations = ["ADD","ADD 0","RESERVE","COMPLETE 1","RESERVE","FAIL 2","DLQ"]taskIds = ["a","b","","a","","b",""]timestamps = [0,0,0,1,1,2,2]leaseDuration = 5maxAttempts = 1return = ["ADDED","ADDED","a:1","COMPLETED","b:2","DEAD","[\"b\"]"]Successful prerequisite completion releases a dependent; exhausted failure enters DLQ.
Example 3
operations = ["ADD","RESERVE","RESERVE","COMPLETE 1","COMPLETE 2"]taskIds = ["x","","","x","x"]timestamps = [0,0,3,3,4]leaseDuration = 3maxAttempts = 2return = ["ADDED","x:1","x:2","IGNORED","COMPLETED"]A stale first token cannot complete the newer reservation.
Constraints
1 <= operations.length <= 200000and all three arrays have equal length.- Each command has a documented form. Timestamps are nondecreasing in
0..10^9. 1 <= leaseDuration <= 10^9,1 <= maxAttempts <= 100000.- Every ADD uses a unique nonempty printable ASCII task ID of length at most
50. - Dependency indices refer to distinct earlier ADD operations, so dependencies form a DAG. Tokens are positive integers; omitted tokens and tokens that were never issued are invalid.