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
The scheduler reads a dependency map — each task listing what must finish before it starts — and runs the tasks in order. When somebody adds a dependency that closes a loop, the scheduler currently hangs; when somebody misspells one, it runs the task anyway, before the thing it needed.
Write order_tasks(tasks). Return a valid run order and everything that cannot be run.
Function to write
order_tasks(tasks: dict) -> dictA dict with order — a valid alphabetical-tie-broken run order — plus blocked and unknown_dependencies.
How to approach it
Repeatedly take every task with no remaining dependencies; stop when none are left ready.
Sample cases
+ 2 held back until you submit
a real dag with two problems
A diamond that must order correctly, a two-task cycle, and a task needing an audit step nobody defined.
Input
Argument 1
{
'publish': [
'transform'
],
'transform': [
'extract',
'load_dim'
],
'extract': [],
'load_dim': [
'extract'
],
'notify': [
'publish',
'audit'
],
'cycle_a': [
'cycle_b'
],
'cycle_b': [
'cycle_a'
]
}Returns
{
'order': [
'extract',
'load_dim',
'transform',
'publish'
],
'blocked': [
'cycle_a',
'cycle_b',
'notify'
],
'unknown_dependencies': {
'notify': [
'audit'
]
}
}no tasks
An empty dag produces an empty order rather than raising on the first lookup.
Input
Argument 1
{}Returns
{
'order': [],
'blocked': [],
'unknown_dependencies': {}
}tasks with no dependencies
Everything is ready at once, so the alphabetical tie-break decides the order.
Input
Argument 1
{
'c': [],
'a': [],
'b': []
}Returns
{
'order': [
'a',
'b',
'c'
],
'blocked': [],
'unknown_dependencies': {}
}Constraints
blocked, and record what it was missing under unknown_dependencies.blocked, sorted, and the function must terminate rather than looping.order, blocked and unknown_dependencies. An empty map produces empty results, not an error.Worked example
transform needs both extract and load_dim, and load_dim needs extract too. That diamond has exactly one correct shape: extract, then load_dim, then transform, then publish. Running transform as soon as extract finishes — which is what a scheduler that only looks one level down does — starts it before the dimension is loaded, and the join silently produces no rows.
cycle_a and cycle_b need each other, so neither is ever ready. A loop that waits for progress never terminates; a loop that stops when nothing is ready leaves exactly the cycle behind, which is both the termination condition and the diagnosis. notify is a third case: it names audit, and there is no such task. It is blocked, and so is nothing else, because nothing depends on it.
What this tests
Kahn's algorithm, and the two failure modes a dependency graph really has. The insight worth having is that the leftovers when no task is ready are the cycle — you get the detection for free by writing the loop honestly.
order_tasks(tasks: dict) -> dictSubmit 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.