Detect Cycles in Dependencies | Dataford Interview Questions

The Allianz customer portal consists of services that depend on other services. A directed edge A -> B means service A requires service B. Implement a function that determines whether the dependency graph contains a circular dependency.

A cycle exists if, starting from any service, following dependency edges can eventually return to that service. The graph may contain disconnected components and services with no dependencies.

Formal Specification

Implement detect_cycle(graph), where graph is a dictionary mapping each service name to a list of services it directly depends on. Every dependency name appears as a key in graph, even if its list is empty. Return True if the directed graph contains at least one cycle, otherwise return False.

Constraints

1 <= number of services <= 10^4
0 <= number of dependency edges <= 5 * 10^4
Service names are non-empty strings
Every dependency appears as a key in graph
The graph may contain disconnected components

Function Signature

def detect_cycle(graph):

Your question is Detect Cycles in Dependencies. 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