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.
int throughput[n]: the throughput generated by each of the n services - 2.
int scaling_cost[n]: the cost of scaling up a service one time - 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:
α‘£ β’ . β’ π© β‘ Much appreciation to Aura Man! πΊ
Example 1:
Input: throughput = [4, 2, 7], scaling_cost = [3, 5, 6], budget = 32
Output: 10
Explanation: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:
Input: throughput = [7, 3, 4, 6], scaling_cost = [2, 5, 4, 3], budget = 25
Output: 9
Explanation:To maximize the throughput of the final service, an optimal solution is:
404 not found π₯²
input:
output: