Bounded worker scheduling

Your task

A worker pool has a fixed number of workers and a FIFO waiting room.
Apply a sequence of events and report a snapshot after every event.
This is a deterministic exercise in concurrency reasoning: do not create threads, goroutines, timers or background work.

Required API

ScheduleWorkers
func ScheduleWorkers(workers, queueLimit int, events []Event) []Snapshot
Event.Kind
Kind string
Event.Job
Job string
Event.Token
Token int
Run.Job
Job string
Run.Token
Token int
Snapshot.Accepted
Accepted bool
Snapshot.Active
Active []Run
Snapshot.Waiting
Waiting []string

Behavior

A submit event is accepted only when its job ID is neither running nor waiting, and a worker or waiting-room slot is available.
Start immediately if a worker is free; otherwise append the job to the waiting room.
Rejected submits change nothing.
Every start receives the next global dispatch token, beginning at 1.
Allocate tokens only when a job actually starts.

A complete event is accepted only for a running job with the matching dispatch token.
A cancel event is accepted only for a running or waiting job.
An accepted completion or cancellation removes that job.
Whenever a worker becomes free, immediately start the oldest waiting job with a fresh token.
Cancellation here is an authoritative simulated event that releases the worker immediately; a real runner may require separate cleanup confirmation.
A released job ID may be submitted again, so an old completion token must never finish its newer run.

Return one Snapshot per event: Accepted indicates whether the event changed state; Active lists running jobs in dispatch order, and Waiting lists queued IDs in FIFO order.
Previously returned snapshots must remain unchanged when later events run.
Empty lists are represented as [].
Do not mutate input events, and keep separate calls independent.

Constraints

Input is valid: workers is 1–3; queueLimit is 0–3; there are 0–16 events.
Each event has kind submit, complete or cancel, an ASCII ID matching [A-Za-z0-9_-]{1,8}, and a token from 0–1,000,000.
Submit/cancel tokens are always 0; only complete uses the supplied token.
Queue capacity counts waiting jobs only, excluding running jobs.
There is no automatic completion, timeout or retry.
Use only the standard library.

Notes and example notation

Examples encode events as [kind, job, token], active runs as {job, token}, and each snapshot as {accepted, active, waiting}.

Examples

The runner calls your functions directly; you do not need to parse JSON.

Example 1 · empty

Arguments

workers

queueLimit

events

[]

Expected return

Empty list

Test data

Input

{"workers":1,"queueLimit":0,"events":[]}

Expected output

[]

Example 2 · capacity and fifo

Arguments

workers

queueLimit

events

[
  [
    "submit",
    "b",
    0
  ],
  [
    "submit",
    "A",
    0
  ],
  [
    "submit",
    "t",
    0
  ],
  [
    "submit",
    "x",
    0
  ],
  [
    "complete",
    "b",
    1
  ]
]

Expected return

[
  {
    "accepted": true,
    "active": [
      {
        "job": "b",
        "token": 1
      }
    ],
    "waiting": []
  },
  {
    "accepted": true,
    "active": [
      {
        "job": "b",
        "token": 1
      },
      {
        "job": "A",
        "token": 2
      }
    ],
    "waiting": []
  },
  {
    "accepted": true,
    "active": [
      {
        "job": "b",
        "token": 1
      },
      {
        "job": "A",
        "token": 2
      }
    ],
    "waiting": [
      "t"
    ]
  },
  {
    "accepted": false,
    "active": [
      {
        "job": "b",
        "token": 1
      },
      {
        "job": "A",
        "token": 2
      }
    ],
    "waiting": [
      "t"
    ]
  },
  {
    "accepted": true,
    "active": [
      {
        "job": "A",
        "token": 2
      },
      {
        "job": "t",
        "token": 3
      }
    ],
    "waiting": []
  }
]

Test data

Input

{"workers":2,"queueLimit":1,"events":[["submit","b",0],["submit","A",0],["submit","t",0],["submit","x",0],["complete","b",1]]}

Expected output

[{"accepted":true,"active":[{"job":"b","token":1}],"waiting":[]},{"accepted":true,"active":[{"job":"b","token":1},{"job":"A","token":2}],"waiting":[]},{"accepted":true,"active":[{"job":"b","token":1},{"job":"A","token":2}],"waiting":["t"]},{"accepted":false,"active":[{"job":"b","token":1},{"job":"A","token":2}],"waiting":["t"]},{"accepted":true,"active":[{"job":"A","token":2},{"job":"t","token":3}],"waiting":[]}]

Example 3 · cancel promotes

Arguments

workers

queueLimit

events

