题目重点：先统计频次再选K项，固定并列口径，区别元素大小 Top K 与超大日志聚合。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练返回恰好k个不同值，合法k∈[0,u]；并列按首次出现顺序。
- 不是数值最大的K个。的网页点击日志并入本题；日志格式未给，训练按每条记录一次点击，若带聚合count则累加权重，需先确认schema。
解题路线
- Counter统计各值频次，上界为输入长度n，因此n+1桶可直接按freq放值，频率从高到低取够k项。并列用Counter首次插入顺序作为训练政策。
- 频次f的桶高于所有频次更低的桶，扫描保证任何选中项不劣于未选项；截断并列只实现指定tie规则，不意味着业务会这样定义。
- 频表大小u：全排序O(u log u)、大小k堆O(u log k)而非每种都泛写O(n log n)。桶版O(n+u)却需要O(n)桶，n远大于u时堆或排序更省。
- 持续流可用freq→值集合及值→freq双索引，并维护非空频桶链表进行+1移动。O(1)更新不等于O(1)输出TopK，输出k项至少Ω(k)，并列按最早顺序还需额外结构。
- 远程超大日志先固定文件版本/校验标识，流式读取或按完整记录边界拆chunk；确认HTTP Range支持，压缩格式是否支持随机解压，避免按任意字节切开UTF-8或记录。每chunk生成局部计数，按page key重新分区并求完整总计数，之后各key分区取局部TopK，再归并候选。最终每个page只能属于一个聚合分区，且所有阶段使用同一确定tie顺序。
手动走一遍
训练[4,1,4,2,1,3]、k=2输出[4,1]；频次相同按首次出现。k=0为空，k>不同值数量属于非法输入。随机记录分片反例：片1为X两次/A三次，片2为X两次/B三次；各取Top1只剩A、B，漏掉全局X四次。先按key汇总再局部选才不会漏。并行作业重试用(fileVersion,chunkId)幂等提交中间结果，不能重复累加同一chunk；原日志里的重复业务事件是否去重则需eventId合同，不能按文本一样直接删。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import Counter
def top_k_frequent(values,k):
"""Frequency descending, ties by first occurrence; k in [0, distinct_count]."""
counts=Counter(values)
if k < 0 or k > len(counts):
raise ValueError("invalid k")
if not k: return []
buckets=[[] for _ in range(len(values)+1)]
for value,count in counts.items(): buckets[count].append(value)
result=[]
for count in range(len(values),0,-1):
for value in buckets[count]:
result.append(value)
if len(result)==k: return result
return result
复杂度
桶版O(n)期望时间、O(n+u)辅助空间；当前输入批次界限n是桶边界，无限流不能预先开固定n桶。分布式精确聚合shuffle最坏传输O(n)记录或O(各chunk不同key数)局部计数，热点key可能倾斜；最终候选至多P·k，归并O(P·k log k)。
易错点与追问
容易失分的边界
- 把高频与大数混题。
- 声称输出TopK也常数时间。
- 记录随机分片仅合并局部TopK。
继续深挖
- 并列全返回时结果大小如何变？
- 滑动窗口含计数下降怎么维护？
- 只需近似热门项时怎样定义误差？
