FastPrep
Problem · Binary Search

Maximum Pipeline Throughput

Learn this problem
● MediumMicrosoftOA
See Microsoft hiring insights

Problem statement

A data-processing pipeline consists of n services connected in series. The output of service i is the input to service i + 1. The base throughput of service i is throughput[i] messages per minute.

Each service can be scaled independently. Scaling service i once costs scalingCost[i]. After scaling that service x times, its throughput becomes throughput[i] * (1 + x).

Because the services operate in series, the pipeline throughput is limited by the service with the smallest resulting throughput.

Given the arrays throughput and scalingCost, together with a total budget, return the maximum pipeline throughput achievable without spending more than the budget.

Function

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

Examples

Example 1

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

An optimal scaling configuration is shown below.

Optimal scaling configuration
Service indexScale fromScale toTimes scaledCost per scalingTotal cost
0412236
12104520
2714166

The total cost is 6 + 20 + 6 = 32. The scaled service throughputs are [12, 10, 14], so the serial pipeline throughput is 10.

Constraints

  • throughput.length = scalingCost.length
  • For this exercise, assume the pipeline contains at least one service, every value in throughput and scalingCost is a positive integer, and budget is a non-negative integer.

More Microsoft problems

drafts saved locally
public long getMaxThroughput(int[] throughput, int[] scalingCost, int budget) {
    // Write your code here
}
throughput[4, 2, 7]
scalingCost[3, 5, 6]
budget32
expected10
checking account