Beyond Big O

Bounded worker scheduling

Bounded worker scheduling

Medium

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
1
queueLimit
0
events
[]
Expected return
Empty list
Test data
Input
{"workers":1,"queueLimit":0,"events":[]}
Expected output
[]

Example 2 · capacity and fifo

Arguments
workers
2
queueLimit
1
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
1
queueLimit
2
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
1
queueLimit
0
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

Editor options
Typing preferences

Saved in this browser.

Restoring local drafts…