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.
这道题的核心是把所有包分配到 k 个通道，使每个通道至少有一个包，并让各通道“质量”（即该通道内数据大小的中位数）之和最大。由于中位数只和排序后的相对位置有关，最优策略通常是先将数组排序，再围绕较大的元素去构造每个通道的中位数贡献；当一个通道只分到一个包时，它的中位数就是该包本身。题目要求如果结果是小数则向上取整，因此实现时需要注意偶数长度通道的中位数可能是平均数。整体思路常见于排序 + 贪心 / 数学构造，重点是尽量把大的值作为各通道的中位数，从而最大化总和。
