FastPrepDurable Work Queue Operations
Problems/Durable Work Queue Operations

Durable Work Queue Operations

OpenAI logoOpenAI● HardFULLTIMEPHONE SCREENONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The queue operations and dependency follow-up match the interview report at about 90%. The visible task reference supplies fixed leases, attempts, global reservation tokens, stale-token rejection and ordered dead-letter behavior. The retained string-ID batch interface, optional dependency-index encoding, STATUS results, JSON DLQ string and examples are explicit practice conventions.

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; return ADDED. For the dependency follow-up, ADD j1,j2,... names distinct earlier ADD operation indices as prerequisites. Such a task stays BLOCKED until all prerequisites complete successfully. A dependency already completed is satisfied immediately.
  • RESERVE: reserve the oldest available task until t + leaseDuration, increment its attempt count, and return taskId:token. Return NONE when 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. Return COMPLETED or IGNORED. Append newly ready dependents in original ADD order.
  • FAIL token: for a current valid reservation, append the task to the ready tail and return REQUEUED if attempts remain, or dead-letter it and return DEAD after maxAttempts reservations. Otherwise return IGNORED.
  • STATUS: return BLOCKED, AVAILABLE, RESERVED, COMPLETED, DEAD, or MISSING.
  • 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 <= 200000 and 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.

More OpenAI problems

  • Determine the Winner of Three-Card HandsPHONE SCREEN · Seen Nov 2026
  • Sparse Plant Infection SimulationPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Light Source Hits: Sample, Compare, and FitPHONE SCREEN · Seen Nov 2026
All OpenAI interview questionsSee OpenAI hiring insights
Saved
class Solution {
    public String[] runWorkQueue(String[] operations, String[] taskIds, int[] timestamps, int leaseDuration, int maxAttempts) {
        // Write your code here.
    }
}
Checking account…