Coding Interview: How Would You Build a Dependency-Aware Task Scheduler?

Prompt and scope

Implement an in-memory TaskScheduler. A caller submits a task ID, dependency IDs, and a function. The scheduler may claim a task only after every dependency has succeeded. Expose operations such as submit, ready, complete, fail, and cancel, and report dependency cycles that can never run. Explain duplicate submissions, failure propagation, concurrency limits, shutdown, and restart boundaries.

This problem combines graph traversal with a live state machine. A strong answer clarifies state and failure semantics before choosing data structures, then maintains indegrees, reverse edges, and a ready queue. Python's TopologicalSorter treats nodes with no unfinished predecessors as processable and exposes detected cycles as diagnostic data. Those semantics help define the contract, but a static sort alone is insufficient because tasks complete, fail, and cancel over time.

What the interviewer is testing

• Distinguishing pending, ready, running, succeeded, failed, blocked, and cancelled.
• Maintaining indegree and reverse-adjacency invariants instead of rescanning every task.
• Releasing only affected dependents when a dependency completes.
• Defining cycle, failure, and cancellation propagation before choosing APIs.
• Limiting workers, guaranteeing one claim per task version, and handling duplicate submissions.
• Giving complexity bounds and tests for adversarial interleavings.

Clarifying questions

• Is the graph static or can tasks be added dynamically? Assume all referenced tasks are submitted before scheduling starts; only a new version may be submitted while running.
• What happens to descendants after a dependency fails? This answer marks them blocked; retry requires an explicit new generation.
• Does cancellation cascade to every descendant? Assume it cancels only that task; descendants become blocked when a required dependency is cancelled.
• Are failures retried automatically? No. The caller submits a new generation and owns idempotency for side effects.
• Does ready() return one task or a batch? Return at most maxConcurrency - running tasks in deterministic order.

Thirty-second answer

Store each task's state, unfinished-dependency count, and reverse adjacency list. Before scheduling, run Kahn's algorithm or a three-color DFS and return a cycle path when one exists. Put zero-indegree tasks in a stable ready queue. Under one lock, claim tasks by changing ready to running; on success, decrement the count of each dependent and enqueue those that reach zero. Failure and cancellation mark affected descendants blocked. Every callback carries a generation so stale workers cannot release dependents twice. A fixed worker pool or semaphore enforces concurrency.

Step-by-step solution

Step 1: Define states and boundaries

States move forward: pending to ready, then running, and finally succeeded or failed. Cancellation may happen while pending or ready; cancellation of a running function is cooperative. blocked means the function did not run because a required dependency can no longer succeed. Terminal states never return to ready, preventing duplicate execution.

Store a generation per task ID. A duplicate submission can be rejected or create a new generation; this answer chooses replacement only while the old version is not running. A running version cannot be silently overwritten; return a conflict or wait for its terminal callback.

Step 2: Build indegrees and reverse edges

The task table stores remainingDeps; a reverse map stores dependents[dependencyId]. Register each edge once. Zero-indegree tasks enter the ready queue during initialization, and later changes update only affected counts.

Task:
  id, generation, dependencies, dependents
  remainingDeps, state, fn, error

submit(task):
  validateUniqueDependencies(task)
  registerEdges(task)
  if task.remainingDeps == 0:
      task.state = READY
      readyQueue.push(task.id)

An unknown dependency must not be treated as already complete. Keep it in a waiting state until submitted, or reject it with an UnknownDependency error if the contract requires a closed graph.

Step 3: Report cycles before execution

For a static graph, Kahn's algorithm copies indegrees, processes zero-indegree nodes, and removes their outgoing edges. If fewer than all nodes are processed, the remainder contains a cycle. Return a concrete path such as A → B → C → A, not only a boolean.

Alternatively, a white-gray-black DFS finds a gray-to-gray edge and reconstructs the cycle through parent pointers. Run detection before any task becomes running. Disallow adding edges after execution starts unless the contract creates a new graph version.

Step 4: Claim tasks and enforce concurrency

ready() computes available slots, removes tasks in stable submission order, and changes each state to running in the same critical section. Once returned, another caller cannot claim the task. complete(id, generation) validates both generation and state; a late callback from an old worker returns a conflict and cannot release dependents.

Use a fixed worker count or semaphore for the concurrency limit. Queue length is not active-task count: only running tasks consume slots. If a requested batch exceeds available slots, return the available number or CapacityExceeded instead of silently raising concurrency.

Step 5: Propagate success, failure, and cancellation

On success, traverse direct dependents. Decrement remainingDeps only for still-pending versions; enqueue a node when the count reaches zero. On failure, this contract marks direct and transitive descendants blocked and records the first blocking cause. An alternative-dependency policy is valid only if stated explicitly.

