题目重点：题目给 (timestamp,key) 流、仅保存最近 m 条和两个查询；本文定义乱序/同时间/截断语义并做完整历史参考对照。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版按 timestamp 最大的 m 条事件保留；同 timestamp 时后到的事件较新。查询阈值使用 timestamp≤t。若面试官定义为最后到达的 m 条，保留结构应换为 FIFO。
- top_key_before(t) 只在当前保留的 m 条内统计 timestamp≤t 的事件，同频返回字典序最小 key；无匹配返回 None。m 可为 0。
- 乱序事件允许进入，但过旧事件可能插入后立刻被淘汰；题目未明确 watermark 或迟到容忍度。
解题路线
- 按 (timestamp,arrivalSequence) 维护有序的至多 m 条记录；插入后若超容量，删最早一条。sequence 让同时间事件的新旧次序明确。
- 查询指定时间前的不同 key 数，扫描保留记录中 timestamp≤t 的事件并建 set；最频繁 key 追问用 Counter，再以 (-count,key) 选稳定赢家。
- 目前写入 O(m) 的有序数组适合 m 适中且语义清晰；若 m 大且写多，可用小根堆 O(log m) 保留最新事件，但时间点查询仍可能需要 O(m) 扫描。若大量历史阈值查询，要重新评估‘只保留 m 条’能否满足需求。
- 用完整历史排序后截取最后 m 条作独立基线，随机乱序、同时间和查询阈值比较 75,000 次。
手动走一遍
m=3，依次收 (5,A)、(7,A)、(6,B)、(8,C) 后保留时间 6:B、7:A、8:C；查询 t=7 的 unique=2，top key 按同频字典序为 A。再收到迟到的 (4,D)，因它比当前最早的 6 更旧，加入后立即被淘汰。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Keep latest m events by timestamp; query unique and most frequent keys."""
from bisect import insort
from collections import Counter
class RecentEvents:
def __init__(self, capacity: int):
if capacity < 0:
raise ValueError("negative capacity")
self.capacity = capacity
self.events: list[tuple[int, int, str]] = []
self.next_sequence = 0
def ingest(self, timestamp: int, key: str) -> None:
insort(self.events, (timestamp, self.next_sequence, key))
self.next_sequence += 1
if len(self.events) > self.capacity:
self.events.pop(0)
def unique_before(self, timestamp: int) -> int:
return len({key for ts, _, key in self.events if ts <= timestamp})
def top_key_before(self, timestamp: int) -> str | None:
counts = Counter(key for ts, _, key in self.events if ts <= timestamp)
if not counts:
return None
return min(counts, key=lambda key: (-counts[key], key))
复杂度
有序数组插入及头部删除最坏 O(m) 时间，存储 O(m)。unique 查询 O(m) 时间、O(u) set 空间；top_key 查询 O(m) 时间与 O(u) Counter 空间，u 为匹配的不同 key 数。若换最小堆，写入可 O(log m)，但任意时间查询仍需扫描或额外索引。
易错点与追问
容易失分的边界
- 未确认最近是按事件时间还是到达顺序。
- 只存不同 key，丢掉同 key 重复次数，无法回答 Top Key 追问。
- 查询从完整历史而非当前保留 m 条计算，违反内存限制。
- 同 timestamp 的多个事件缺稳定取舍，测试结果随容器顺序变化。
- 把 timestamp<t 和 ≤t 混用。
继续深挖
- 若指定 timestamp 可以早于当前最老事件，如何声明查询可回答范围？
- 若 m 达百万且每秒高频查询，如何组织时间索引和可撤销计数？
- 迟到事件有 5 分钟容忍窗口时，按事件时间保留的策略如何改变？
- Top K 而非单个 Top Key 时怎样控制查询成本？
