题目重点：按用户最近 K 条观看历史形成集合，分组同集合用户，再找电影交集至少 M 的用户对，区分顺序、重复电影与候选剪枝。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 历史按观看先后排列，取最后 K 条记录后转集合；同一电影在最后 K 条内重复只计一个电影。题目写最后 K 部电影，若指 K 个不同片名需另定。
- 历史不足 K 条的用户在训练版不参与比较；K=0 时所有用户都是空集合。用户 id 可排序以稳定输出。
- 按集合交集大小≥M 判断 pair；M=0 返回所有合格用户对。题目未明确是否只返回最大连通群，本文按 pair 字面要求。
解题路线
- 先对每名用户切取最后 K 条，转 frozenset 作为稳定哈希键。相同集合分组可用 `map[frozenset]→users`，只输出人数至少 2 的组。
- 追问从两两用户对的集合交集基线出发；因为‘重叠至少 M’不具传递性，不能把边连成连通分量后当作同组。
- 若用户数 U 很大，给每部电影建倒排索引，仅枚举共享电影的候选用户对并累积交集计数；M=0 仍可能有 Θ(U²) 输出，因此没有普遍次二次最坏时间。热点电影需要压缩 posting、分片或分层过滤。
手动走一遍
训练例 A 最近两条 [X,Y]、B [Y,X]、C [X,Z]。A/B 属于同集合组；M=1 时 A-B、A-C、B-C 都是合格 pair；M=2 时只有 A-B。若 A 最近两条是 [X,X]，其集合大小为 1，不等于 [X,Y]。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import defaultdict
from itertools import combinations
def group_same_last_k(histories, k):
if k < 0:
raise ValueError("k must be nonnegative")
groups = defaultdict(list)
for user, movies in histories.items():
if len(movies) < k:
continue
key = frozenset(movies[-k:] if k else ())
groups[key].append(user)
return [sorted(users) for users in groups.values() if len(users) > 1]
def pairs_with_at_least_m_overlap(histories, k, m):
if k < 0 or m < 0:
raise ValueError("k and m must be nonnegative")
users = sorted(user for user, movies in histories.items() if len(movies) >= k)
recent = {user: set(histories[user][-k:] if k else ()) for user in users}
return [(left, right) for left, right in combinations(users, 2)
if len(recent[left] & recent[right]) >= m]
复杂度
取历史尾部与构建集合总计 O(UK)；同集合分组预期 O(UK) 时间和空间。两两 pair 基线 O(U²K) 时间、O(UK+P) 空间，P 为输出 pair 数；倒排候选可在稀疏数据上更快，但热门电影仍可能产生二次候选。
易错点与追问
容易失分的边界
- 把最近 K 条按顺序 tuple 比较，违背‘集合相同’。
- 先对全部历史去重再取 K，改变最后 K 的语义。
- 把 M 重叠关系当等价关系做并查集，错误扩大分组。
- 忘记同一电影在近期重复时集合大小会小于 K。
- 未考虑输出本身可能有 O(U²) 对。
继续深挖
- 如果要求最近 K 个不同片名，要怎样从尾部扫描？
- 数据流新增观看事件时如何增量更新分组键？
- 热门电影造成倒排组合爆炸时如何先做稀疏过滤或分布式聚合？
