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
A task failed, and the on-call engineer wants to know what it will hurt. Every task that runs after the failed one, directly or through other tasks, is affected.
Write reachable_tasks(edges, start). edges is a list of [before, after] pairs: the task after runs once the task before is done. start is the failed task. Return a sorted list of every task that is downstream of start.
Function to write
reachable_tasks(edges: list[list[str]], start: str) -> list[str]A sorted list of every task downstream of start, each listed once, never including start.
How to approach it
Build a map from each task to the tasks that come right after it. Then keep a queue of tasks to visit and a set of tasks already seen.
Sample cases
+ 3 held back until you submit
a small pipeline
From `clean`, the tasks after it are `load`, `audit` and `report`. `ingest` runs before it, so it is not included.
Input
Argument 1
[
[
'extract',
'clean'
],
[
'clean',
'load'
],
[
'clean',
'audit'
],
[
'load',
'report'
],
[
'ingest',
'extract'
]
]Argument 2
'clean'Returns
[
'audit',
'load',
'report'
]a diamond
Task `d` can be reached by two paths, but it must appear once.
Input
Argument 1
[
[
'a',
'b'
],
[
'a',
'c'
],
[
'b',
'd'
],
[
'c',
'd'
]
]Argument 2
'a'Returns
[
'b',
'c',
'd'
]a task with nothing after it
`b` is the last task, so the answer is an empty list.
Input
Argument 1
[
[
'a',
'b'
]
]Argument 2
'b'Returns
[] (empty list)
no edges at all
An empty graph has nothing to reach.
Input
Argument 1
[] (empty list)
Argument 2
'a'Returns
[] (empty list)
Constraints
start if you can get to it by following edges forward, one or more steps.start is never in its own answer, even when a loop leads back to it.start that is not in any edge, or has no tasks after it, gives an empty list.Worked example
Take the edges extract→clean, clean→load, clean→audit, load→report, and ingest→extract, with start = clean. Build a map from each task to its children: clean has load and audit; load has report. Put clean in a queue. Take it out: its children load and audit are new, so record them and queue them. Take out load: report is new. Take out audit and report: nothing new. The answer is ['audit', 'load', 'report'].
The trap: with the edges a→b, b→c, c→a, a search that does not remember which tasks it has seen goes around the loop forever.
What this tests
Breadth-first search on a graph, the idea behind problems such as 'Number of Islands' and 'Course Schedule'. The two habits that matter are a visited set and a queue. The set means a loop cannot trap you. The queue, instead of recursion, means a long chain cannot overflow the stack. Data engineers use this to find the impact of a failed task or a changed table.
reachable_tasks(edges: list[list[str]], start: 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.