FastPrepFastPrep
Problem Brief

Get Maximum Throughput

INTERNNEW GRADOA

The developers at Amazon are working on optimizing their database query times. There are n host servers, where the throughput of the ith host server is given by host_throughput[i].

These host servers are grouped into clusters of size three. The throughput of a cluster, denoted as cluster_throughput, is defined as the median of the host_throughput values of the three servers in the cluster. Each server can be part of at most one cluster, and some servers may remain unused.

The total system throughput, called system_throughput, is the sum of the throughputs of all the clusters formed. The task is to find the maximum possible system_throughput.

Note: The median of a cluster of three host servers is the throughput of the 2nd server when the three throughputs are sorted in either ascending or descending order.

Function Description

Complete the function getMaxThroughput in the editor.

getMaxThroughput has the following parameter:

  1. int host_throughput[n]: an array denoting the throughput of the host servers

Returns

long: the maximum system_throughput

πŸ³π“‚ƒ π“ˆ’π“Έ Couldn’t do this without da best spike!π“‚ƒπŸ–Š

1Example 1

Input
host_throughput = [4, 6, 3, 5, 4, 5]
Output
9
Explanation
Here, n = 6, and the host throughput is given by host_throughput = [4, 6, 3, 5, 4, 5]. The maximum number of clusters that can be formed is 2. One possible way to form the clusters is to select the 1st, 2nd, and 3rd host servers for the first cluster, and the 4th, 5th, and 6th host servers for the second cluster. The cluster_throughput of the first cluster [4, 6, 3] will be 4 (the median), and the cluster_throughput of the second cluster [5, 4, 5] will be 5 (the median). Thus, the system_throughput will be 4 + 5 = 9.

2Example 2

Input
host_throughput = [2, 3, 4, 3, 4]
Output
4
Explanation
The max number of clusters that can be formed is 1, and two host servers will remain unused. One possible cluster is to select the 1st, 3rd, and 5th host servers. The cluster_throughput of [2, 4, 4] will be 4 (the median value :) Thus, the system_throughput for all clusters will be 4.

Constraints

Limits and guarantees your solution can rely on.

  • 1 ≀ n ≀ 2 * 10^5
  • 1 ≀ host_throughput[i] ≀ 10^9
public long amazonGetMaxThroughput(int[] host_throughput) {
  // write your code here
}
Input

host_throughput

[4, 6, 3, 5, 4, 5]

Output

9

Sign in to submit your solution.