At-Least-Once Job Queue with Timeouts, Retries, a Dead-Letter Queue and Dependencies

Implement an in-memory task scheduling queue that provides at-least-once delivery and has a dead-letter queue (DLQ). The reported interface is: - `enqueue(job_id, timeout, max_retry)`: add a job. - `reserve(job_id)`: a worker claims the job in order to run it. - `pass(job_id)`: the worker reports that the job succeeded. - `fail(job_id)`: the worker reports that the job failed. - `get_dlq()`: return the jobs that have been given up on. The source gives only these names and parameters. Start from the standard reading of at-least-once delivery and confirm the details: a reservation lasts `timeout`; a reserved job that is neither passed nor failed within that time is treated as failed and becomes available again, so a job can be delivered more than once; a failed job is retried until its `max_retry` retries are used up, after which it moves to the DLQ. ### Constraints and Clarifications - Single process, in memory. Persistence is a follow-up, not a requirement. - Make the clock injectable, so tests can move time forward without sleeping. - In Python, `pass` is a reserved word, so name that method `pass_`, `ack` or similar. - Job ids are unique. ### Clarifying Questions - `reserve` is reported as taking a job id. Does the caller choose which job to run, or should there also be a call that returns the next ready job, and in what order? - Does `max_retry` count retries after the first attempt, allowing up to `max_retry + 1` attempts, or total attempts? - Does a reservation that times out use up a retry in the same way as an explicit `fail`? - What should `pass` and `fail` do for a job that is not currently reserved, including one whose reservation has already timed out? - Must a timeout be acted on at the moment it expires, or is it enough to notice it on the next call? - Should `get_dlq` return job ids, or job records with their failure history? ### Part 1 — The core queue Implement the five operations with the semantics you agreed on. Keep each operation efficient when many jobs are reserved at the same time. ```hint Model the life of a job List the states a job can be in, and which operation, or the passage of time, moves it from one state to the next, before writing any method. ``` ```hint Finding expired reservations When a call arrives, how do you find the reservations that have run out without scanning every reserved job? And how do you ignore a timer for a reservation that has already ended? ``` #### What This Part Should Cover - An explicit job state machine and correct retry accounting - Efficient detection of expired reservations, with stale timers ignored after a job moves on - Defined results for unknown jobs and for operations on jobs in the wrong state - Tests driven by a controllable clock ### Part 2 — Dependencies Extend `enqueue` with a `depends_on: list[job_id]` parameter. A job must not be reservable until every job it depends on has passed. ```hint Avoid rescanning When a job passes, how do you find the waiting jobs it unblocks, and tell whether each one still waits on something else, without looking at every waiting job? ``` #### Clarifying Questions for this Part - May `depends_on` name a job that has not been enqueued yet, or one that has already passed? - If a dependency ends up in the DLQ, what happens to the jobs waiting on it? - Can the dependencies form a cycle, and if so, how should it be detected? #### What This Part Should Cover - For each job, a count of unfinished dependencies, plus a reverse index from a job to the jobs waiting on it - A defined outcome when a dependency is dead-lettered, applied transitively - Validation of `depends_on`, and why cycles can or cannot arise under the chosen rules ### What a Strong Answer Covers - Semantics agreed before coding: retry counting, late acknowledgments and the `reserve` contract - The consequence of at-least-once delivery: a job can run more than once, so job handlers must be idempotent - Time and space complexity of every operation - Readable code with tests that use a fake clock - A thread-safety plan for concurrent workers ### Follow-up Questions - How would you make the queue survive a process restart without losing jobs? - A worker finishes after its reservation expired and another worker has reserved the same job. How would you stop the late `pass` or `fail` from acting on the new reservation? - How would you add a delay between retries with exponential backoff? - How would you let an operator move a job from the DLQ back into the queue, and what should happen to the jobs that depend on it?