Cycle Detection in Directed Graphs | Dataford Interview Questions

Your question is Cycle Detection in Directed Graphs. Start with the requirements on the right.

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

Problem

Juspay Hyper can model payment-processing steps as directed dependencies, where an edge from step A to step B means A must complete before B starts. Given this dependency graph, determine whether it contains a directed cycle.

Implement has_cycle(graph). Return True if any directed cycle exists, otherwise return False.

Formal Specification

Input: graph, a dictionary mapping each node name, represented by a string, to a list of neighboring node names.
Output: A boolean. Return True when the graph contains at least one directed cycle; otherwise return False.
Every node referenced as a neighbor is guaranteed to appear as a key, possibly with an empty neighbor list.
The graph may be disconnected and may contain self-loops.

Constraints

1 <= number of nodes <= 10^5
0 <= number of edges <= 2 * 10^5
Node names are non-empty strings
Every referenced neighbor appears as a graph key
Duplicate edges may be present

Function Signature

def has_cycle(graph):