Task Scheduler with Dependencies
A CI pipeline runner: priorities, dependencies that may arrive later, and cycle detection.
the brief
What you are building
Every git push starts a pipeline: compile, then unit tests and lint, then deploy, then notify the team.
Some jobs need others to finish first. Some are more urgent. Jobs can be added while the pipeline is already running — even before the jobs they depend on exist.
You will build the scheduler that always picks the right next job, and can warn when some jobs can never run.
must have
Requirements
addTask(id, priority, dependsOn)adds a task. It returnsfalse(and changes nothing) if this id was ever added before, even if it already ran.dependsOnmay name tasks that are not added yet. A name repeated independsOncounts once. A dependency that already ran does not block.- A task is ready when it has not run yet and every task it depends on has run.
runNext()picks the ready task with the highest priority (equal priorities: the id that comes first alphabetically), marks it as run, and returns its id. If nothing is ready, it returns"".canFinishAll()returnstrueif every task added so far (and not run yet) could still run one day, by running ready tasks again and again. It returnsfalseif some are stuck: in a cycle, depending on themselves, or waiting for a task that was never added. It changes nothing.
the contract
The Java API: class TaskScheduler
public TaskScheduler()- No tasks.
public boolean addTask(String id, int priority, String[] dependsOn)falseifidwas added before.public String runNext()- Runs the best ready task; returns its id, or
"". public boolean canFinishAll()- Could every unfinished task still run? Read-only.
- up to 2,000 tasks and 10,000 calls in total
- 0 ≤ dependsOn.length ≤ 10
- priorities may be negative
- ids are non-empty strings like
unit-tests
example session
Calls in, answers out
A small build pipeline. notify is added before approval exists.
| call | returns | why |
|---|---|---|
new TaskScheduler() | — | |
addTask("compile", 5, new String[] {}) | true | |
addTask("unit-tests", 3, new String[] {"compile"}) | true | |
addTask("lint", 3, new String[] {}) | true | |
addTask("deploy", 9, new String[] {"unit-tests", "lint"}) | true | |
addTask("lint", 1, new String[] {}) | false | lint was already added |
runNext() | "compile" | deploy is most urgent but not ready; compile (5) beats lint (3) |
runNext() | "lint" | lint and unit-tests tie at 3; "lint" comes first |
canFinishAll() | true | |
runNext() | "unit-tests" | |
addTask("notify", 1, new String[] {"deploy", "approval"}) | true | approval does not exist yet — allowed |
canFinishAll() | false | notify waits for a task that was never added |
runNext() | "deploy" | |
runNext() | "" | notify still waits for approval |
addTask("approval", 2, new String[] {}) | true | |
canFinishAll() | true | |
runNext() | "approval" | |
runNext() | "notify" | |
runNext() | "" | all done |
time plan
Your 120 minutes
- 15 minclarify — Can a dependency arrive later? Can an id be re-added after it ran? Tie rule? What exactly makes
canFinishAllfalse? - 15 mindesign — It is a graph: an edge from each dependency to the task waiting on it. Count unfinished dependencies per task; ready tasks go in a priority queue.
- 45 mincore code —
addTaskandrunNextwith the counts and the heap. Run the example up todeploy. ThencanFinishAllwith Kahn's algorithm on a copy. - 30 minedge cases — A two-task cycle, a self-dependency, repeated dependencies, a dependency that already ran, a chain of 2,000 tasks added last-first.
- 15 minpolish — Be ready to run tasks on several workers in parallel, and to explain O(V + E).
Practise under real pressure: a 120-minute clock with the phases above. It keeps running if you reload the page.
your turn
Build it here
Write the whole class in the editor. Run replays the example session; Submit adds the hidden tests (edge cases and large random sessions). Stuck for 20 minutes? Open one hint at a time.
Build TaskScheduler in the browser
Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
The reference, the data-structure reasoning and the rubric are hidden so you can build it first. Even a half-working attempt teaches you more than reading a perfect answer.
Opening all three hints also shows it.
reference
One clean way to build it
In-degree counts, a waiters map, a heap of ready tasks, and Kahn's algorithm on a copy for canFinishAll.
class TaskScheduler { static class Task { final String id; final int priority; int waitingOn; // dependencies not done yet. 0 = ready Task(String id, int priority) { this.id = id; this.priority = priority; } } /** Higher priority first; equal priorities by id, alphabetically. */ private static final Comparator<Task> FIRST = Comparator.comparingInt((Task t) -> -t.priority).thenComparing(t -> t.id); private final Map<String, Task> tasks = new HashMap<>(); private final Map<String, List<String>> dependents = new HashMap<>(); // dep → tasks waiting for it private final Set<String> done = new HashSet<>(); private final PriorityQueue<Task> ready = new PriorityQueue<>(FIRST); public boolean addTask(String id, int priority, String[] dependsOn) { if (tasks.containsKey(id)) return false; Task task = new Task(id, priority); tasks.put(id, task); for (String dep : new LinkedHashSet<>(Arrays.asList(dependsOn))) { // a repeated dependency counts once if (done.contains(dep)) continue; // already finished: nothing to wait for task.waitingOn++; dependents.computeIfAbsent(dep, k -> new ArrayList<>()).add(id); // dep may not exist yet: fine } if (task.waitingOn == 0) ready.add(task); return true; } public String runNext() { Task task = ready.poll(); // the best ready task: O(log n) if (task == null) return ""; done.add(task.id); for (String waiting : dependents.getOrDefault(task.id, List.of())) { Task t = tasks.get(waiting); if (--t.waitingOn == 0) ready.add(t); // its last dependency just finished } dependents.remove(task.id); return task.id; } /** Kahn's algorithm on a copy of the counts: can every unfinished task still run? O(V + E). */ public boolean canFinishAll() { Map<String, Integer> left = new HashMap<>(); ArrayDeque<String> queue = new ArrayDeque<>(); for (Task t : tasks.values()) { if (done.contains(t.id)) continue; left.put(t.id, t.waitingOn); if (t.waitingOn == 0) queue.add(t.id); } int canRun = 0; while (!queue.isEmpty()) { String id = queue.poll(); canRun++; for (String w : dependents.getOrDefault(id, List.of())) { if (left.merge(w, -1, Integer::sum) == 0) queue.add(w); } } return canRun == left.size(); // a cycle or a missing task leaves someone waiting forever }}the choices
Which data structures, and why
HashMap<String, List<String>> (dependency → waiters)The graph's edges, pointing from a dependency to the tasks that wait on it. Works even before the dependency is added.
O(E) memory; each edge is followed once when its dependency runs.
The in-degree. "Ready" is just "count == 0" — no need to re-check every dependency.
O(1) per decrement.
PriorityQueue<Task>Only ready tasks, best first (priority, then id).
O(log n) per runNext and per task that becomes ready. Scanning all tasks would be O(n) per call.
Decides whether everything can finish without changing the real state. Stuck tasks never reach count 0.
O(V + E) per canFinishAll.
self-check
Mark yourself like the interviewer would
Tick only what your code really does. Nothing is saved or sent — this is just for you.
your honest self-score: 0 / 100
traps
Common mistakes
- Scanning every task on every
runNextto see if its dependencies are done. It works, but it is O(V × deps) per call. - Counting a repeated dependency twice, so the task waits for a decrement that never comes.
- Running Kahn's algorithm on the real counts inside
canFinishAll, which changes the state. - Detecting cycles with recursive DFS on a 2,000-task chain — deep recursion can overflow the stack (and the in-browser JVM has a smaller one).
- Forgetting that a dependency that already ran must not block a newly added task.
what they ask next
Follow-ups and extensions
Run on 4 workers in parallel. Each task takes some minutes. When does everything finish?
Simulate time with two heaps: ready tasks (by priority) and running tasks (by finish time). While a worker is free and a task is ready, start it. Otherwise jump to the next finish time, free that worker, and release its waiters.
Which tasks are stuck, not just whether any are?
After Kahn's pass on the copy, every unfinished task whose count did not reach 0 is stuck. Return those ids.
Retry a failed task up to 3 times.
On failure, keep it out of the done set, increase its attempt count, and push it back into the ready heap if attempts < 3. Its waiters stay blocked until it succeeds.
How is this related to LeetCode 207 (Course Schedule)?
207 asks only "can everything finish?" — that is canFinishAll, Kahn's algorithm. This spec adds priorities, live updates and forward references.
revise