How should I practice Detect a Deadlock from Lock Logs?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Helm.ai phone screen problems in FastPrep.

Is Detect a Deadlock from Lock Logs associated with Helm.ai?

FastPrep tags this as a Helm.ai phone screen coding practice problem when the problem catalog has that company and stage context.

Detect a Deadlock from Lock Logs

Helm.ai● MediumFULLTIMEPHONE SCREEN

Problem statement

Several threads share locks. You are given a log of lock requests and releases, logs, in the order they happened. Each entry is "<thread> acquire <lock>" or "<thread> release <lock>". A thread and a lock may have the same name; they are still different things.

Replay the log with these rules:

acquire: if the lock is free, the thread now holds it. If another thread holds it, the requesting thread starts waiting for that lock and is blocked.
release: the thread gives up the lock. If threads are waiting for it, the one that started waiting earliest now holds it and is no longer blocked. Otherwise the lock becomes free.

A deadlock is a cycle of blocked threads where each thread waits for a lock held by the next thread in the cycle, and the last thread waits for a lock held by the first. None of them can ever run again, so a deadlock never goes away once it forms.

Return true if at least one deadlock exists after the whole log is replayed, and false otherwise. Other threads may keep running while some threads are deadlocked.

Function

hasDeadlock(logs: String[]) → boolean

Examples

Example 1

logs = ["t1 acquire A","t2 acquire B","t1 acquire B","t2 acquire A"]return = true

t1 holds A and t2 holds B. Then t1 waits for B (held by t2) and t2 waits for A (held by t1). This is a cycle, so the answer is true.

Example 2

logs = ["t1 acquire A","t2 acquire A","t1 acquire B","t1 release B","t1 release A","t2 release A"]return = false

t2 waits for A while t1 holds it. t1 keeps running, takes and releases B, then releases A, which goes to t2. t2 releases it later. Nobody is left waiting, so the answer is false.

Example 3

logs = ["t1 acquire A","t2 acquire B","t3 acquire C","t1 acquire B","t2 acquire C","t3 release C","t3 acquire A"]return = false

t1 waits for B (held by t2) and t2 waits for C (held by t3).
t3 releases C, so t2 gets it and runs again. Then t3 waits for A, held by t1.
Now t3 waits for t1, and t1 waits for t2, but t2 is not blocked. The chain ends, so there is no cycle and the answer is false.

Example 4

logs = ["t1 acquire A","t1 acquire B","t1 release B","t1 release A","t2 acquire B","t2 acquire A","t2 release A","t2 release B"]return = false

t1 takes A then B, and t2 later takes B then A. This opposite lock order could deadlock in a different run, but here t1 releases both locks before t2 starts, so no thread ever waits. Only an actual deadlock counts, so the answer is false.

Example 5

logs = ["p acquire X","q acquire Y","p acquire Y","q acquire X","r acquire Z","r release Z","s acquire Z","s release Z"]return = true

p holds X and waits for Y, while q holds Y and waits for X: a deadlock. Threads r and s keep taking and releasing Z afterwards, but that does not clear the deadlock, so the answer is true.

Constraints

0 <= logs.length <= 1500
Each logs[i] is "<thread> acquire <lock>" or "<thread> release <lock>", with single spaces.
Thread and lock names have 1 to 10 characters, all letters or digits.
The log is consistent: a waiting thread has no entries until it gets its lock, a thread releases only locks it holds, and a thread never acquires a lock it already holds.

See Helm.ai hiring insights