[
  [
    "submit",
    "a",
    0
  ],
  [
    "submit",
    "b",
    0
  ],
  [
    "submit",
    "c",
    0
  ],
  [
    "cancel",
    "b",
    0
  ],
  [
    "cancel",
    "a",
    0
  ],
  [
    "complete",
    "a",
    1
  ]
]

Expected return

[
  {
    "accepted": true,
    "active": [
      {
        "job": "a",
        "token": 1
      }
    ],
    "waiting": []
  },
  {
    "accepted": true,
    "active": [
      {
        "job": "a",
        "token": 1
      }
    ],
    "waiting": [
      "b"
    ]
  },
  {
    "accepted": true,
    "active": [
      {
        "job": "a",
        "token": 1
      }
    ],
    "waiting": [
      "b",
      "c"
    ]
  },
  {
    "accepted": true,
    "active": [
      {
        "job": "a",
        "token": 1
      }
    ],
    "waiting": [
      "c"
    ]
  },
  {
    "accepted": true,
    "active": [
      {
        "job": "c",
        "token": 2
      }
    ],
    "waiting": []
  },
  {
    "accepted": false,
    "active": [
      {
        "job": "c",
        "token": 2
      }
    ],
    "waiting": []
  }
]

Test data

Input

{"workers":1,"queueLimit":2,"events":[["submit","a",0],["submit","b",0],["submit","c",0],["cancel","b",0],["cancel","a",0],["complete","a",1]]}

Expected output

[{"accepted":true,"active":[{"job":"a","token":1}],"waiting":[]},{"accepted":true,"active":[{"job":"a","token":1}],"waiting":["b"]},{"accepted":true,"active":[{"job":"a","token":1}],"waiting":["b","c"]},{"accepted":true,"active":[{"job":"a","token":1}],"waiting":["c"]},{"accepted":true,"active":[{"job":"c","token":2}],"waiting":[]},{"accepted":false,"active":[{"job":"c","token":2}],"waiting":[]}]

Example 4 · stale completion

Arguments

workers

queueLimit

events

[
  [
    "submit",
    "a",
    0
  ],
  [
    "cancel",
    "a",
    0
  ],
  [
    "submit",
    "a",
    0
  ],
  [
    "complete",
    "a",
    1
  ],
  [
    "complete",
    "a",
    2
  ]
]

Expected return

[
  {
    "accepted": true,
    "active": [
      {
        "job": "a",
        "token": 1
      }
    ],
    "waiting": []
  },
  {
    "accepted": true,
    "active": [],
    "waiting": []
  },
  {
    "accepted": true,
    "active": [
      {
        "job": "a",
        "token": 2
      }
    ],
    "waiting": []
  },
  {
    "accepted": false,
    "active": [
      {
        "job": "a",
        "token": 2
      }
    ],
    "waiting": []
  },
  {
    "accepted": true,
    "active": [],
    "waiting": []
  }
]

Test data

Input

{"workers":1,"queueLimit":0,"events":[["submit","a",0],["cancel","a",0],["submit","a",0],["complete","a",1],["complete","a",2]]}

Expected output

[{"accepted":true,"active":[{"job":"a","token":1}],"waiting":[]},{"accepted":true,"active":[],"waiting":[]},{"accepted":true,"active":[{"job":"a","token":2}],"waiting":[]},{"accepted":false,"active":[{"job":"a","token":2}],"waiting":[]},{"accepted":true,"active":[],"waiting":[]}]

Related guides

Retry Queue Correctness: Duplicate Work, Retry Boundaries, and Cancellation

Solution guide

Reveal solution guide — spoilers

Approach

Represent active dispatches separately from the FIFO waiting queue and associate each active job with its current dispatch token.
Process one explicit event at a time. Admit only within the worker and waiting limits, and accept completion only for the matching active token. Cancellation removes the current job state without accepting later stale completions.
After an event frees a worker, dispatch waiting work in FIFO order and assign a fresh monotonic token. Report the exact post-event snapshot required by the contract.

Why it works

Separate active and waiting state makes both capacity bounds explicit. A dispatch token identifies an execution attempt rather than just a reusable job ID, so a late completion cannot finish a replacement. Processing explicit events models these ownership decisions deterministically; it does not test operating-system thread interleavings.

Complexity

Using maps and a linked FIFO gives expected O(1) state transitions plus the cost of each required snapshot. A simple array queue may use linear removal; total output size is a necessary lower bound on runtime and storage.

Edge cases to check

Zero waiting capacity still permits dispatch to an idle worker when the contract allows it.
Cancelling an active job can immediately release a worker for the oldest waiting job.
A reused ID needs a fresh dispatch token; repeated cancellation and stale completion must not mutate state.

Restoring local drafts…