Detect Cycles in Workflow Graph | Dataford Interview Questions

Implement an efficient algorithm to detect cycles in a directed graph representing workflow dependencies for Qventus. Represent the graph as a dictionary mapping each workflow step to a list of dependent steps, and return True if any directed cycle exists, otherwise return False. Implement has_cycle(graph), where nodes may appear only in dependency lists and the graph may contain disconnected components.

Constraints

0 <= number of distinct nodes <= 10^4
Each adjacency list contains valid hashable node identifiers
A node may appear as a dependency without being a key in the graph
The graph may contain disconnected components
The graph is directed and duplicate edges do not affect the result

Function Signature

def has_cycle(graph):

Your question is Detect Cycles in Workflow 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

Constraints

0 <= number of distinct nodes <= 10^4
Each adjacency list contains valid hashable node identifiers
A node may appear as a dependency without being a key in the graph
The graph may contain disconnected components
The graph is directed and duplicate edges do not affect the result

Function Signature

def has_cycle(graph):

Your question is Detect Cycles in Workflow 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.