Deadlock Detection in Agent Graphs | Dataford Interview Questions

Given a directed graph of agent dependencies, write an algorithm to detect potential deadlocks in a multi-agent system.

Treat each edge A -> B as agent A waiting for or depending on agent B. Implement detect_deadlocks(graph), where graph is a dictionary mapping each agent ID to a list of dependent agent IDs. Return a sorted list of every agent that belongs to a directed cycle, including self-loops. Agents that merely lead into a cycle are not deadlocked. Assume every referenced agent appears as a graph key.

Constraints

0 <= number of agents <= 2,000
Each agent ID is a unique non-empty string
Every referenced dependency appears as a key in graph
The total number of dependency edges is at most 20,000
Return every agent in a directed cycle exactly once

Function Signature

def detect_deadlocks(graph):

Your question is Deadlock Detection in Agent Graphs. 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

Given a directed graph of agent dependencies, write an algorithm to detect potential deadlocks in a multi-agent system.

Constraints

0 <= number of agents <= 2,000
Each agent ID is a unique non-empty string
Every referenced dependency appears as a key in graph
The total number of dependency edges is at most 20,000
Return every agent in a directed cycle exactly once

Function Signature

def detect_deadlocks(graph):

Your question is Deadlock Detection in Agent Graphs. 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.