Cancellation affects versions that have not started. A running function may receive an AbortSignal, but only the function can confirm cooperative exit. Descendants become blocked when a required dependency is failed or cancelled; they never pretend that dependency succeeded.

Step 6: Make submissions and callbacks idempotent

Use (taskId, generation) as the idempotency key. Repeated complete, fail, or cancel calls return the known terminal state and do not decrement dependents twice. When replacing a pending version, remove its old reverse edges before registering new ones; overwriting the object alone leaves stale edges and can make a dependent wait forever.

If updates are unnecessary, rejecting duplicate IDs is simpler. State the tradeoff: a static builder can reject duplicates, while a long-lived workflow usually needs generations, audit records, and explicit retry versions.

Step 7: Shutdown, retry, and recovery

close() rejects new submissions, stops ready() from claiming more work, and waits for running callbacks or a defined timeout. Queued tasks are cancelled or retained according to the contract; clearing memory without recording a reason loses information. A retry creates a new generation and rechecks the dependency snapshot instead of changing failed back to ready.

An in-memory scheduler cannot recover after a process crash. Persistence requires tasks, versions, states, dependencies, and leases. Recovery workers claim tasks with conditional writes, and task functions must be idempotent. Recovery can provide at-least-once execution, not exactly-once side effects.

Step 8: Complexity and tests

Graph initialization is O(V + E). Each completion scans only outgoing edges, so a whole propagation pass remains O(V + E); a heap-based ready queue claims in O(log V). Space is O(V + E).

Test an empty graph, independent branches, a long chain, cycles, unknown dependencies, two dependencies completing together, failure propagation, descendant cancellation, duplicate callbacks, duplicate submissions, zero capacity, shutdown races, and late callbacks from old generations. A small state model can compare each ready set and assert at most one pending → running transition per version.

Model answer

I would freeze the graph first, then store state, generation, remaining dependency count, and reverse adjacency for each task. Kahn's algorithm plus parent pointers reports a concrete cycle. Tasks with no dependencies enter a stable ready queue. ready() claims up to the remaining concurrency slots under one lock and immediately marks tasks running. A completion callback must match the generation and may transition only once; success decrements downstream counts and enqueues nodes that reach zero. Failure and cancellation produce blocked descendants rather than fake success. Duplicate callbacks are idempotent, retries create a new generation, and shutdown rejects new work before draining running callbacks. The pass is O(V + E) and tests cover concurrency and side-effect boundaries.

Common mistakes

• Performing one topological sort without defining live completion and failure transitions.
• Scanning every node for readiness after each completion instead of using reverse edges.
• Returning only a cycle boolean, with no diagnostic path.
• Omitting a generation from completion callbacks, allowing stale workers to release dependents.
• Treating dependency failure as success and running downstream work without prerequisites.
• Claiming that cancelling a running function is forceful without a cooperative signal contract.
• Increasing worker count to hide backlog and exhausting downstream capacity.
• Reusing failed state for retries without idempotency, side-effect, or lease semantics.

Follow-up questions

How would you handle a graph too large for memory?

Store task metadata and edges durably, and load only an active window by tenant or partition. Keep a cursor in memory. Claims use conditional writes or short leases, and completion still checks the generation. Explain cross-partition dependencies, pagination consistency, and duplicate execution after lease expiry.

How can a failed branch continue while dependent nodes stop?

Label edges as required or optional. A task becomes ready only after all required dependencies succeed and optional dependencies reach a terminal state. Record optional failures in the input summary and metrics rather than silently dropping them; this expands the state machine and tests.

How would you add dependencies dynamically?

Allow new edges only while a task is pending, incrementing indegree in the same critical section. Reject changes to ready or running tasks. If running changes are required, create a new generation and execute it against the new graph after the old version reaches a terminal state.

How do you cancel a shared dependency without harming unrelated branches?

Change only that dependency's terminal state, then inspect required-edge relationships along reverse edges. Branches without the dependency continue; every downstream task that requires it becomes blocked. Audit who cancelled it, when, and along which propagation path.

How do multiple worker processes avoid double execution?

Claim with an atomic database update or lease and include the generation in the condition. A lease may expire and permit another claim, so the function must be idempotent or compensatable. An in-memory lock protects one process only.

Which observability signals matter?

Track cycle count, blocked count, ready wait time, run duration, claim conflicts, lease expiry, duplicate callbacks, and propagation latency per edge. Segment by task type and tenant so averages do not hide tail backlog, and distinguish graph configuration errors from function failures.

How would you prove a task is not claimed twice?

Put state checking, slot decrement, and the running write in one critical section or atomic conditional update, and include the generation in callbacks. A model test can interleave two ready() calls and assert at most one pending → running transition per version; duplicate completion returns the known terminal state.