Cycle Detection in Dependencies | Dataford Interview Questions

Write a program to detect cycles in a directed graph, representing dependencies in a vehicle state machine.

Implement has_cycle(graph), where graph is a dictionary mapping each state to a list of states it can transition to. Return True if any directed cycle exists, otherwise return False. The graph may contain disconnected components, and every referenced state is present as a key.

Constraints

0 <= number of states <= 1000
Each state name is unique and hashable
Every referenced neighbor appears as a key in graph
The graph may contain disconnected components

Function Signature

def has_cycle(graph):

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

Write a program to detect cycles in a directed graph, representing dependencies in a vehicle state machine.

Constraints

0 <= number of states <= 1000
Each state name is unique and hashable
Every referenced neighbor appears as a key in graph
The graph may contain disconnected components

Function Signature

def has_cycle(graph):

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