FastPrep
Problem · Binary Search

Pipeline Throughput Maximization Under Budget

● MediumUberFULLTIMEOA
See Uber hiring insights

You have a serial pipeline of n services. Service i has base throughput throughputs[i] and scaling cost costs[i].

If you scale service i by a non-negative integer x, its throughput becomes throughputs[i] * (1 + x) and the total scaling cost for that service is x * costs[i].

Because the pipeline is serial, the overall pipeline throughput equals the minimum throughput across all services after scaling. Given a total budget, compute the maximum achievable overall pipeline throughput.

To achieve a target throughput T for service i, you need x = ceil(T / throughputs[i]) - 1 scale steps (where x = 0 if throughputs[i] >= T), at a cost of x * costs[i]. The minimum total budget required to achieve overall throughput T is the sum of these costs over all services. Binary search on T to find the maximum feasible throughput within the given budget.

Function Description

Complete the function maximizePipelineThroughput in the editor below.

maximizePipelineThroughput has the following parameters:

  • int[] throughputs: base service throughputs
  • int[] costs: scaling costs per extra multiple
  • long budget: the total scaling budget

Returns

long: the maximum achievable pipeline throughput.

Examples
01 · Example 1
throughputs = [5, 2, 4]
costs = [3, 10, 2]
budget = 0
return = 2

With no budget, the pipeline throughput is the minimum base throughput, which is 2.

02 · Example 2
throughputs = [5, 2, 4]
costs = [3, 10, 2]
budget = 20
return = 4
Binary search on target throughput T. For T=4: service 0 already has throughput 5>=4 (cost 0), service 1 needs ceil(4/2)-1=1 scale step (cost 1*10=10), service 2 already has throughput 4>=4 (cost 0). Total cost = 10 <= 20, so T=4 is achievable. For T=5: service 1 needs ceil(5/2)-1=2 steps (cost 20), service 2 needs ceil(5/4)-1=1 step (cost 2). Total cost = 22 > 20, so T=5 is not achievable. Therefore the maximum throughput is 4.
Constraints
  • 1 <= throughputs.length == costs.length <= 2 * 10^5
  • 1 <= throughputs[i], costs[i] <= 10^9
  • 0 <= budget <= 10^18
  • The answer (maximum achievable pipeline throughput) fits within a long (64-bit signed integer).
  • When computing the cost to achieve a target throughput T, use 128-bit or careful overflow-checked arithmetic, as intermediate values may exceed long range.
More Uber problems
drafts saved locally
public long maximizePipelineThroughput(int[] throughputs, int[] costs, long budget) {
    // write your code here
}
throughputs[5, 2, 4]
costs[3, 10, 2]
budget0
expected2
checking account