Detect Circular Dependency | Dataford Interview Questions

EPAM DIAL may represent workflow steps as a directed dependency graph, where an edge A -> B means step A must complete before step B. Implement a function that determines whether the graph contains a circular dependency.

A circular dependency exists when following directed edges can return to a node already on the current traversal path. A self-dependency such as A -> A is also a cycle.

Formal Specification

Given graph, a dictionary mapping each node to a list of nodes that depend on it, return True if the directed graph contains a cycle. Return False otherwise. Nodes that appear only in dependency lists must also be considered part of the graph.

Constraints

0 <= number of distinct nodes <= 10^5
0 <= number of directed edges <= 2 * 10^5
Node identifiers are hashable values
The graph may be disconnected
Duplicate edges may be present

Function Signature

def has_circular_dependency(graph):

Your question is Detect Circular Dependency. 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