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):

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.

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:

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.

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