面试题库 › C++ / 后端 › 乱序数据中求90分位值(P90)

乱序数据中求90分位值(P90)

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

哪些公司问过

阿里巴巴1

常见岗位:C/C++ 软件开发

答案要点

  1. 约定分位定义,如取第 ceil(0.9n) 小的元素
  2. 排序 O(n log n);快速选择平均 O(n),可用 nth_element
  3. 小顶堆保存最大的约 10% 元素,堆顶即 P90,O(n log(n/10))
  4. 值域有限时分桶计数,累计到 90% 即为答案,适合海量或流式
  5. 允许近似时可用 t-digest 等分位数草图

易错点

面试官常见追问

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

相关面试题