AlgoMaster Logo
AlgoMasterDesign a Deadlock-Free Two-Key Executormedium

Design a Deadlock-Free Two-Key Executor

medium

Design a task executor that acquires exclusive access to two keyed resources without deadlocking.

Implement the TwoKeyTaskExecutor class:

  • TwoKeyTaskExecutor(keyCount) creates an executor for keys from 0 through keyCount - 1.
  • execute(firstKey, secondKey, task) waits until it owns both requested keys, invokes task exactly once while holding them, then returns.

Two callbacks must not overlap if their key pairs share either key. Callbacks whose key pairs are disjoint must be independent and capable of executing at the same time.

Callers may provide the keys in any order. Requests such as (1, 2) and (2, 1) must never deadlock. Acquire distinct keys in one consistent global order, such as the smaller key before the larger key.

If both arguments contain the same key, acquire that key only once. The implementation must work with non-reentrant locks.

If task throws an unchecked exception or panics, both locks must still be released and the original failure must continue to the caller. Different executor instances must be independent. No fairness or execution-order policy is required.

The judge creates all caller threads and supplies the callbacks. Standard concurrency, callback, lock, and thread APIs are preloaded, so you do not need import, include, package, or using statements.

Example 1:

Input:

Output:

Explanation: Both requests acquire key 1 before key 3, regardless of argument order. This prevents circular waiting.

Example 2:

Input:

Output:

Explanation: The key sets {0, 1} and {2, 3} are disjoint.

Constraints

  • 1 <= keyCount <= 100
  • 0 <= firstKey, secondKey < keyCount
  • At most 100 threads use one executor at a time.
  • At most 50000 calls are made per executor.
  • A callback may complete normally or fail with an unchecked exception or panic.
  • A callback does not call execute on the same executor.
  • Judge threads are not interrupted while waiting for keys.
Loading...

Input

Thread 1: executor.execute(1, 3, taskA)
Thread 2: executor.execute(3, 1, taskB)

Output

taskA and taskB never overlap, and both finish

Run is a quick check against the first couple of scenarios, which is roughly what these examples describe. Submit puts your class under the full set, which stays hidden.