Amazon VO 面试真题解析：Data Stream 中位数（Median of a Data Stream）

Given a data stream of CPU utilization values as doubles: 10.0, 20.5, 35.0, 45.0, 20.0, 19.0, 18.5, …

Find the median of the data stream.

The expectation is to write a class as below:

median_cpu_util = MedianCPUUtilization()
median_cpu_util.add(10.0)
median_cpu_util.add(20.5)
median_cpu_util.add(35.0)
median_cpu_util.get_median() => 20.5
median_cpu_util.add(45.0)
median_cpu_util.get_median() => ??
median_cpu_util.add(20.0)
median_cpu_util.get_median() => 20.5
median_cpu_util.add(21.0)
median_cpu_util.get_median() => (20.5 + 21) / 2

Java

class MedianCPUUtilization {void add() { }

    double getMedian() {}
}

这道题要求你设计一个支持动态插入与实时查询中位数的数据结构。输入是不断到来的 CPU 利用率双精度数值流，核心目标是让 <code>add</code> 和 <code>getMedian</code> 都足够高效。标准做法通常是维护两个堆：一个大顶堆保存较小的一半元素，一个小顶堆保存较大的一半元素，并始终保证两边大小平衡、堆顶元素可直接用于计算中位数。这样每次插入只需调整堆即可，查询中位数可以做到 O(1)，适合面试中考察数据流、堆和在线算法的场景。