LinkedIn Top K Search Words 系统设计：时间窗、精确计数与近似方案

题目重点：区分搜索 query 事件聚合与文章词频算法，设计去重、分区、窗口 Top K 和热点词处理。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

训练口径把每次搜索提交视为一条事件 (event_id, user_id, query, event_time)；将规范化完整 query 当一个词条，不拆成单词。若真实题要分词或唯一用户数，计数模型必须改变。
请求查询最近 1 小时/24 小时 Top K；允许秒级最终一致和少量迟到事件，精确计数是默认目标。题目未明确这些数字。

入口为事件附唯一 ID、事件时间和 schema 版本；消息队列按规范化 query 或稳定 hash 分区。消费者在 TTL 内按 event_id 去重，避免 at-least-once 投递把热词重复计数。迟到策略应写清楚：窗口关闭前修正，之后补偿或标水位。
按事件时间把每个 query 的计数写入分钟桶，再在查询时合并目标窗口桶；固定 1 小时可持续维护滑动窗口汇总，但窗口边缘若要任意秒级精确值，分钟桶不足以精确回答，需保留更细事件或定向扫描边界。
分区内维护局部候选 Top K，中央合并候选并查精确全局计数。不能盲目只把每个分区的局部 Top K 合并：若同一 query 分散在所有分区，可能每处都排在 K 以外却全局第一。按 query key 分区可让每个 query 的计数归一处；若一个超级热词要拆盐，中央必须合并所有盐份额并建立可证明足够的候选上界，或接受近似。
读层提供 (window_end, k, normalization_version, watermark) 的版本化结果缓存；排行榜更新用增量候选或定期全量计算并以快照替换。私人/敏感 query 做过滤和最低频阈值，不能把原始搜索词无条件公开。
若吞吐太高且允许误差，可按分片用 Space-Saving/Count-Min Sketch 产生候选，再做精确计数复核；说明误差界、重词召回和短窗口重置，避免把近似值冒充精确排名。

分钟桶 10:00 有 `data engineer` 4 次、10:01 有 3 次，窗口 [10:00,10:02) 的计数为 7。若其中一条 event_id 重放，去重后仍是 7；10:02 的事件不在该半开窗口。多个用户搜同词按事件计 7 次，而按唯一用户数可能不同。

E 条事件、U 个窗口内不同 query、B 个时间桶：写入平均 O(1) 状态更新，桶状态最坏 O(U·B)；精确 Top K 快照对 U 个计数堆选为 O(U log K)，窗口查询若每次跨 B 桶现算则 O(U·B)。预聚合和增量更新以存储、迟到修正换查询延迟。