Implement a fault-tolerant work queue that never loses tasks when workers fail

Implement a fault-tolerant work queue. Producers submit tasks to the queue, and workers take tasks from it and process them. A worker can crash, hang, or report an error at any point while it holds a task. The queue must guarantee that no task is lost because the worker holding it failed: every submitted task must eventually be completed by some worker, or deliberately set aside as one that cannot be completed. Propose the queue's interface, implement it as a class with runnable code, and show tests that simulate worker failures. ```hint Taken is not finished When a worker takes a task, the task leaves the line of waiting work, but the queue still owes it to someone. Decide what record the queue keeps between "handed out" and "done". ``` ```hint A crashed worker sends nothing A worker that crashes never reports back, so the queue needs its own rule for deciding that a task has been abandoned. Make time something your tests can control. ``` ```hint The worker that comes back Consider a worker that was presumed dead but finishes after its task was handed to someone else. Decide how the queue tells its report apart from the current holder's. ``` ### Constraints and Clarifications - In the reported interview this was a two-part coding exercise, checked by running the code against tests. The two parts were not described, so this version states the core task, and likely extensions appear as follow-up questions. - Assume the queue is an in-process data structure, and that a worker failure shows up either as an explicit failure report or as silence. ### Clarifying Questions - How should the queue detect a failed worker: an explicit failure call, a time limit on each task, periodic heartbeats from the worker, or a combination? - Is at-least-once processing acceptable, meaning a task may be processed twice if a slow worker is wrongly presumed dead, or must each task's effect happen exactly once? - Should a task that keeps failing be retried forever, or given up on after a limit, and where should it go then? - Do workers run concurrently on several threads, so that the queue must be thread-safe? - Must tasks be handed out in submission order, and where does a retried task go in that order? - Does the queue itself need to survive a process restart, or is in-memory state enough? ### What a Strong Answer Covers - Explicit task states and the transitions between them, with no path that drops a task - A failure-detection rule for silent workers, with an injectable clock so tests are deterministic - Rejection of late or duplicate reports from a worker that no longer owns the task - A bounded retry policy with a terminal state for tasks that always fail - Thread safety and the cost of each operation, including how abandoned tasks are found without scanning every task - Tests that cover a crash, a slow worker, a late report and a task that always fails ### Follow-up Questions - How would you make the queue survive a restart of its own process without losing tasks that were in progress? - Processing a task sends an email. How do you keep a redelivered task from sending it twice? - How would you support a task that legitimately runs longer than the failure-detection time limit? - What changes when workers are separate processes on other machines that talk to the queue over a network?