Coding Interview: How do you implement a cancellable priority task scheduler?

Prompt and scope

Implement a single-node Scheduler with schedule(taskId, runAt, priority, fn), cancel(taskId), and next(). Select the earliest runAt, then the highest priority, then submission sequence. Only one version of a taskId is valid. A cancelled task must not start; when nothing is due, next() returns a wait hint or an empty result. Explain lazy deletion, worker concurrency, clock choice, and shutdown races.

Public interview material presents task scheduling as a combined problem involving priority queues, worker pools, cancellation, and failure handling. It tests lifecycle and concurrency contracts in addition to the heap data structure itself.

What the interviewer is testing

• A state machine for pending, running, cancelled, and completed without illegal transitions.
• A deterministic key (runAt, -priority, sequence) that never compares task objects.
• Version checks or lazy deletion so replacement and cancellation cannot leak stale work.
• A precise distinction between cancelling queued work and stopping a running function.
• A proof that worker limits, shutdown order, and clock selection preserve the contract.

Clarifications to ask first

• Is runAt a monotonic relative deadline or wall-clock time? Assume a monotonic clock for waits.
• Does fn receive cancellation? Assume an AbortSignal, with cooperative stopping only.
• Does a duplicate taskId replace or fail? This version replaces the old version.
• Does cancel stop a running function immediately? No; it prevents a not-yet-started run and signals a running one.
• Does close wait for running work? Assume it rejects new work and waits for workers to finish.

30-second answer

I would keep (runAt, -priority, sequence, taskId, version) in a min-heap and store the current version for each task ID in a map. Scheduling or cancelling updates the map and invalidates old heap entries; next() repeatedly validates version and state before moving a due task to running. A dispatcher uses a monotonic clock to wait for the heap head, then hands work to a fixed-size worker pool. Queued cancellation is a strong guarantee; cancellation of running code is cooperative. Shutdown rejects new submissions, wakes the dispatcher, and waits for cleanup.

Step-by-step deep dive

Step 1: Define the key and invariants

Use (runAt, -priority, sequence) as the heap key. A monotonic sequence makes equal timestamps and priorities deterministic. current[taskId] stores only the newest version. Stale versions may remain in the heap temporarily, but they can never transition from pending to running.

Step 2: Define replacement in schedule

Each schedule creates a new version, stores it in the map, and pushes a new heap entry. There is no linear search through the array. When an entry is popped, its version is compared with the map. Insertion is O(log n) and duplicate IDs cannot produce two valid executions.

schedule(id, runAt, priority, fn):
    version = nextVersion(id)
    current[id] = {version, state: pending, fn, runAt, priority}
    heappush(heap, (runAt, -priority, nextSequence(), id, version))

Step 3: Implement cancel and head cleanup

Cancellation marks the current pending task as cancelled and wakes a waiter. When next() pops the head, it checks that the map still points to the same version and that the state is pending. Stale, cancelled, and superseded entries are discarded. Lazy deletion avoids an O(n) scan, but stale-entry ratios must be monitored and periodically rebuilt.

Step 4: Gate due work with a worker limit

The dispatcher must not hand future work to workers. It computes the delay to the heap head with a monotonic clock. Once due, it atomically changes pending to running and puts the task on a fixed-size worker queue. The worker count or a semaphore enforces the concurrency bound.

Step 5: Separate cancellation from function termination

If a queued task is cancelled before the state transition, fn is never called. A running task can only receive an AbortSignal; the function must check it or pass it to cancellable I/O. Record cancelRequested, and do not report completion until the function has actually returned.

Step 6: Order close against races

close first enters closing and rejects new schedules, then cancels timers and wakes the dispatcher. The dispatcher stops claiming new tasks while workers finish already-claimed work; only then does the scheduler become closed. If queued work should be discarded immediately, mark the map entries cancelled instead of merely clearing the heap.

Step 7: Prove complexity and space bounds

Normal schedule is O(log n), cancel is an O(1) state update, and next performs O(log n) heap work. Each stale entry is popped at most once, so cleanup is amortized over the update or cancellation that created it. Rebuild from current map entries when heap size exceeds a fixed multiple of live tasks.

Step 8: Test the important interleavings

Test stable ordering for equal keys, replacement before the old entry reaches the head, cancellation immediately before and after claiming, an earlier task interrupting a wait, the worker limit, function failure, submission during close, and monotonic-clock jumps. Differential-test next() against a sorted reference model and record peak active workers.

High-quality sample answer

I would separate state from the heap: a map stores the newest version for each taskId, while a min-heap stores (runAt, -priority, sequence, taskId, version). Replacement writes a new version and cancellation marks state; neither mutates the heap array. The dispatcher claims only due tasks and puts them into a fixed-size worker queue. Version validation prevents cancelled and stale entries from running, while AbortSignal gives running functions cooperative cancellation. Shutdown rejects new work, stops claiming, wakes waiters, and waits for claimed work to finish. Metrics track live entries versus heap size so lazy deletion cannot grow without bound.

Common mistakes

• Sorting only by priority and ignoring that runAt is still in the future.
• Mutating a heap entry in place and breaking the heap invariant.
• Deleting only from the map, then executing an old heap entry.
• Treating a successful cancel() call as proof that running code has stopped.
• Using wall-clock time for waits and suffering from clock corrections.
• Clearing the queue on close while leaving timers, dispatchers, or workers alive.
• Starting unbounded workers and turning the scheduler into an unbounded launcher.

Follow-up questions and answers

How do you prevent starvation of low-priority work?

State that strict priority is the default and can starve low-priority tasks. If fairness is required, increase effective priority with waiting time or use weighted quotas. Both choices change the ordering key and the latency proof, so add metrics and tests.

How do you prevent overlapping runs for a recurring task?

Add a running lock or generation to the task state. If the next trigger arrives while it is running, explicitly choose skip, coalesce one pending run, or enqueue a new version. Never submit unconditionally when overlap is forbidden.

How would you recover after a process crash?

An in-memory heap only covers process lifetime. Persist version, state, and next-run time, rebuild the heap at startup, and claim with a conditional update or lease. Recovery normally provides at-least-once execution, so task functions must be idempotent.

How would you extend it to multiple nodes?

Replace the local heap with a persistent time-indexed queue and use leases or conditional writes for ownership. Let an expired lease become retryable after node failure. Carry versions through cancellation and replacement so consumers reject stale work, and use storage time or an explicit tolerance window across nodes.