题目重点：Onsite 先问 kth element，再追问高流量每窗第 k 值；把时间窗口和范围桶的精确性条件分清。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版求最近 W 秒的第 k 小，事件为 (timestamp,value)，按 timestamp 非递减到达，窗口 (now−W,now]，k 从 1 起；若不足 k 项返回无结果。
- 训练版整数 value 落在已知有限范围 [L,R]，可用每个精确值一个频次桶；若只按粗范围桶，必须在命中桶内有额外结构才能给精确 kth。
- queue 必须至少保留窗口中每个事件的 (timestamp,value) 才能到期时减相应频次；若事件量本身超过内存预算，需外存/近似或改变要求。
解题路线
- 每到新事件，先从队首弹出 timestamp≤now−W 的事件并对相应 value 频次减 1；再将新事件入队并加频次。维持 total 当前数量。
- 查询第 k 小时扫描值域累计频次，首个累计≥k 的值即答案；范围大且查询多时用 Fenwick/segment tree 维护计数前缀和并做 order-statistic search。
- 若只做固定粗 bucket，先按桶累计定位目标桶，再用该桶内 exact subcount/有序结构找精确值；只保存总桶计数不足以区分同桶值。
- 大时间窗高 QPS 的队列内存为 O(M)，M 是窗内事件数；若预算小于 M 且值/时间任意，不能保证对所有滑窗精确过期。需澄清是否允许固定 tumbling window、外部日志或误差。
- 先把离线 kth（排序或 quickselect）与持续滑窗 kth 区分，复杂度和删除需求不同；向面试官确认第 k 大/小与同值处理。
手动走一遍
训练例 W=10，事件 (1,4),(2,1),(9,4)，now=9 时窗有 [4,1,4]，第 2 小为 4。到 (12,2) 时先过期 t≤2 的两项，剩 (9,4),(12,2)，第 2 小仍为 4。若误用 [now−W,now] 闭左边，t=2 会被多留。
规模与取舍
M 条窗内事件、值域宽 D=R−L+1：每事件入/出队摊还 O(1)，精确频次 O(D) 空间，线性查询 O(D)；Fenwick 更新 O(log D)、第 k 查询 O(log D)，总内存 O(M+D)。外存或压缩实现另算。
易错点与追问
容易失分的边界
- 未定窗口端点就写过期比较，边界事件多算。
- 只保留每个值的频次，不留事件时间，无法知道哪个值何时过期。
- 用粗范围桶的 count 直接输出精确 kth，桶内多个值时做不到。
- 声称固定小内存即可处理任意高流量精确滑窗，而未给额外存储或近似许可。
继续深挖
- 事件乱序/迟到时怎样处理？
- 第 k 大如何转成第 k 小？
- 值域未知或有浮点值时怎样维护 order statistic？
- 如果只需每分钟整窗结果，可否减少状态？
