Job Dispatcher with Least-Loaded, Round-Robin Assignment and Executor Removal

Implement a simple job dispatcher that distributes incoming jobs to a pool of executors (workers). Each job is represented by an integer ID. Executors are added and removed while the system is running. Define two classes. **`Executor`**: a worker that accepts jobs. Each executor has a string ID and: - `assign_job(job_id: int)` stores the job in the executor's queue of pending jobs. - `execute_next_job()` removes the next job from the executor's queue. All executors handle the same kind of job, and you do not need to implement any real processing logic. **`JobDispatcher`** (the load balancer): keeps the executors and distributes jobs to them. It has: - `add_executor(executor: Executor)` to add an executor. - `remove_executor(executor_id: str)` to remove an executor. The jobs still queued on the removed executor must be reassigned to the remaining executors. - `dispatch(job_id: int)` to assign a job to one of the executors. - `get_state()`, which returns a mapping from executor ID to that executor's list of pending jobs. **Dispatch policy:** send each job to the executor with the fewest pending jobs; when several executors are tied for the fewest, choose among them round-robin. Design this policy before writing the rest, because it shapes the whole implementation. ```hint Pin down "round-robin among the tied" Write out, for three executors and a few dispatches and completed jobs, which executor you expect to receive each job. Then decide what state the dispatcher must keep to reproduce that sequence. ``` ```hint Where does the load live An executor's queue shrinks through `execute_next_job` without the dispatcher being involved. Decide how the dispatcher sees that change before you choose a structure for finding the least-loaded executor. ``` ### Constraints and Clarifications - An executor's queue is first-in, first-out: the "next" job is the oldest pending one. - An executor's load is the number of jobs currently pending in its queue. - Executor IDs are unique among the executors registered with the dispatcher. ### Clarifying Questions - What exactly does round-robin mean among tied executors: rotating through executors in the order they were added, or preferring the one that received a job least recently? - In what order should a removed executor's pending jobs be reassigned, and should they be placed behind the jobs already queued on the other executors? - What should happen when `dispatch` is called with no executors, or when the last executor is removed while it still has jobs? - What should `remove_executor` do for an unknown ID, and `add_executor` for an ID that is already registered? - Can `execute_next_job` be called directly on an executor, and must the dispatcher still see the reduced load when that happens? - Roughly how many executors and jobs should the design handle? (This decides whether a linear scan per dispatch is acceptable.) ### What a Strong Answer Covers - A precise, deterministic definition of the least-loaded, round-robin rule, checked against a hand-traced example - A load view that stays correct when executors finish jobs on their own - Removal that reassigns every queued job exactly once through the same policy, with nothing lost or duplicated - Defined behavior with no executors, for duplicate or unknown IDs, and for an empty queue - Time complexity of dispatch, removal and `get_state`, and when to replace a scan with a priority structure - Tests for ties, rotation, removal with pending jobs, and removal of the last executor ### Follow-up Questions - With thousands of executors, how do you make dispatch faster than a linear scan while keeping the same tie-break, and what must happen when an executor finishes a job? - Executors now have different capacities, such as a maximum queue length or different speeds. How does the policy change? - `dispatch`, `remove_executor` and `execute_next_job` are called from several threads. What must be synchronized, and how do you avoid assigning a job to an executor that is being removed? - An executor crashes instead of being removed cleanly. How do you make sure its queued jobs are not lost?