题目重点：从某个 percentile 的精确秩出发，比较两堆、磁盘归并和 quantile sketch。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练 p∈(0,1]，nearest-rank为第 ceil(pN)小，重复值各计；其他插值定义需另约。
- 要求逐次实时结果还是处理完整有限文件后查询会改变方案；“落盘”不能自动给实时常数延迟。
解题路线
- 先问精确/近似、p是否固定、数据量N是否已知、能否重放、更新频率与磁盘预算。不同分位数定义可能在同一数据上给不同结果。
- 内存精确可维护两部分，较小部分大小ceil(pN)，其最大值就是目标秩；每次新增N变化时调整目标大小，保存全部样本仍需 O(N) 内存。
- 有限文件超内存时切为可内存排序的 runs 落盘，k路归并推进到目标秩。需要总N或先统计一遍；合并还包括文件句柄、缓冲与临时盘容量。
- 若需要无界流、有限内存、低延迟，讨论允许秩误差的 sketch。不能既声称完整精确又只保留固定小摘要；值域有界的精确频表是另一条件。
手动走一遍
[1,2,3,100]，p=.75 nearest-rank取第3项3；插值定义可能不一样。外存每run可装M项，分R个run；堆保存各run当前项，弹出到第ceil(.75N)项，重复值不能跳过。
规模与取舍
run排序约 O(N log M)，R路合并推进r项 O(r log R)，堆 O(R)加缓冲；大量run需多趟归并，I/O成本与块大小/扇入关联。两堆精确仍 O(N) 内存。
易错点与追问
容易失分的边界
- 不确认 percentile 定义。
- 只提 merge k lists 没有runs生成和N。
- 无限精确流承诺固定内存。
继续深挖
- 多个p查询怎样复用外排序？
- 秩误差与数值误差为何不同？
