Implement a multithreaded task executor with semaphores
Company: SoFi
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Design and implement a thread-safe `TaskExecutor` that limits concurrent work using a semaphore-like mechanism.
You are given an interface similar to:
- `initialize(int maxThreads)`: sets up the executor with a maximum number of “worker permits”.
- `acquire(int permits)`: blocks until the requested number of permits is available, then reserves them.
- `execute(Task task, int input)`: runs a task while respecting the permit limit.
A `Task` is an interface and multiple subclasses implement different behaviors, but all must use the same interface. Each task declares:
- how many threads/permits it requires (e.g., `requiredPermits()`), and
- whether `execute(...)` should block until the task finishes (blocking) or return immediately while the task continues in the background (fire-and-forget).
Example tasks:
- `MultiplyTask(factor, xPermits)`: multiplies `input` by `factor`, requires `xPermits`, and is fire-and-forget (i.e., `execute` should not wait for completion).
- `DivideTask(divisor, yPermits)`: divides `input` by `divisor`, requires `yPermits`, and is blocking (i.e., `execute` returns only after completion and returns the computed result).
Requirements:
1. Total permits in use across all running tasks must never exceed `maxThreads`.
2. Permits must be released reliably even if a task throws.
3. The design should be extensible/maintainable: adding a new `Task` type should not require changing `TaskExecutor` logic beyond using the common `Task` interface.
4. Avoid busy-waiting; use proper concurrency primitives.
Specify the key classes/interfaces and implement the core logic of `initialize`, `acquire`, and `execute` (language: Java or pseudocode acceptable).
Quick Answer: This question evaluates understanding of concurrent programming, thread-safety, semaphore-style resource management, exception-safe permit release, and extensible API design, and it falls under the Coding & Algorithms category testing concurrency/multithreading, synchronization primitives, and resource management.
In the original design question, a `TaskExecutor` uses a semaphore to limit concurrent work. For deterministic grading, implement the core scheduling logic as `solution(max_threads, tasks)` instead of using real threads. This is equivalent to calling `initialize(max_threads)` once, then repeatedly performing `acquire` and `execute` for each task. Each task tuple models an object implementing a common Task interface: `(kind, value, permits, duration, input_value)`. `kind == 'M'` is a fire-and-forget `MultiplyTask`; `kind == 'D'` is a blocking `DivideTask`. A task may start only when all of its requested permits are available. Once started, it holds those permits for exactly `duration` time units. Tasks are submitted by a single caller in the given order. If the task is fire-and-forget, the caller immediately submits the next task at the same current time. If the task is blocking, the caller waits until it finishes before submitting the next task. For a divide task, return `input_value // value`; if `value == 0`, record `'ERROR'` instead, but the task still consumes permits for its full duration and must release them afterward. Return a list of `(start_time, finish_time, result)` for every submitted task in submission order, where `result` is `None` for multiply tasks.