FastPrepDurable Work Queue with Dependencies
Problems/Durable Work Queue with Dependencies

Durable Work Queue with Dependencies

OpenAI logoOpenAI● HardFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The original interview report specifies enqueue, reserve, pass, fail, dead-letter retrieval, at-least-once delivery, timeouts, retry limits, and dependencies. A later report adds preemption cooldown measured from the preemption timestamp and re-entry ordered by the original enqueue time. The finite operation sequence supplies the deterministic adapter and return tokens.

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. Return OK, or INVALID for 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 equals id; return OK or UNAVAILABLE. The reservation expires at current time plus timeout.
  • PASS id: mark a running job passed; return OK, otherwise INVALID.
  • FAIL id: fail a running job; return OK, otherwise INVALID.
  • PREEMPT id cooldown: end a running reservation without recording a failure. The job cools down until preemption time plus cooldown; return OK, otherwise INVALID.
  • ADVANCE_TIME delta: advance time, process every reservation whose deadline is at or before the new time, and release every completed cooldown; return OK.
  • GET_DLQ: return dead-lettered IDs in arrival order joined by commas, or EMPTY.

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 <= 1000000000 and 0 <= 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.

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[] simulateDurableQueue(String[] operations) {
        // Write your code here.
    }
}
Checking account…