FastPrep
Problem · Binary Search

Get Max Throughput

Learn this problem
● HardCitadelINTERNNEW GRADOA

Problem statement

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

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

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! 🌺

    Examples

    Example 1

    throughput = [4, 2, 7]scaling_cost = [3, 5, 6]budget = 32return = 10
    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.

    Example 2

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

    Constraints

      404 not found 🥲

    More Citadel problems

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