Fault-Tolerant Task Queue with Retry Cooldowns, a Dead-Letter Queue and Dependencies

Implement an in-memory task queue that tolerates worker failures. Workers take tasks from the queue; when a worker fails or is preempted while holding a task, the task goes back into the queue and is retried later, and a task that keeps failing is moved to a dead-letter queue (DLQ). The interview provided starter code and a set of unit tests that all had to pass, so the exact semantics below matter more than extra features. The queue exposes these operations: - `enqueue`: add a new task. - `reserve`: hand the next eligible task to a worker. - `fail`: report that a reserved task failed or was preempted, so it must be retried later. - The DLQ: tasks that have failed too often are moved there and are never handed out again. The exact signatures came from the starter code and are not reported. Assume this shape, with the current time passed in explicitly so the tests are deterministic: ```python class FaultTolerantQueue: def __init__(self, max_attempts: int) -> None: ... def enqueue(self, task_id: str, cooldown: int, now: int) -> None: ... def reserve(self, now: int) -> str | None: ... def fail(self, task_id: str, now: int) -> None: ... def dead_letter_queue(self) -> list[str]: ... ``` ### Constraints and Clarifications - Every task carries its own cooldown. After a task is failed or preempted, it cannot be reserved again until its cooldown has passed, counted from the timestamp of that failure: the task becomes eligible again at failure time + cooldown. Your code must compute this end time itself from the preemption timestamp. - When a failed task re-enters the queue, it is ordered by its **original** enqueue time, not by the time it failed or the time its cooldown ended. - `reserve(now)` returns the eligible task with the earliest original enqueue time and marks it reserved, or returns `None` when no task is eligible at `now`. - Assume a task moves to the DLQ when it has failed `max_attempts` times, and that the `now` values passed to the operations never decrease. Confirm both. ### Clarifying Questions - What sends a task to the DLQ: a maximum number of failures, a particular kind of failure, or an explicit call? Does a preemption count against that limit the same way as an ordinary failure? - Is a task eligible exactly at failure time + cooldown, or only strictly after it? - If two tasks have the same enqueue timestamp, which one is reserved first? - What should `fail` do for a task that is not currently reserved, and `enqueue` for an ID that already exists: raise an error or ignore the call? - In what order should the DLQ list its tasks, and can a task ever leave the DLQ? ### Part 1 — Retries, cooldowns and the dead-letter queue Implement the operations above. ```hint Two kinds of waiting A task that is cooling down and a task that is ready to run are waiting for different things. Decide which timestamp orders each group and when a task moves from one group to the other. ``` ```hint Trace the tricky case first Before coding, trace by hand: task A is enqueued first, reserved and failed; task C is enqueued later and never fails. Once A's cooldown is over, which task should the next reserve return, and does your design produce that? ``` #### What This Part Should Cover - Data structures that keep `reserve` and `fail` efficient, with their complexity - The cooldown end computed from the failure timestamp, including the boundary case - Ordering by original enqueue time after re-entry, with a deterministic tie rule - Attempt counting and the move to the DLQ ### Part 2 — Tasks with dependencies Tasks may now depend on other tasks: a task must not be reserved until every task it depends on has finished successfully. Extend `enqueue` with a list of dependency IDs. Cooldowns, retries, the DLQ and ordering by original enqueue time still apply. The source does not say how the queue learns that a task has finished. Assume a `complete(task_id, now)` call that a worker makes after a reserved task succeeds, and confirm it. ```hint Count what is missing For each blocked task, think about what you need to record so that finishing one task can unblock its dependents directly, without scanning every waiting task. ``` #### Clarifying Questions for this Part - Can a task depend on a task that has not been enqueued yet? If so, how should dependency cycles be handled? - If a dependency ends up in the DLQ, what should happen to the tasks waiting on it? - When a task becomes unblocked, is it ordered by its original enqueue time or by the time it was unblocked? #### What This Part Should Cover - Tracking unmet dependencies and dependents so that a completion unblocks tasks in time proportional to their number - How dependencies interact with failures, cooldowns and dead-lettered dependencies - Validation of unknown IDs, duplicates and cycles ### What a Strong Answer Covers - Pins down the semantics before coding: where the cooldown starts, the eligibility boundary, ordering on re-entry, and the DLQ rule - A clear state model for a task (blocked, ready, reserved, cooling, done, dead) with valid transitions only - Efficient data structures with stated time and space complexity - Tests aimed at the subtle cases: re-entry order, the cooldown boundary, the DLQ threshold and dependency chains - Behavior for invalid calls and for a worker that crashes without reporting back ### Follow-up Questions - A worker crashes after `reserve` and never calls `fail` or `complete`. How do you make sure the task is retried? - How would an operator replay tasks from the DLQ, and what should happen to their attempt counts and ordering? - How would the design change if many worker processes on different machines shared the queue? - Should a task's cooldown grow with each failure? How would you add exponential backoff without breaking the ordering rule?