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

Implement an in-memory, fault-tolerant task queue. Producers add tasks; workers reserve a task, process it, and then either finish it or report that it failed. A failed task is retried, and a task that keeps failing is moved to a dead-letter queue (DLQ), where it is never handed out again and can be inspected. The interviewer provides unit tests, and the solution must pass all of them. The task comes in two parts: Part 1 builds the queue with retries and the DLQ, and Part 2 adds dependencies between tasks. A possible interface (adjust it as you clarify): ```python class FaultTolerantQueue: def __init__(self, max_attempts: int): ... def enqueue(self, task_id: str, payload: object) -> None: ... def reserve(self) -> tuple[str, object] | None: ... def complete(self, task_id: str) -> None: ... def fail(self, task_id: str) -> None: ... def dead_letters(self) -> list[str]: ... ``` ### Constraints and Clarifications - The reported operations are `enqueue`, `reserve`, `fail` and the DLQ. A reserved task also needs a way to finish successfully, which the sketch calls `complete`; confirm its name and behavior against the tests. - The retry limit was not given, so it is the constructor parameter `max_attempts`. - "Fault-tolerant" here means the queue copes with failing tasks: retries and a DLQ. One process, in memory. Persistence and concurrent workers are follow-ups. - Task IDs are strings chosen by the producer. ### Clarifying Questions - Does `max_attempts` count the first attempt? With `max_attempts = 3`, does the third failure or the fourth send a task to the DLQ? - When a failed task is retried, does it go to the back of the queue or back to the front? Must it wait before it can be reserved again? - What should `reserve` return when no task is available? - What should `fail` or `complete` do when the task is not currently reserved: an unknown ID, a task already completed, or one already in the DLQ? - Can the same task ID be enqueued twice? - Can a worker reserve a task and then never call `complete` or `fail`, or may the tests assume every reservation is answered? - What does the DLQ need to expose: task IDs in the order they were dead-lettered, their payloads, a way to put them back? ### Part 1 — Retries and the dead-letter queue Implement `enqueue`, `reserve`, `complete`, `fail` and read access to the DLQ. Available tasks are handed out in the order they were enqueued, and a reserved task must not be handed to another worker. `fail` makes the task available again until it has used all of its attempts; after that it moves to the DLQ and is never reserved again. ```hint Name the states List the states a task can be in and which transition each method makes. Then choose structures that find the next available task without scanning every task the queue has seen. ``` #### What This Part Should Cover - Task states, legal transitions, and what happens on an invalid call - The exact attempt at which a task moves to the DLQ - Where a retried task goes, and the order in which tasks are reserved - The cost of each operation ### Part 2 — Dependencies between tasks Extend `enqueue` with an optional list of task IDs that the new task depends on: ```python def enqueue(self, task_id: str, payload: object, depends_on: list[str] | None = None) -> None: ... ``` A task may be reserved only after every task it depends on has completed successfully. Tasks without dependencies behave exactly as in Part 1, and the Part 1 tests must still pass. ```hint Count what is missing Rather than re-checking every waiting task on each `reserve`, decide which single event can make a waiting task available, and update only the tasks that event affects. ``` #### Clarifying Questions for this Part - Can a task depend on a task that has not been enqueued yet? - If a dependency ends up in the DLQ, what happens to the tasks waiting on it? - Can dependencies form a cycle, and if so, should `enqueue` reject it? - When several tasks become available at the same moment, which is reserved first? #### What This Part Should Cover - How a waiting task becomes available, and what that costs per completed task - What happens to the dependents of a task that is dead-lettered - Unknown, repeated, already-completed and cyclic dependencies - Extending the Part 1 code without changing its behavior ### What a Strong Answer Covers - Settles the unresolved policies (attempt counting, retry position, invalid calls, dependency failure) before writing code - An explicit task state machine that rejects invalid transitions instead of corrupting state - Constant-time `reserve`, and dependency bookkeeping that never scans all waiting tasks - Working code for both parts, checked against the provided tests and against its own edge cases - A clear account of what the in-memory design does not handle: lost workers, concurrency, restarts ### Follow-up Questions - A worker reserves a task and crashes without calling `fail`. How does the task get back into the queue, and what if the worker was only slow and calls `complete` later? - Several worker threads now call the queue concurrently. What has to be synchronized? - The queue must survive a process restart. What do you persist, and when? - A failed task must now wait before it can be retried, with the wait growing after each failure. What changes in your structures?