How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at SoFi.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at SoFi during technical interviews.

Implement a multithreaded task executor with semaphores

Quick Overview

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.

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.

Constraints

0 <= len(tasks) <= 200000
1 <= max_threads <= 10^9
For every task, 1 <= permits <= max_threads
0 <= duration <= 10^9
`kind` is either `'M'` or `'D'`
For divide tasks with `value != 0`, assume `value` divides `input_value` exactly

Examples

Input: (3, [('M', 2, 2, 5, 4), ('M', 5, 1, 4, 7), ('D', 3, 2, 2, 18), ('D', 0, 1, 1, 9), ('D', 3, 3, 2, 27)])

Expected Output: [(0, 5, None), (0, 4, None), (5, 7, 6), (7, 8, 'ERROR'), (8, 10, 9)]

Explanation: The first two multiply tasks start immediately at time 0 and consume all 3 permits. The first divide task must wait until time 5 to get 2 permits. The divide-by-zero task returns 'ERROR' but still releases its permit at time 8, allowing the final task to start.

Input: (5, [])

Expected Output: []

Explanation: No tasks are submitted, so the schedule is empty.

Input: (4, [('M', 2, 2, 3, 5), ('M', 3, 2, 3, 5), ('D', 5, 4, 2, 20)])

Expected Output: [(0, 3, None), (0, 3, None), (3, 5, 4)]

Explanation: Both multiply tasks run from time 0 to 3 and together use all 4 permits. The divide task can only start once both finish at time 3.

Input: (3, [('M', -2, 1, 4, 7), ('D', 2, 2, 3, -8), ('D', 7, 3, 1, 21)])

Expected Output: [(0, 4, None), (0, 3, -4), (4, 5, 3)]

Explanation: The blocking divide task can run alongside the first multiply task because enough permits are free. The last task needs all 3 permits, so it must wait until the multiply task finishes at time 4.

Input: (2, [('M', 10, 2, 0, 3), ('D', 5, 2, 1, 20)])

Expected Output: [(0, 0, None), (0, 1, 4)]

Explanation: The zero-duration multiply task starts and finishes at time 0, immediately freeing both permits for the divide task.

Hints

Keep a min-heap of currently running tasks ordered by finish time. When you need more permits, jump time forward to the next finishing task and release all tasks that end then.
The caller's current time only advances in two situations: when waiting to acquire permits, or when a blocking divide task is running. Fire-and-forget multiply tasks do not advance the caller's time.

Quick Overview