FastPrepMaximize Pipeline Throughput Under a Scaling Budget

Maximize Pipeline Throughput Under a Scaling Budget

Microsoft logoMicrosoft● MediumNEW GRADINTERNOA
Learn

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 = 0return = 2

With no available scaling operation, the pipeline remains limited by the service whose base throughput is 2.

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.

More Microsoft problems

See Microsoft hiring insights
public long maximizePipelineThroughput(int[] throughput, int[] scalingCost, long budget) {
  // write your code here
}
throughput[3,2,5]
scalingCost[2,5,10]
budget28
expected6
Checking account…