面试题库 › C++ / 后端 › 海量数据与流式日志如何求中位数

海量数据与流式日志如何求中位数

难度 ★★☆在 5 场真实面经中被问到 方向:C++ / 后端考点:TopK与海量数据

哪些公司问过

百度3拼多多1阿里巴巴1

常见岗位:C++ 后端、Java 后端

答案要点

  1. 数据无法全量载入内存,需分治、分桶计数或外部排序
  2. 按高位分桶统计计数,累加定位中位数所在桶,再对该桶按低位二次计数
  3. 有符号数需处理符号位,偶数个数时取中间两个数
  4. 流式近似可用 t-digest、GK、KLL 等分位数草图,内存可控且可合并
  5. 也可用蓄水池采样得到随机样本再求中位数,精度依赖样本量

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题