Detect Dependency Graph Cycles

MediumPython00:00

Practice interviewer

In session

5 left

00:00

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

You need to log in / sign up to run or submit.

Problem

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 solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output