Round 1
Questions: The manager oversees a set of n servers, each with a designated upgrade capacity represented by the array element capacity[i]. The goal is to create precisely k upgrade batches, where the number of servers in the ith batch is represented by the array element numServers[i] where 0 ≤ i < n.
The efficiency of an upgrade batch is determined by the difference between the maximum and minimum upgrade capacities of the servers within that batch. The manager's objective is to allocate servers to the upgrade batches in a way that maximizes the sum of efficiencies across all k batches. The task is to find the maximum sum of efficiency.
Note: Each server must be assigned to exactly one upgrade batch.
Example
n = 4
k = 2
capacity = [3, 6, 1, 2]
numServers = [1, 3]
One of the optimal ways is:
- Batch 1 takes the first server. Therefore, the efficiency of the batch = 3 - 3 = 0
- Batch 2 takes the servers at indices 1, 2, and 3. The efficiency of the batch = 6 - 1 = 5
Hence, the sum of efficiencies is 0 + 5 = 5.
Function Description Complete the function getMaximumEfficiency in the editor below.
getMaximumEfficiency takes the following parameter(s):
- int capacity[n]: the upgrade capacity of each server
- int numServers[k]: the number of servers in each upgrade batch
Returns long: the maximum possible sum of efficiency of k upgrade batches
Constraints
- 1 ≤ n ≤ 2×10^5
- 1 ≤ k ≤ n
- 1 ≤ capacity[i] ≤ 10^9
- 1 ≤ numServers[i] ≤ n
- ∑ numServers[i] = n
Sample Case 0 Sample Input for Custom Testing
STDIN FUNCTION ----- -------- 4 → capacity[] size n = 4 1 → capacity = [1, 2, 3, 4] 2 3 4 → numServers[] size k = 1 4 → numServers = [4]
Sample Output
3
Explanation Since there is only one batch to upgrade all the servers, the efficiency of the batch is 4 - 1 = 3. Hence, the sum of efficiencies of all the batches (which is 1) is 3.
Sample Case 1 Sample Input for Custom Testing
STDIN FUNCTION ----- -------- 3 → capacity[] size n = 3 4 → capacity = [4, 2, 1] 2 1 3 → numServers[] size k = 3 1 → numServers = [1, 1, 1] 1 1
Sample Output
0
Explanation Since the size of each server upgrade batch is 1, all 3 servers are upgraded in different batches, and the efficiency of each batch is 0. Hence, the sum of efficiencies is 0.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.