Maximum Pipeline Throughput Within Budget

Reported in interviews at Two Sigma

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.

Related free problems