Amazon | SDE2 | OA

Round 1

Questions: Amazon's AWS provides fast and efficient server solutions. The developers want to stress-test the quality of the servers' channels. They must ensure the following:

• Each of the packets must be sent via a single channel.
• Each of the channels must transfer at least one packet.

The quality of the transfer for a channel is defined by the median of the sizes of all the data packets sent through that channel.

Note: The median of an array is the middle element if the array is sorted in non-decreasing order. If the number of elements in the array is even, the median is the average of the two middle elements.

Find the maximum possible sum of the qualities of all channels. If the answer is a floating-point value, round it to the next higher integer.

Example packets = [1, 2, 3, 4, 5] channels = 2

At least one packet has to go through each of the 2 channels. One maximal solution is to transfer packets {1, 2, 3, 4} through channel 1 and packet {5} through channel 2.

The quality of transfer for channel 1 is (2 + 3)/2 = 2.5 and that of channel 2 is 5. Their sum is 2.5 + 5 = 7.5 which rounds up to 8.

Function Description Complete the function findMaximumQuality in the editor below.

findMaximumQuality has the following parameter(s):

• int packets[n]: the packet sizes
• int channels: the number of channels

Returns long int: the maximum sum possible

Constraints

• 1 ≤ len(packets) ≤ 5×10^5
• 1 ≤ packets[i] ≤ 10^9
• 1 ≤ channels ≤ len(packets)

Sample Case 0 Sample Input For Custom Testing

STDIN        Function
-----        ------
5       →    packets[] size n = 5
2       →    packets = [2, 2, 1, 5, 3]
2
1
5
3
2       →    channels = 2

Sample Output

7

Explanation One solution is to send packet {5} through one channel and {2, 2, 1, 3} through the other. The sum of quality is 5 + (2 + 2)/2 = 7

Sample Case 1 Sample Input For Custom Testing

STDIN         Function
-----         ------
3        →    packets[] size n = 3
89       →    packets = [89, 48, 14]
48
14
3       →    channels = 3

Sample Output

151

Explanation There are 3 channels for 3 packets. Each channel carries one, so the overall sum of quality is 89 + 48 + 14 = 151

Working Solution

public static long findMaximumQuality(List<Integer> packets, int channels) {
    int n = packets.size();
    
    if (channels == 1) {
        long result = 0;
        for (int packet : packets) {
            result += packet;
        }
        return result;
    }
    
    List<Integer> packetsSorted = new ArrayList<>(packets);
    packetsSorted.sort(Collections.reverseOrder());

    // Calculate the result
    long result = 0;
    for (int i = 0; i < channels - 1; i++) {
        result += packetsSorted.get(i);
    }
    
    List<Integer> medianTemp = packetsSorted.subList(channels - 1, packetsSorted.size());
    
    double temp;
    if (medianTemp.size() % 2 == 0) {
        int mid1 = medianTemp.size() / 2;
        int mid2 = mid1 - 1;
        temp = (medianTemp.get(mid1) + medianTemp.get(mid2)) / 2.0;
    } else {
        int mid = medianTemp.size() / 2;
        temp = medianTemp.get(mid);
    }

    // Add the median to the result
    result += Math.ceil(temp);

    return result;
}

Candidate's Approach

No approach provided.

Interviewer's Feedback

No feedback provided.

---