Detect Cycles in Pipeline Graph | Dataford Interview Questions

Roku data pipelines can depend on one another, and a circular dependency prevents the pipeline schedule from completing. Given a directed dependency graph, determine whether it contains at least one cycle.

Use depth-first search with three states for each node: unvisited, currently visiting, and fully processed.

Formal Specification

Implement detect_cycle(graph), where graph is a dictionary mapping each pipeline name to a list of pipeline names that must run after it. A referenced pipeline may appear only in an adjacency list and does not need its own dictionary entry. Return True if the directed graph contains a cycle; otherwise, return False.

Constraints

0 <= number of declared nodes <= 10^5
0 <= number of edges <= 2 * 10^5
Node names are non-empty strings
The graph may be disconnected
A referenced node may be absent as a dictionary key

Function Signature

def detect_cycle(graph):

Your question is Detect Cycles in Pipeline Graph. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem