Count Completed Jobs in a Serial Multi-Worker Pipeline
Company: Plaid
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Count Completed Jobs in a Serial Multi-Worker Pipeline
An automation pipeline contains stages that execute in order. Each stage is represented as `[number_of_jobs, job_time, number_of_workers]`. Workers within one stage process jobs in parallel, but each worker handles at most one job at a time and a job cannot be split. The next stage begins only after every job in the current stage is complete. Given a total time limit, return how many jobs finish completely.
## Function Signature
```python
def calculate_jobs_with_workers(pipeline: list[list[int]], time_limit: int) -> int:
```
## Inputs
- `pipeline[i][0]` is the number of jobs in stage `i`.
- `pipeline[i][1]` is the integer duration of every job in that stage.
- `pipeline[i][2]` is the number of workers available only to that stage.
- All workers in a stage are available when the stage starts.
## Output
Return the total number of jobs completed by `time_limit`. Jobs in progress at the limit do not count.
## Constraints
- `0 <= len(pipeline) <= 100_000`
- Every stage has exactly three integers.
- `0 <= number_of_jobs <= 10^9`
- `1 <= job_time, number_of_workers <= 10^9`
- `0 <= time_limit <= 9_000_000_000_000_000`
- Across the complete pipeline, `sum(ceil(number_of_jobs / number_of_workers) * job_time) <= 9_000_000_000_000_000`.
- These limits keep every batch count, stage duration, cumulative duration, deadline, and returned job count within the exact integer range shared by JavaScript `Number` and signed 64-bit Java/C++ integers.
- The input collection must not be mutated.
## Examples
```text
pipeline = [[4, 3, 2], [10, 1, 1]]
time_limit = 14
output = 12
```
Two workers finish the first four jobs in 6 time units. During the remaining 8 time units, the single worker in stage two finishes eight jobs.
```text
pipeline = [[5, 4, 2], [3, 1, 3]]
time_limit = 9
output = 4
```
Four jobs finish in two complete four-unit batches. The fifth job is incomplete at the limit, so the next stage never begins.
Quick Answer: Count completed jobs in a serial pipeline where each stage has several parallel workers but the next stage waits for all current work. Practice reasoning about completion waves, unfinished batches at the deadline, large integer bounds, zero-job stages, and efficient processing across many stages.
An automation pipeline contains stages that execute in order. Stage `i` is
given as `pipeline[i] = [number_of_jobs, job_time, number_of_workers]`.
- `pipeline[i][0]` is the number of jobs in stage `i`.
- `pipeline[i][1]` is the integer duration of every job in that stage.
- `pipeline[i][2]` is the number of workers available only to that stage.
- All workers of a stage are available the moment that stage starts.
Workers inside one stage process jobs in parallel, but each worker handles at
most one job at a time and a job can never be split between workers. Every job
in a stage takes exactly `job_time` time units. The next stage begins only
after **every** job of the current stage has finished, so an unfinished stage
blocks everything after it.
Given the total time budget `time_limit`, return the number of jobs that
finish completely. A job that is still in progress when the budget runs out
does not count. The pipeline must not be mutated.
## Function signature
```python
def calculate_jobs_with_workers(pipeline, time_limit):
```
## Output
Return a single integer: the total number of jobs completed by `time_limit`,
summed over every stage. Return `0` when nothing finishes. The answer is a
single number, so there is no ordering or tie-breaking to choose.
## Examples
**Example 1**
```text
pipeline = [[4, 3, 2], [10, 1, 1]]
time_limit = 14
output = 12
```
Stage 0 has 2 workers and 4 jobs of 3 time units each, so it needs 2 batches
and finishes at time 6 with all 4 jobs done. Of the remaining 8 time units,
stage 1's single worker completes 8 of its 10 one-unit jobs, so 4 + 8 = 12.
**Example 2**
```text
pipeline = [[5, 4, 2], [3, 1, 3]]
time_limit = 9
output = 4
```
Stage 0 needs `ceil(5 / 2) = 3` batches of 4 time units, i.e. 12 time units,
which exceeds the budget. Two complete batches fit into 9 time units, so
`2 * 2 = 4` jobs finish. The fifth job is still running at the limit, stage 0
never completes, and stage 1 therefore never starts.
Constraints
- 0 <= len(pipeline) <= 100_000
- Every stage has exactly three integers.
- 0 <= number_of_jobs <= 10^9
- 1 <= job_time, number_of_workers <= 10^9
- 0 <= time_limit <= 9_000_000_000_000_000
- Across the complete pipeline, sum(ceil(number_of_jobs / number_of_workers) * job_time) <= 9_000_000_000_000_000.
- These limits keep every batch count, stage duration, cumulative duration, deadline, and returned job count within the exact integer range shared by JavaScript `Number` and signed 64-bit Java/C++ integers.
- The input collection must not be mutated.
Examples
Input: ([[4,3,2],[10,1,1]], 14)
Expected Output: 12
Input: ([[5,4,2],[3,1,3]], 9)
Expected Output: 4
Hints
- Every job inside one stage costs the same, so a stage advances in whole batches: after k batches, exactly min(k * number_of_workers, number_of_jobs) of its jobs are done and k * job_time time has passed.
- Per stage, first decide whether the entire stage fits in the time you have left; only when it does not do you need the count of jobs a partial stage contributes, and at that point you can stop scanning, because a stage that does not finish blocks every stage after it.
- Mind the arithmetic width. A stage duration reaches 9 * 10^15 and the answer can exceed 2^31 - 1, so 32-bit accumulators are not enough; and a batch count multiplied by a worker count can exceed 64 bits, so compare batch counts against ceil(number_of_jobs / number_of_workers) instead of multiplying first.