Implement a type-based mutex for tasks
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: nan
Interview Round: Technical Screen
## Problem
You are given a multithreaded task runner. Each task has:
- `task_id: int`
- `task_type: "gen" | "score"`
- `duration: int` (seconds)
Each task runs in its own thread and calls a shared lock before and after doing work.
```python
from dataclasses import dataclass
from typing import Literal
@dataclass
class SampleTask:
task_id: int
task_type: Literal["gen", "score"]
duration: int
class TaskLock:
def acquire(self, task: SampleTask) -> None:
raise NotImplementedError
def release(self, task: SampleTask) -> None:
raise NotImplementedError
```
The task runner does:
1. `lock.acquire(task)`
2. sleeps for `task.duration`
3. `lock.release(task)`
## Task
Implement a `MutexTaskLock(TaskLock)` such that:
- Multiple tasks of the **same** `task_type` may run **concurrently**.
- Tasks of **different** `task_type` must **not** run at the same time (i.e., if any `gen` task is running, no `score` task may run, and vice versa).
- The implementation must be thread-safe and avoid deadlocks.
You may use Python threading primitives such as `threading.Lock`, `threading.Condition`, or semaphores.
## Clarifications / Expected behavior
- If no tasks are running, either type may acquire the lock.
- If tasks of one type are running, tasks of the other type must block until all running tasks of the current type finish and release.
- It is acceptable for waiting tasks to wake up and re-check conditions (i.e., use a loop around `wait`).
Quick Answer: This question evaluates understanding of concurrency and synchronization primitives, testing the ability to design a thread-safe type-based mutex that permits concurrent execution of tasks with the same type while preventing concurrent execution across different types.
You are modeling the core behavior of a multithreaded task lock. Real threads are not used in this problem. Instead, you are given a chronological log of lock operations, and you must verify whether the log could have been produced by a correct type-based mutex.
Each event is a string in one of these forms:
- `acquire <task_id> <task_type>`
- `release <task_id> <task_type>`
Where `task_type` is either `gen` or `score`.
A correct mutex follows these rules:
1. Multiple running tasks of the same type may exist at the same time.
2. Tasks of different types may never overlap. If any `gen` task is running, no `score` task may acquire, and vice versa.
3. A task cannot acquire twice without releasing.
4. A task can release only if it is currently running.
5. The `task_type` used at release must match the type used when that task acquired.
Return the 0-based index of the first invalid event. If the entire log is valid, return `-1`.
Constraints
- 0 <= len(events) <= 200000
- Each event uses `task_type` equal to `gen` or `score`
- `task_id` is an integer
- Events are processed in the given order
Examples
Input: ([],)
Expected Output: -1
Explanation: There are no events, so nothing violates the mutex rules.
Input: (["acquire 1 gen", "acquire 2 gen", "release 1 gen", "release 2 gen", "acquire 3 score", "release 3 score"],)
Expected Output: -1
Explanation: Two `gen` tasks run together, then after both finish, a `score` task runs. This is valid.
Input: (["acquire 1 gen", "acquire 2 score", "release 1 gen"],)
Expected Output: 1
Explanation: Event 1 is invalid because a `score` task tries to acquire while a `gen` task is still running.
Input: (["acquire 5 score", "acquire 5 score"],)
Expected Output: 1
Explanation: The same task cannot acquire twice without releasing first.
Input: (["acquire 7 gen", "release 7 score"],)
Expected Output: 1
Explanation: Task 7 acquired as `gen`, so releasing it as `score` is invalid.
Input: (["release 1 gen"],)
Expected Output: 0
Explanation: A task cannot release unless it is currently running.
Hints
- Track the currently active task type, if any. If the lock is active for one type, an acquire for the other type is invalid.
- Use a hash map from `task_id` to its running `task_type` so you can validate duplicate acquires and releases in O(1) time.