题目重点：题目明确按词返回热度前 K 且同一用户同词只计一次；本文实现去重索引、稳定并列顺序和窗口追问边界。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版事件为 (userId,query)；同一对无论出现几次，给该 query 的热度贡献都是 1。query 按原字符串比较，不做大小写、拼写或语言归一化。
- top_k(k) 按去重用户数降序、同分 query 字典序升序；k<0 报错。题目没有窗口要求，窗口只在追问讨论。
- 新增事件按调用顺序处理；若用户撤销历史，需另加删除语义。
解题路线
- 维护 query→set(userId)，每次 ingest 直接加入对应集合；重复用户自动不增长计数。
- top_k 读取每词 set 大小并按 (-count,query) 排序取前 K。若 query 种类极多且查询频繁，可另外维护可更新排序索引，但每次 ingest 必须先检查是否为新用户贡献。
- 若追加最近 W 时间窗口，必须为每个 (user,query) 保存窗口内事件次数：一次事件过期时，只有该 pair 的最后一条也过期才减少词热度；简单把原 set 中 user 删除会误算。
- 用原始事件历史在每一步重新构造 distinct pair 集合作为独立参考，覆盖重复、同分、k=0 与 k 大于词数。
手动走一遍
事件 (A,cat)、(A,cat)、(B,cat)、(A,dog) 后，cat 的热度是 2，dog 是 1，top 2 为 [(cat,2),(dog,1)]。若 B 再搜 cat，仍为 2；若 B 搜 dog，则两词同为 2，按训练并列规则 cat 在前。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Count each user at most once per query and return popular queries."""
from collections import defaultdict
class HotSearch:
def __init__(self):
self.users_by_query = defaultdict(set)
def ingest(self, user_id: str, query: str) -> None:
self.users_by_query[query].add(user_id)
def top_k(self, k: int) -> list[tuple[str, int]]:
if k < 0:
raise ValueError("k must be nonnegative")
return sorted(
((query, len(users)) for query, users in self.users_by_query.items()),
key=lambda item: (-item[1], item[0]),
)[:k]
复杂度
一次 ingest 在均匀哈希下期望 O(1) 时间；U 个不同 (user,query) pair 占 O(U) 空间。V 个不同 query 的 top_k 完整排序 O(V log V) 时间、O(V) 列表空间；若用 size K 堆可优化查询为 O(V log K)，但动态更新成本另计。
易错点与追问
容易失分的边界
- 对原始日志按 query COUNT(*)，同用户重复点击抬高热度。
- 维护全局 user set，导致用户搜不同词只被一个词计数。
- 声称原题要求滑动窗口；题目未明确时间条件。
- 窗口追问中一条重复事件过期就把 user 从 set 删除，漏掉仍在窗内的同 pair 事件。
- 同分时输出顺序不稳定，测试易摇摆。
继续深挖
- 最近 24 小时窗口内如何维护 pair 引用计数？
- 用户量太大、set 存储不下时如何在精确分片和近似去重间取舍？
- 多地区日志重复投递如何用事件 ID 去重？
- 查询词大小写和语言规范化应在何处定义？
