Detect a Deadlock from Thread Lock Acquire and Release Logs
Company: Helmai
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given the event log of a multithreaded program, in the order the events happened. Each event records a thread requesting or releasing a lock. Write a function that decides whether the program ends in a deadlock: a group of threads in which each thread is waiting for a lock held by the next thread in the group, so that none of them can ever continue.
The report gives only the task, deciding from a set of logs whether there is a deadlock. The event format and lock semantics below are fixed here so that the answer is well defined.
### Function Signature
```python
def has_deadlock(logs: list[list[str]]) -> bool:
```
### Rules
- `logs[i] = [thread, action, lock]`, where `action` is `"acquire"` or `"release"`. Events are listed in the order they happened.
- Every lock is exclusive: at most one thread holds it at a time. A thread may hold several locks at once.
- `"acquire"`: if the lock is free, the thread now holds it. If another thread holds it, the requesting thread starts waiting for it and joins the end of that lock's waiting queue.
- `"release"`: the thread gives up a lock it holds. If threads are waiting for that lock, the thread at the front of its queue (the one that started waiting earliest) is given the lock at once and stops waiting. Otherwise the lock becomes free.
- A waiting thread is blocked: it logs no event until it has been given the lock it waits for.
- After the last event, thread `a` *waits on* thread `b` when `a` is waiting for a lock that `b` holds. Return `True` if there are distinct threads `t1, t2, ..., tk`, with `k` at least 2, such that `t1` waits on `t2`, `t2` waits on `t3`, ..., and `tk` waits on `t1`. Otherwise return `False`.
- A waiting thread that is not on such a cycle is not deadlocked, because the thread it waits on can still release the lock. Threads on a cycle are all blocked, so a cycle, once formed, is never broken by a later event; checking the state after the last event is therefore enough.
- An empty log has no deadlock.
### Constraints
- `0 <= len(logs) <= 10^5`
- Every `thread` and `lock` is a non-empty string of at most 20 ASCII letters and digits. Thread names and lock names are separate: a thread and a lock may share a name without being related.
- The log is valid under the rules: a thread logs an event only while it is not waiting, never requests a lock it already holds, and releases only locks it holds.
### Examples
**Example 1**
```text
Input: logs = [["T1", "acquire", "A"], ["T2", "acquire", "B"], ["T1", "acquire", "B"], ["T2", "acquire", "A"]]
Output: True
```
T1 holds `A` and T2 holds `B`. T1 then waits for `B`, held by T2, and T2 waits for `A`, held by T1, so T1 waits on T2 and T2 waits on T1.
**Example 2**
```text
Input: logs = [["T1", "acquire", "A"], ["T2", "acquire", "B"], ["T2", "acquire", "A"], ["T1", "release", "A"], ["T1", "acquire", "B"]]
Output: False
```
T2 waits for `A` until T1 releases it; T2 is then given `A` and stops waiting. When T1 requests `B`, held by T2, T1 waits on T2, but T2 is not waiting and can still release `B`.
**Example 3**
```text
Input: logs = [["T1", "acquire", "A"], ["T2", "acquire", "B"], ["T3", "acquire", "C"], ["T1", "acquire", "B"], ["T2", "acquire", "C"], ["T4", "acquire", "A"], ["T3", "acquire", "A"]]
Output: True
```
T1 waits on T2 (lock `B`), T2 waits on T3 (lock `C`), and T3 waits on T1 (lock `A`). T4 also waits on T1 for `A`, ahead of T3 in that lock's queue, but T4 is not on the cycle; the cycle of T1, T2 and T3 makes the answer `True`.
Overview: A coding question that gives the event log of a multithreaded program, in which threads acquire and release exclusive locks and blocked threads queue in order, and asks whether the program ends in a deadlock. It tests simulating lock ownership and hand-off, and finding a cycle of threads that each wait on a lock held by the next.
You are given the event log of a multithreaded program, in the order the events happened. Each event records a thread requesting or releasing a lock. Decide whether the program ends in a deadlock: a group of threads in which each thread is waiting for a lock held by the next thread in the group, so that none of them can ever continue.
Implement `has_deadlock(logs)`, which returns `True` if the state after the last event contains such a group and `False` otherwise.
### Rules
- `logs[i] = [thread, action, lock]`, where `action` is `"acquire"` or `"release"`. Events are listed in the order they happened.
- Every lock is exclusive: at most one thread holds it at a time. A thread may hold several locks at once.
- `"acquire"`: if the lock is free, the thread now holds it. If another thread holds it, the requesting thread starts waiting for it and joins the end of that lock's waiting queue.
- `"release"`: the thread gives up a lock it holds. If threads are waiting for that lock, the thread at the front of its queue (the one that started waiting earliest) is given the lock at once and stops waiting. Otherwise the lock becomes free.
- A waiting thread is blocked: it logs no event until it has been given the lock it waits for.
- After the last event, thread `a` *waits on* thread `b` when `a` is waiting for a lock that `b` holds. Return `True` if there are distinct threads `t1, t2, ..., tk`, with `k` at least 2, such that `t1` waits on `t2`, `t2` waits on `t3`, ..., and `tk` waits on `t1`. Otherwise return `False`.
- A waiting thread that is not on such a cycle is not deadlocked, because the thread it waits on can still release the lock. Threads on a cycle are all blocked, so a cycle, once formed, is never broken by a later event; checking the state after the last event is therefore enough.
- An empty log has no deadlock.
### Constraints
- `0 <= len(logs) <= 10^5`
- Every `thread` and `lock` is a non-empty string of at most 20 ASCII letters and digits. Thread names and lock names are separate: a thread and a lock may share a name without being related.
- The log is valid under the rules: a thread logs an event only while it is not waiting, never requests a lock it already holds, and releases only locks it holds.
### Example 1
```text
Input: logs = [["T1", "acquire", "A"], ["T2", "acquire", "B"], ["T1", "acquire", "B"], ["T2", "acquire", "A"]]
Output: True
```
T1 holds `A` and T2 holds `B`. T1 then waits for `B`, held by T2, and T2 waits for `A`, held by T1, so T1 waits on T2 and T2 waits on T1.
### Example 2
```text
Input: logs = [["T1", "acquire", "A"], ["T2", "acquire", "B"], ["T2", "acquire", "A"], ["T1", "release", "A"], ["T1", "acquire", "B"]]
Output: False
```
T2 waits for `A` until T1 releases it; T2 is then given `A` and stops waiting. When T1 requests `B`, held by T2, T1 waits on T2, but T2 is not waiting and can still release `B`.
Constraints
- 0 <= len(logs) <= 10^5
- logs[i] = [thread, action, lock], where action is "acquire" or "release"; events are listed in the order they happened
- Every thread and lock is a non-empty string of at most 20 ASCII letters and digits
- Thread names and lock names are separate: a thread and a lock may share a name without being related
- The log is valid under the rules: a thread logs an event only while it is not waiting, never requests a lock it already holds, and releases only locks it holds
Examples
Input: ([],)
Expected Output: False
Explanation: Minimum valid: an empty log has no waiting threads, so no deadlock.
Input: ([['T1', 'acquire', 'A']],)
Expected Output: False
Explanation: Singleton: one acquire of a free lock; nobody waits.
Hints
- Only the state after the last event matters: who holds each lock, and which threads are waiting for it in what order.
- Releasing a lock that has waiters never leaves it free: the earliest waiter takes it immediately and is no longer blocked.
- A blocked thread waits for exactly one lock, and that lock has exactly one holder, so each thread waits on at most one other thread.