How should I practice Maximize Pipeline Throughput Under a Scaling Budget?

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

Is Maximize Pipeline Throughput Under a Scaling Budget associated with Microsoft?

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

Maximize Pipeline Throughput Under a Scaling Budget

Microsoft● MediumNEW GRADINTERNOA

Problem statement

You have a serial pipeline of services. Service i has base throughput throughput[i] and one scaling operation costs scalingCost[i].

After scaling service i exactly x times, its capacity is throughput[i] * (x + 1) and the spent budget is x * scalingCost[i].

The pipeline throughput is the minimum capacity among all services. Given a total budget, return the maximum pipeline throughput that can be achieved without exceeding the budget.

Function

maximizePipelineThroughput(throughput: int[], scalingCost: int[], budget: long) → long

Examples

Example 1

throughput = [3,2,5]scalingCost = [2,5,10]budget = 28return = 6

Reaching 6 costs 2 + 10 + 10 = 22. Reaching 7 would cost 4 + 15 + 10 = 29, which exceeds the budget.

Example 2

throughput = [5,2,4]scalingCost = [3,10,2]budget = 1return = 2

The budget of 1 is smaller than every scaling cost, so no service can be scaled. The pipeline remains limited by the service whose base throughput is 2.

Example 3

throughput = [4,2,7]scalingCost = [3,5,6]budget = 32return = 10

Scale services 0, 1, and 2 by 2, 4, and 1 operations respectively:

Scaling configuration within the budget of 32
Service	Scale from	Scale to	Operations	Cost per operation	Total cost
0	4	12	2	3	6
1	2	10	4	5	20
2	7	14	1	6	6

The total cost is 6 + 20 + 6 = 32, and the serial pipeline throughput is min(12, 10, 14) = 10. Reaching 11 would require at least 6 + 25 + 6 = 37, which exceeds the budget.

Constraints

1 <= throughput.length = scalingCost.length <= 10^5
1 <= throughput[i] <= 10^7
1 <= scalingCost[i] <= 200
1 <= budget <= 10^9
The answer is at most 10^9.