Amazon OA Interview Question: Maximize the Sum of Channel Medians
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 = 2At 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 key idea is to partition all packets into exactly k non-empty channels so that the sum of channel medians is as large as possible. Since a channel’s median depends only on the sorted order of values inside that channel, the best strategy is usually to sort the packet sizes and greedily assign large values so they become medians of different groups. Single-element channels contribute their only packet as the median, while even-sized channels may produce a fractional median that must be rounded up. This is a classic sorting plus greedy construction problem aimed at maximizing the contribution of the largest feasible elements.
