Loadingone moment…
Sign in to run and submit your work
Reading is open to everyone. Running code and saving drafts need an account so your work is yours and comes back on your next visit.
or
CODE WORKSPACE
Someone added a new dependency, and now the scheduler reports that some tasks never start. A task can start only when every task it depends on is finished. If two tasks wait for each other, or if a longer ring of tasks does, none of them can ever start.
Write blocked_tasks(edges). edges is a list of [before, after] pairs: after can start only when before is done. Return a sorted list of every task that can never start.
Function to write
blocked_tasks(edges: list[list[str]]) -> list[str]A sorted list of the tasks that can never start, because they are in a loop or behind one.
How to approach it
Count how many unfinished tasks each task is waiting on. Run every task that waits on nothing, and lower the count of its children. Whatever never reaches zero is stuck.
Sample cases
+ 3 held back until you submit
a healthy pipeline
There is no loop, so every task can run and nothing is blocked.
Input
Argument 1
[
[
'a',
'b'
],
[
'b',
'c'
],
[
'a',
'c'
]
]Returns
[] (empty list)
a loop of three with a tail
`a`, `b` and `c` wait for each other. `after_loop` and `report` wait for them, so they are blocked too. `start` runs fine.
Input
Argument 1
[
[
'start',
'a'
],
[
'a',
'b'
],
[
'b',
'c'
],
[
'c',
'a'
],
[
'c',
'after_loop'
],
[
'after_loop',
'report'
]
]Returns
[
'a',
'after_loop',
'b',
'c',
'report'
]two tasks waiting on each other
The smallest loop: each task waits for the other.
Input
Argument 1
[
[
'x',
'y'
],
[
'y',
'x'
]
]Returns
[
'x',
'y'
]no edges
No tasks and no edges means nothing is blocked.
Input
Argument 1
[] (empty list)
Returns
[] (empty list)
Constraints
Worked example
Take the edges start→a, a→b, b→c, c→a, c→after_loop, after_loop→report. Count how many tasks each task is waiting on: start 0, a 2 (start and c), b 1, c 1, after_loop 1, report 1. Only start is waiting on nothing, so it runs. That frees a by one, but a is still waiting on c. The queue is now empty. Everything still waiting is stuck: a, after_loop, b, c, report. That is the answer, sorted.
The trap: checking only for two tasks that wait for each other finds nothing in this graph, because the loop is a→b→c→a. It would also miss after_loop and report, which are stuck behind the loop.
What this tests
Cycle detection with Kahn's algorithm, which is the same method behind 'Course Schedule' (can all courses be finished?). Run the topological sort, and the tasks that never become ready are the ones in or behind a loop. Data engineers meet this when a scheduler rejects a DAG, or when a table depends on itself through a chain of views.
blocked_tasks(edges: list[list[str]]) -> list[str]Submit for review to find out what your query gets right, what it gets wrong, and how it compares with the best working query for this exercise.
This scenario runs a full workspace — editor, canvas and results side by side. It needs a laptop or desktop to be usable. Open this page on a bigger screen to start building.