Company: Squarepoint
Difficulty: medium
Maximize Minimum Throughput Problem Description You are given n services. For each service i , the following information is provided: t[i] → the base throughput of the service c[i] → the cost of scaling the service by one step If you scale service i by an integer amount x[i] ≥ 0 , then: Its throughput becomes: throughput_i = (x[i]+1) · t[i] The cost of scaling it is: x[i] · c[i] You are also given a total budget B . Your task is to allocate scaling amounts x[i] to the services such that: The total cost of scaling does not exceed B . The minimum throughput across all services is as large as possible. Formally, maximize: min(throughput_1, throughput_2, ..., throughput_n) subject to the constraint: ∑ (x[i] · c[i]) ≤ B (from i=1 to n) Return this maximum possible bottleneck throughput. Constraints x[i] must be an integer. x[i] ≥ 0 for all services i . The total cost of scaling, ∑ (x[i] · c[i]) , must not exceed the budget B .