FastPrep
Problem · Binary Search

Pipeline Throughput Maximization Under Budget

● MediumUberFULLTIMEOA
See Uber hiring insights

You have a serial pipeline of 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 scaling cost is x * costs[i].

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

Function Description

Complete the function maximizePipelineThroughput in the editor below.

maximizePipelineThroughput has the following parameters:

  1. int[] throughputs: base service throughputs
  2. int[] costs: scaling costs per extra multiple
  3. 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

Spending the full budget can raise the bottleneck service from 2 to 4, but not to 5.

Constraints
  • 1 <= throughputs.length == costs.length <= 2 * 10^5
  • 1 <= throughputs[i], costs[i] <= 10^9
  • 0 <= budget <= 10^18
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
sign in to submit