How should I practice Pipeline Throughput Maximization Under Budget?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Uber online assessment problems in FastPrep.

Is Pipeline Throughput Maximization Under Budget associated with Uber?

FastPrep tags this as a Uber online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Binary Search

Pipeline Throughput Maximization Under Budget

Learn this problem

● Medium

UberFULLTIMEOA

See Uber hiring insights

Problem statement

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

maximizePipelineThroughput(throughputs: int[], costs: int[], budget: long) → long

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

Example 1

throughputs = [5, 2, 4]costs = [3, 10, 2]budget = 0return = 2

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

Example 2

throughputs = [5, 2, 4]costs = [3, 10, 2]budget = 20return = 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.