PreviousNext
Coding/Concurrency

Deadlock detection

Write codeMedium25 minMicrosoft style

Your task

A system has n threads 0..n-1. A wait-for graph is given as a list of edges [a, b] meaning thread a is blocked waiting on a resource held by thread b. A deadlock exists if and only if the wait-for graph contains a directed cycle. Return True if there is a deadlock, otherwise False.

Examples

has_deadlock(n: int, wait_for: list[list]) -> bool
Example 1
Inputhas_deadlock(3, [[0, 1], [1, 2], [2, 0]])
OutputTrue