FastPrepFastPrep
Problem Brief

Get Max Throughput

INTERNNEW GRADOA

A data processing pipeline consists of n services connected in a series where output of the ith service serves as the input of the (i + 1)th service. However, the processing units have varying latenciesl, and the throughput of the ith units is represented by the array throughput[i] in messages per minute. The first service receives input through an API, and the nth service produces the final output.

Each service can be scaled up independently, with the cost of scaling up the ith service on unit equal to scaling_cost[i]. After scaling up a service x times, it can process throughput[i] * (i + x) messages per minute.

Given the arrays throughput and scaling_cost, both of size n, and an integer budget representing the budget available, determine the optimal scaling configuration for the services such that the throughput generated by the nth service is maximized.

Function Description

Complete the function getMaxThroughput in the editor πŸ‘‰πŸ‘‰.

getMaxThroughput has the following parameters:

  1. 1. int throughput[n]: the throughput generated by each of the n services
  2. 2. int scaling_cost[n]: the cost of scaling up a service one time
  3. 3. int budget: the available memory

Returns

long: the max value of the throughput generated at the end of the composite service after scaling within the budget.

Key insight:

  • _consider all feasible sol'ns_
  • Binary search across all possible throughput values, checking if can be attained within budget

    • α‘£ β€’ . β€’ 𐭩 β™‘ Much appreciation to Aura Man! 🌺

    1Example 1

    Input
    throughput = [4, 2, 7], scaling_cost = [3, 5, 6], budget = 32
    Output
    10
    Explanation
    Example 1 illustration
    To maximize the throughput of the final service, an optimal solution is: When these units are applied in series, they generate a throughput of 10 units, the max possible throughput given the budget. Hence the answer is 10.

    2Example 2

    Input
    throughput = [7, 3, 4, 6], scaling_cost = [2, 5, 4, 3], budget = 25
    Output
    9
    Explanation
    Example 2 illustration
    To maximize the throughput of the final service, an optimal solution is:

    Constraints

    Limits and guarantees your solution can rely on.

      404 not found πŸ₯² 
    public long getMaxThroughput(int[] throughput, int[] scaling_cost, int budget) {
  // write your code here
}
    Input

    throughput

    [4, 2, 7]

    scaling_cost

    [3, 5, 6]

    budget

    32

    Output

    10

    Sign in to submit your solution.