Dynamic Least-Loaded Job Dispatcher
Cresta● HardFULLTIMEPHONE SCREENProblem statement
Process operations on a job dispatcher. Executors retain insertion order, each executor owns a FIFO queue, and the dispatcher maintains a round-robin cursor into the current executor order.
["ADD", executor]adds an empty executor and returnsOK.["DISPATCH", job]chooses an executor with the smallest queue. If several are tied, scan cyclically from the cursor and choose the first tied executor. Advance the cursor to the executor after the chosen one, enqueue the job, and return the chosen executor ID.["EXECUTE", executor]removes and returns that executor's oldest job, or the empty string when its queue is empty.["REMOVE", executor]removes the executor, then redistributes its queued jobs in FIFO order using the same dispatch rule. ReturnOK.["STATE"]returns all executors in insertion order asexecutor:job1,job2groups joined by|. An empty queue has nothing after the colon.
Return one result for every operation.
Function
runDispatcher(operations: String[][]) → String[]Examples
Example 1
operations = [["ADD","a"],["ADD","b"],["DISPATCH","j1"],["DISPATCH","j2"],["DISPATCH","j3"],["STATE"],["EXECUTE","a"],["DISPATCH","j4"],["STATE"]]return = ["OK","OK","a","b","a","a:j1,j3|b:j2","j1","b","a:j3|b:j2,j4"]Least-load choices dominate; the cursor resolves the two equal-load ties.
Example 2
operations = [["ADD","a"],["ADD","b"],["ADD","c"],["DISPATCH","j1"],["DISPATCH","j2"],["DISPATCH","j3"],["DISPATCH","j4"],["REMOVE","a"],["STATE"]]return = ["OK","OK","OK","a","b","c","a","OK","b:j2,j1|c:j3,j4"]The removed executor's jobs are redistributed in their original FIFO order.
Example 3
operations = [["ADD","solo"],["EXECUTE","solo"],["STATE"]]return = ["OK","","solo:"]Executing an empty queue returns the empty string.
Constraints
1 <= operations.length <= 100000.- Executor and job IDs contain 1 to 30 alphanumeric characters and contain neither comma, colon, nor vertical bar.
- An executor is added at most once while present, and every referenced executor exists.
DISPATCHoccurs only when at least one executor exists.REMOVEoccurs only when at least one other executor remains.- Each job ID is dispatched at most once.