Machine coding · Schedulers and queues
Concurrent job scheduler with a swappable ordering policy
- Reported in several places
- SDE-2 (L4)
- Strategy
- State
- Producer-consumer
- 2 sources
Two or more independent public pages, at least one a candidate write-up.
Build a job scheduler whose code is demonstrable, handles edge cases and stays correct under concurrency and multithreading. Two candidates reported a machine coding round along these lines and neither shared the exact statement, so this answer fixes a concrete scope of its own: delayed start, an ordering rule that can be swapped, cancellation and retries.
Restated in our own words, not a quote from Uber or any page. The answer below is written for this site.
Clarify first
Pin the scope down before you name a single class.
Neither report gives the exact statement, so spend the first minutes pinning it down.
- Is a job a function that runs once, or does it repeat? Assume one-shot with an optional start delay.
- When several jobs are ready, what decides the order: priority, arrival, something else? Assume the rule must be replaceable.
- How many workers run at once, and can callers submit while jobs are running? Assume a fixed number and yes.
- Is a failed job retried, and can a waiting job be cancelled? Assume both.
In scope: submit with delay and priority, cancel, retries with exponential backoff, a fixed worker count, shutdown, and thread safety of the shared state. Out of scope: cron expressions, persistence across restarts, distributed workers and job dependencies.
Entities and relationships
Who owns what, and who talks to whom.
- Scheduler is the facade. It owns the job map, the two heaps and the worker slots, and exposes
submit,cancel,tick,drainandshutdown. - Job holds the task, priority, run time, retry settings and a status of PENDING, RUNNING, DONE, FAILED or CANCELLED. It owns the only legal move from PENDING to RUNNING,
claim(). - OrderingPolicy is the strategy interface with one method,
before(a, b).PriorityPolicy,FifoPolicyandOldestDuePolicyimplement it. - Heap is a small binary heap that takes a comparison function. The scheduler has a delayed heap ordered by run time and a ready heap ordered by the policy.
- Clock is injected so tests control time. The scheduler uses it and never reads the system clock itself.
The scheduler has many jobs, uses one policy and one clock, and each job is in at most one heap at a time.
The design
The class map, the main flow and the patterns that earn their place.
- A caller submits a spec and the scheduler creates a PENDING job.
- The job waits in the delayed heap, ordered by its run time.
- When the clock reaches the run time, the job moves to the ready heap.
- Each tick offers the ready jobs to the free worker slots.
- A slot pops the job the policy ranks first.
- The slot claims the job; only a successful claim runs the task.
Open on the whiteboardAll 3 diagrams on one tidy board, with a step-by-step walkthrough.
The scheduler keeps two heaps. The delayed heap holds submitted jobs ordered by runAt. The ready heap holds jobs that are due, ordered by the injected policy. Time decides when a job becomes eligible; the policy decides which eligible job goes next. Keeping those two questions in separate structures is what makes the policy swappable.
The Strategy pattern earns its place at the ready heap. Each policy implements before(a, b) and ends with the submission sequence number as a tie-break, so equal priorities still produce a stable, repeatable order. Changing the rule is one constructor argument and no scheduler code. The State idea is the job status: each transition is explicit and only claim() can move a job from PENDING to RUNNING.
Main flow:
submitvalidates the spec (task is a function, delay is not negative, id is unused), creates a PENDING job and pushes it on the delayed heap.tickfirst promotes every job whoserunAtis not afterclock.now()into the ready heap, dropping any that were cancelled.- It then fills worker slots 0 to N minus 1. For each slot it pops the best job and calls
claim(). If the claim fails, the job was cancelled after it was queued, so the entry is discarded and the next one is popped. - If the task throws and attempts are within the retry budget, the job returns to PENDING with
runAtmoved out bybackoff * 2 ** (attempts - 1)and goes back on the delayed heap. Otherwise it ends FAILED with the error message.
The model steps workers explicitly, one tick per call, so output is repeatable. The idea that carries over to real threads is that PENDING to RUNNING is the single decision point. Cancel and claim() both test the same status field and only act on PENDING, so a cancel that races a pop either wins (the worker sees CANCELLED and skips) or loses (cancel returns false because the job is already RUNNING). Nothing runs twice and nothing is cancelled after it started. In a real version that test-and-set is the part done under the lock.
A real version needs one lock around both heaps and the job map, a condition variable so idle workers sleep until the next runAt or a new submit instead of spinning, the state change done under that lock or with compare-and-set, and tasks run outside the lock so a slow task never blocks submit. Shutdown flips a flag, wakes the workers and lets them exit when the heaps are empty.
Trade-off: cancel uses lazy deletion. It is O(1) but leaves dead entries in the heaps until they are popped. An indexed heap removes them at once for O(log n) per cancel and more code. Submit and pop are O(log n).
The code
Runnable JavaScript, with the checks it passes.
class FakeClock {
constructor(start = 0) {
this.time = start;
}
now() {
return this.time;
}
advance(ms) {
this.time += ms;
}
}
class Heap {
constructor(before) {
this.before = before;
this.items = [];
}
get size() {
return this.items.length;
}
peek() {
return this.items[0];
}
push(item) {
const a = this.items;
a.push(item);
let i = a.length - 1;
while (i > 0) {
const parent = (i - 1) >> 1;
if (!this.before(a[i], a[parent])) break;
[a[i], a[parent]] = [a[parent], a[i]];
i = parent;
}
}
pop() {
const a = this.items;
const top = a[0];
const last = a.pop();
if (a.length > 0) {
a[0] = last;
let i = 0;
for (;;) {
const left = 2 * i + 1;
const right = left + 1;
let best = i;
if (left < a.length && this.before(a[left], a[best])) best = left;
if (right < a.length && this.before(a[right], a[best])) best = right;
if (best === i) break;
[a[i], a[best]] = [a[best], a[i]];
i = best;
}
}
return top;
}
}
class PriorityPolicy {
before(a, b) {
if (a.priority !== b.priority) return a.priority < b.priority;
return a.seq < b.seq;
}
}
class FifoPolicy {
before(a, b) {
return a.seq < b.seq;
}
}
class OldestDuePolicy {
before(a, b) {
if (a.runAt !== b.runAt) return a.runAt < b.runAt;
return a.seq < b.seq;
}
}
class Job {
constructor(spec, seq, now) {
this.id = spec.id;
this.priority = spec.priority ?? 5;
this.runAt = now + (spec.delay ?? 0);
this.task = spec.task;
this.retries = spec.retries ?? 0;
this.backoff = spec.backoff ?? 10;
this.seq = seq;
this.attempts = 0;
this.status = "PENDING";
this.result = null;
}
claim() {
if (this.status !== "PENDING") return false;
this.status = "RUNNING";
return true;
}
}
class Scheduler {
constructor({ clock, policy, workers }) {
if (!Number.isInteger(workers) || workers < 1) throw new Error("workers must be a positive integer");
this.clock = clock;
this.workers = workers;
this.jobs = new Map();
this.delayed = new Heap((a, b) => a.runAt < b.runAt || (a.runAt === b.runAt && a.seq < b.seq));
this.ready = new Heap((a, b) => policy.before(a, b));
this.seq = 0;
this.open = true;
}
submit(spec) {
if (!this.open) throw new Error("scheduler is shut down");
if (typeof spec.task !== "function") throw new Error("task must be a function");
const delay = spec.delay ?? 0;
if (!Number.isFinite(delay) || delay < 0) throw new Error("delay must be a non-negative number");
const retries = spec.retries ?? 0;
if (!Number.isInteger(retries) || retries < 0) throw new Error("retries must be a non-negative integer");
if (this.jobs.has(spec.id)) throw new Error("duplicate job id " + spec.id);
const job = new Job(spec, this.seq++, this.clock.now());
this.jobs.set(job.id, job);
this.delayed.push(job);
return job.id;
}
cancel(id) {
const job = this.jobs.get(id);
if (!job || job.status !== "PENDING") return false;
job.status = "CANCELLED";
return true;
}
statusOf(id) {
const job = this.jobs.get(id);
return job ? job.status : null;
}
promote() {
while (this.delayed.size > 0 && this.delayed.peek().runAt <= this.clock.now()) {
const job = this.delayed.pop();
if (job.status === "PENDING") this.ready.push(job);
}
}
nextJob() {
while (this.ready.size > 0) {
const job = this.ready.pop();
if (job.claim()) return job;
}
return null;
}
runOn(worker, job) {
job.attempts += 1;
try {
job.result = job.task(job);
job.status = "DONE";
} catch (error) {
if (job.attempts <= job.retries) {
job.status = "PENDING";
job.runAt = this.clock.now() + job.backoff * 2 ** (job.attempts - 1);
this.delayed.push(job);
} else {
job.status = "FAILED";
job.result = error instanceof Error ? error.message : String(error);
}
}
return { worker, id: job.id, status: job.status };
}
tick() {
this.promote();
const ran = [];
for (let worker = 0; worker < this.workers; worker++) {
const job = this.nextJob();
if (!job) break;
ran.push(this.runOn(worker, job));
}
return ran;
}
drain(step = 1, limit = 1000) {
const ran = [];
for (let i = 0; i < limit && this.delayed.size + this.ready.size > 0; i++) {
ran.push(...this.tick());
this.clock.advance(step);
}
return ran;
}
shutdown() {
this.open = false;
}
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Extend it
The change requests an interviewer throws next.
- How would you add recurring jobs that run every N seconds without letting a slow run overlap the next one?
- A worker thread dies halfway through a job. How does the scheduler notice, and what happens to that job?
- How would you stop low-priority jobs from starving when high-priority jobs keep arriving?
- How would the design change if jobs had to survive a process restart?
- How would you let one job wait until another job has finished successfully?
Where candidates slip
The mistakes this problem punishes.
- Checking the status and then setting RUNNING as two separate steps with the lock released in between. Two workers, or a worker and a cancel, both win.
- Waiting with a sleep loop instead of a timed wait on the next due job, which burns CPU or adds latency.
- Running the task while holding the scheduler lock, so one slow job blocks every submit.
- Comparing on priority alone. Equal priorities then come out in an unstable order and the demo prints something different on each run. Add a sequence number.
- Hard-coding the ordering inside the scheduler, so the follow-up "now order by deadline" means editing core code.
- Reading the system clock inside the scheduler, which makes delays and retries impossible to test.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.