FastPrepFastPrep
Problem Brief

Pipeline Throughput Maximization Under Budget

FULLTIMEOA
See Uber online assessment and 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.

1Example 1

Input
throughputs = [5, 2, 4], costs = [3, 10, 2], budget = 0
Output
2
Explanation

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

2Example 2

Input
throughputs = [5, 2, 4], costs = [3, 10, 2], budget = 20
Output
4
Explanation

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

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= throughputs.length == costs.length <= 2 * 10^5
  • 1 <= throughputs[i], costs[i] <= 10^9
  • 0 <= budget <= 10^18
public long maximizePipelineThroughput(int[] throughputs, int[] costs, long budget) {
    // write your code here
}
Input

throughputs

[5, 2, 4]

costs

[3, 10, 2]

budget

0

Output

2

Sign in to submit your solution.