Katkat
Back

Implement a type-based mutex for tasks

MicrosoftSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests knowledge of synchronization primitives, dictionary-based locking mechanisms, and the ability to manage resource contention based on dynamic categorization.

Problem Statement

Design a TypeBasedMutex class that manages task execution based on a string task_type. Your implementation must ensure that:

  1. Multiple tasks of the same task_type can run concurrently.
  2. Tasks of different task_types must execute exclusively relative to each other (i.e., if a task of type 'A' is running, no task of type 'B' can start until all 'A' tasks have finished).

Implement the following methods:

  • acquire(task_type: str): Blocks the caller until it is safe to execute a task of the given type.
  • release(task_type: str): Signals that the task of the given type has finished.

Constraints

  • The system should handle an arbitrary number of unique task_type strings.
  • You may assume calls to acquire and release for the same type are balanced.
  • Ensure thread safety and avoid busy-waiting.

Example

# Execution sequence:
mutex = TypeBasedMutex()

# Thread 1 calls mutex.acquire('A') -> Success (Global lock acquired for 'A')
# Thread 2 calls mutex.acquire('A') -> Success (Allowed because 'A' is already active)
# Thread 3 calls mutex.acquire('B') -> Blocks (Waiting for 'A' tasks to finish)
# Thread 1 calls mutex.release('A')
# Thread 2 calls mutex.release('A') -> Now the 'A' global lock is free, Thread 3 can proceed

Hints

Hint 1

Use a shared global lock to represent the state of the system being 'occupied' by a specific type.

Hint 2

Maintain a reference counter for each active `task_type` to track how many threads are currently using that type.

Hint 3

Consider using a condition variable to notify waiting threads when the active type's reference count drops to zero.

Follow-up questions

  • How would you modify your design if you wanted to implement a priority system where certain types have preference?
  • What are the performance bottlenecks if there are thousands of unique task types frequently being acquired and released?
  • How would you handle a scenario where a thread dies before calling release?