Maximum Pipeline Throughput Within Budget
Problem statement
A data pipeline is a series of $n$ processing units. Unit $i$ has base throughput throughput[i]. Because the units are in series, the pipeline's overall throughput is set by its slowest unit (the bottleneck).
You may scale any unit independently. Scaling unit $i$ a total of $x$ times costs scaling_cost[i] per scale (so $x \cdot \text{scaling\_cost}[i]$ total) and raises its throughput to $\text{throughput}[i] \cdot (1 + x)$.
Given throughput, scaling_cost, and an integer budget, find the maximum achievable bottleneck throughput.
getMaximumThroughput(throughput: List[int], scaling_cost: List[int], budget: int) -> int
Constraints
- Scaling is multiplicative: $\text{throughput}[i] \cdot (1 + x)$, not additive.
Example
throughput = [4, 2, 7]
scaling_cost = [3, 5, 6]
budget = 32
Scale unit 0 to 12 ($x=2$, cost 6), unit 1 to 10 ($x=4$, cost 20), unit 2 to 14 ($x=1$, cost 6). Total cost $= 32 \le$ budget; bottleneck $= \min(12, 10, 14) = 10$. Answer: 10.
Show hint
If someone handed you a target bottleneck value, how easy would it be to decide whether the budget can afford it?
Relevant roles: ML Engineer, MLOps Engineer, Forward Deployed Engineer and AI Engineer.