题目重点：排名按频次，随机概率按count/总count，二者不是均匀选key。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 题目只给hashmap频率排序/随机追问方向，训练采用静态item→非负整数count。
- randbelow(total)须均匀产生0..total−1整数；并列排名保留输入插入顺序。
解题路线
- 对正频项建立严格递增prefix累计和。随机整数r落入哪个半开频次区间就返回哪item，bisect_right(prefix,r)处理端点。
- 某项区间长度正好count，因此概率count/total。零频项剔除，空mass拒绝；不以random%total默认均匀，随机源必须保证无模偏差。
- 排序独立按count降序和稳定tie；动态增删频次可用Fenwick更新/按累计次数找rank，静态prefix更新则要重建后续值。
手动走一遍
频次A2、B3，对r0/1返回A，r2/3/4返回B，概率2/5与3/5。r恰2应B，bisect_left会在此边界误给A。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from bisect import bisect_right
class FrequencyTable:
def __init__(self,frequencies):
self.items=[];self.prefix=[];total=0
for item,count in frequencies.items():
if type(count) is not int or count<0:raise ValueError("nonnegative integer counts required")
if count:
total+=count;self.items.append(item);self.prefix.append(total)
self.total=total
def sample(self,randbelow):
if not self.total:raise ValueError("empty frequency mass")
r=randbelow(self.total)
if type(r) is not int or not 0<=r<self.total:raise ValueError("invalid random source")
return self.items[bisect_right(self.prefix,r)]
def ranked(self):
counts=[self.prefix[0]]+[self.prefix[i]-self.prefix[i-1] for i in range(1,len(self.prefix))] if self.prefix else []
return [self.items[i] for i in sorted(range(len(self.items)),key=lambda i:(-counts[i],i))]
复杂度
建prefix O(d)，sample O(logd)，rank O(dlogd)，空间O(d)；频次数值大但不展开。
易错点与追问
容易失分的边界
- 按key等概率抽样忽略频率。
- 浮点累计概率在巨大计数下丢失小项，整数区间更易精确验证。
继续深挖
- 动态更新怎么使用Fenwick的prefix selection？
- 无放回加权抽样时每次取后是否清零、概率合同怎样变化？
