题目重点：返回频次最高的K项，讨论高频读取与高频更新下的计算、缓存和有序索引。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练可比较hashable值、准确频次，返回(value,count)，频次降序/值升序；K非负，更新delta可负但总count不能负。零计数删除。
- 代码是frequency map+lazy cached全排序baseline，不假称实现了每次update O(logD)的有序索引。
解题路线
- 静态数组先计count，再对D不同值排序，取K。更新频次O(1)平均并使cached无效；首次top重新排序，之后未变更的读仅拷K项。
- Read-heavy且写少，缓存摊销大量重复排序；写后一个cache generation即可，若有并发需版本/锁防旧重算覆盖新状态。
- Write-heavy且读少，计数map便宜，查询按需heap TopK O(D logK)或排序，避免每写维护复杂全序。Read和write都多时可用按(-count,value)有序结构更新O(logD)并TopK O(K)，但实现和锁成本提高。
- 只保存K项的heap对减少计数/删除会缺替补，不能精确维护动态TopK；需完整候选索引或查询重扫。lazy heap过期项需要generation校验及空间回收。
- TopK返回的是值和频次，不是数组原始位置；重复出现按计数合并，若要index结果必须另定映射。
手动走一遍
a3、b2，top1为a；把a减2成1后top1必须b，旧缓存不能继续返回a。count负数更新拒绝，原状态保留；并列a/b都2按a先。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class FrequentValues:
"""Comparable hashable values, exact counts; cached full order after writes.
top(k)->(value,count), tie value ascending; cache invalidated by any update.
"""
def __init__(self):self.counts={};self.cached=None
def update(self,value,delta=1):
count=self.counts.get(value,0)+delta
if count<0:raise ValueError('negative count')
if count:self.counts[value]=count
else:self.counts.pop(value,None)
self.cached=None
def top(self,k):
if k<0:raise ValueError('nonnegative k')
if self.cached is None:self.cached=sorted(self.counts.items(),key=lambda p:(-p[1],p[0]))
return self.cached[:k]
def top_frequent(values,k):
counter=FrequentValues()
for value in values:counter.update(value)
return counter.top(k)
复杂度
update平均O(1)，D不同值，cache miss排序O(D logD)，cache hit top O(min(K,D))输出，状态O(D)。频繁写读交替几乎每次排序，不能仅凭有缓存就标查询常数。
易错点与追问
容易失分的边界
- 减频/删除未失效缓存。
- 只有K候选的heap无法在旧冠军下降后找到全局替补。
- 把hash更新O(1)与有序索引更新O(logD)混说。
继续深挖
- 过期窗口词频如何加入减贡献，并与缓存版本同步？
- 如果K经常变化，缓存全排序与只缓存固定TopK的空间/重算区别？
