题目重点：用用户×文章当前态防重复，分数差量更新；区分‘最近三次投票’与‘最近三次改变意见’的题目变体。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版以用户×文章保存当前 -1/0/+1 状态；同方向重复为 no-op，反向投票记一个 flip event；top K 按净赞成票 `up−down` 降序，同分 article_id 升序。
- `get_most_recent_3_flip_article` 训练版返回最近三次翻转事件的 article_id，允许同一篇文章重复出现；原文‘最近三篇改变想法的 article’是否要求去重未公开。 的最近三次所有有效投票应另设接口和事件日志，不能与 flip 查询合并。
解题路线
- add_article 产生稳定 article_id 与零分；`vote[(article,user)]` 记用户当前态。新投票由 0→±1，分数加 ±1；同态重复不改分/历史；翻转 +1→−1 的分数差为 −2，反向为 +2。
- 仅在旧态非零且方向变化时，把 article_id 放进该用户长度 3 的 flip 队列头部；若还要‘最近三次有效投票’，需另建全事件日志，两种查询不能混用。
- top K 训练版排序所有文章 O(A log A)；若高频查询可用分数有序索引，但每次投票要同步删除旧分数键并插入新键。排序平局必须稳定，文章删除/隐藏需要定义是否仍在榜。
- 并发实现用用户×文章状态的事务/CAS 及分数变更同一原子边界；否则两次并发 upvote 可能重复加分。本文代码仅单进程，不声称生产并发安全。
手动走一遍
文章 7：用户 2 首次 up，分数 +1；再次 up 不变；改 down，分数从 +1 到 −1（delta−2）且 flip 队列加入 7；再次 down 不变；再改 up，分数回 +1 且队列再加入 7。最近三次 flip event 可出现 [7,7]。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import defaultdict, deque
class ArticleVoting:
"""Training contract: last three flip events; tie by smaller article ID."""
def __init__(self) -> None:
self.next_id = 1
self.names: dict[int, str] = {}
self.vote: dict[tuple[int, int], int] = {}
self.score: dict[int, int] = {}
self.flips: dict[int, deque[int]] = defaultdict(lambda: deque(maxlen=3))
def add_article(self, name: str) -> int:
article_id = self.next_id
self.next_id += 1
self.names[article_id] = name
self.score[article_id] = 0
return article_id
def up_vote_article(self, article_id: int, user_id: int) -> None:
self._set_vote(article_id, user_id, 1)
def down_vote_article(self, article_id: int, user_id: int) -> None:
self._set_vote(article_id, user_id, -1)
def _set_vote(self, article_id: int, user_id: int, value: int) -> None:
if article_id not in self.names:
raise KeyError(article_id)
key = (article_id, user_id)
previous = self.vote.get(key, 0)
if previous == value:
return
self.vote[key] = value
self.score[article_id] += value - previous
if previous != 0:
self.flips[user_id].appendleft(article_id)
def get_most_recent_3_flip_article(self, user_id: int) -> list[int]:
return list(self.flips[user_id])
def get_top_k(self, k: int) -> list[int]:
if k < 0:
raise ValueError("negative k")
return sorted(self.names, key=lambda article: (-self.score[article], article))[:k]
复杂度
单次投票哈希映射平均 O(1)，最近三次翻转 O(1) 输出上限三项；当前 top K 全排序 O(A log A)、空间 O(A)，状态空间 O(不同用户文章投票对数)。有序榜索引可使更新 O(log A)、查询 O(K+log A)。
易错点与追问
容易失分的边界
- 同方向重复 up 仍加分。
- 从 up 改 down 只减 1，漏掉撤销旧 +1。
- 把最近三次有效投票误作最近三次 flip。
- 不说明 flip article 是否去重。
- 并发投票时状态与分数分两次非原子更新。
继续深挖
- 如果撤销投票回到中立，算不算 flip？
- 最近三篇不同文章如何维护？
- 榜单要按近 24h 而非全历史分数怎么改？
- 同用户跨设备同时反向投票怎样保证一次有效状态转移？
