海量数据与流式日志如何求中位数
哪些公司问过
答案要点
- 数据无法全量载入内存,需分治、分桶计数或外部排序
- 按高位分桶统计计数,累加定位中位数所在桶,再对该桶按低位二次计数
- 有符号数需处理符号位,偶数个数时取中间两个数
- 流式近似可用 t-digest、GK、KLL 等分位数草图,内存可控且可合并
- 也可用蓄水池采样得到随机样本再求中位数,精度依赖样本量
易错点
- 试图把 20 亿个数全部读入内存排序
- 把用于估计频次的 Count-Min Sketch 当成求分位数的工具
- 分桶时忽略有符号整数的符号位,导致桶顺序错误
- 找到所在桶后忘记加上前面各桶的累计数量
面试官常见追问
- 如果数据能放进内存但持续流入,怎么实时维护中位数?
- 外部排序方案有什么缺点?
- t-digest 为什么适合求分位数?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。