Cycle Detection in Dependency Graph | Dataford Interview Questions

Applied Intuition simulation components are represented as a directed dependency graph. An edge A -> B means component A depends on component B. Implement an efficient algorithm that determines whether the graph contains a directed cycle, which would prevent dependencies from being resolved safely.

Formal Specification

Implement has_cycle(graph), where graph is a dictionary mapping each component name to a list of components it depends on. A component may appear only in a dependency list and need not have its own dictionary entry. Return True if any directed cycle exists, otherwise return False.

The graph may contain multiple disconnected components. Do not modify the input graph.

Constraints

0 <= number of distinct components <= 100,000
0 <= number of dependency edges <= 200,000
Component names are non-empty strings
Self-dependencies count as cycles
The graph may be disconnected and may contain duplicate edges

Function Signature

def has_cycle(graph):

Your question is Cycle Detection in Dependency 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