Count Completed Jobs in a Serial Single-Worker Pipeline
Company: Plaid
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Count Completed Jobs in a Serial Single-Worker Pipeline
An automation pipeline contains stages that execute in order. Each stage is represented as `[number_of_jobs, job_time]`. A stage has one worker, its jobs run one at a time, and the next stage cannot begin until every job in the current stage is complete. Given a total time limit, return how many jobs across the pipeline finish completely within that time.
## Function Signature
```python
def calculate_jobs_completed(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 each job in that stage.
- `time_limit` is the total time available from the start of stage 0.
## Output
Return the total number of fully completed jobs. A job still running when the time limit expires does not count.
## Constraints
- `0 <= len(pipeline) <= 100_000`
- Every stage has exactly two integers.
- `0 <= number_of_jobs <= 10^9`
- `1 <= job_time <= 10^9`
- `0 <= time_limit <= 9_000_000_000_000_000`
- Across the complete pipeline, `sum(number_of_jobs * job_time) <= 9_000_000_000_000_000`.
- These limits keep every 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], [10, 1]]
time_limit = 14
output = 6
```
The first stage completes four jobs in 12 time units. Two time units remain, so two jobs complete in the second stage.
```text
pipeline = [[3, 5], [2, 1]]
time_limit = 12
output = 2
```
Only two jobs in the first stage finish; the second stage cannot start.
Quick Answer: Calculate how many jobs finish before a deadline in a serial, stage-gated, single-worker pipeline. The prompt tests cumulative-time reasoning, partial-stage completion, zero-job stages, very large counts and durations, overflow safety, and linear processing without mutating input.
An automation pipeline contains stages that execute in order. Each stage is given as `[number_of_jobs, job_time]`.
A stage has exactly one worker, so its jobs run one at a time: a stage of `n` jobs each taking `t` time units occupies the worker for `n * t` time units. The next stage cannot begin until every job in the current stage is complete, so the stages are strictly serial and the pipeline starts at time `0`.
Given a total `time_limit`, return how many jobs across the whole pipeline finish completely within that limit.
## Function
```
calculate_jobs_completed(pipeline, time_limit)
```
## Input
- `pipeline[i][0]` is the number of jobs in stage `i`.
- `pipeline[i][1]` is the integer duration of each job in stage `i`.
- `time_limit` is the total time available, measured from the start of stage `0`.
## Output
Return a single integer: the total number of jobs that are fully completed. A job that is still running when the time limit expires does not count. A job that finishes at exactly `time_limit` does count. A stage with `0` jobs occupies the worker for `0` time and therefore does not delay the stages after it.
The answer is a single number, so there is nothing to order or tie-break, but note that both an individual stage's duration and the returned count can exceed the range of a signed 32-bit integer — see the constraints.
Do not mutate `pipeline`.
## Examples
**Example 1**
```
pipeline = [[4, 3], [10, 1]]
time_limit = 14
output = 6
```
Stage `0` completes its 4 jobs in `4 * 3 = 12` time units. Two time units remain, and stage `1`'s jobs take 1 unit each, so 2 of them finish. `4 + 2 = 6`.
**Example 2**
```
pipeline = [[3, 5], [2, 1]]
time_limit = 12
output = 2
```
Stage `0` needs `3 * 5 = 15` time units but only 12 are available. Its first two jobs finish at time 10; the third is still running at time 12, so it does not count. Stage `1` never starts. The answer is 2.
Constraints
- 0 <= len(pipeline) <= 100_000
- Every stage has exactly two integers.
- 0 <= number_of_jobs <= 10^9
- 1 <= job_time <= 10^9
- 0 <= time_limit <= 9_000_000_000_000_000
- Across the complete pipeline, sum(number_of_jobs * job_time) <= 9_000_000_000_000_000.
- These limits keep every 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], [10, 1]], 14)
Expected Output: 6
Explanation: Stage 0 runs 4 jobs of 3 time units = 12. Two units remain, so 2 of the second stage's 1-unit jobs finish: 4 + 2 = 6.
Input: ([[3, 5], [2, 1]], 12)
Expected Output: 2
Explanation: Stage 0 needs 15 time units but only 12 are available, so 2 jobs finish (10 units used) and the third is still running when time expires. Stage 1 never starts.
Hints
- The stages are strictly serial, so a single running clock -- the time already consumed by all earlier stages -- is enough state. Each stage then asks one question of the time that is left.
- A stage either fits entirely in the remaining budget (advance the clock and keep going) or it does not (count how many whole jobs fit, then stop). Decide which case you are in before you count anything.
- Work out the largest values the constraints permit before choosing integer types. A single stage's duration and the returned count can both exceed what a signed 32-bit integer holds, and in JavaScript the quotient of two large integers is not automatically exact.