Katkat
Back

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

CrestaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

A coding exercise to implement Executor and JobDispatcher classes that send each integer job ID to the executor with the fewest pending jobs, breaking ties round-robin, while executors join and leave. It tests precise tie-break semantics, consistent load tracking, reassigning a removed executor's queued jobs, and edge cases.

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.

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

Hints

Hint 1

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 2

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.

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?