Detect Dependency Graph Cycles | Dataford Interview Questions

Propio's Interpreter Platform represents service dependencies as a directed graph. If service A depends on service B, the graph contains an edge from A to B. A circular dependency can prevent services from starting correctly.

Implement has_cycle(dependencies) to determine whether the dependency graph contains at least one directed cycle.

Formal Specification

Input: dependencies, a dictionary mapping each service name to a list of services it directly depends on. Service names are strings.
Output: Return True if the directed graph contains a cycle, otherwise return False.
Services that appear only in dependency lists must still be considered graph nodes.

Constraints

1 <= number of distinct services <= 10^4
0 <= number of dependency edges <= 5 * 10^4
Service names are strings
Duplicate edges may appear
The graph may be disconnected

Function Signature

def has_cycle(dependencies):

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