题目重点：用整数票区间证明按权重抽样，明确过期边界与重复值规则，再比较线性扫描和 Fenwick 树的取舍。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 权重为正整数；每次add是一条独立贡献，相同value可有不同过期时间，抽到同value的概率是活跃贡献权重之和。
- 训练时钟now单调非递减，expiry=add_time+ttl，now≥expiry就失效，ttl=0立即失效；题目未明确边界。
- 没有活跃贡献时抛LookupError，正式接口待核；抽样与过期清理在同一个时间快照下。
解题路线
- 每条活跃entry占连续weight张票，total为总权重。均匀生成整数ticket∈[0,total)，从左到右扣权重直到落入某条区间；该entry恰好weight张票，故概率weight/total。
- 先给清晰线性实现：advance剔除过期entry，再add或draw。维护绝对expiry便于测试，测试注入clock与ticket，避免真实sleep或频率统计掩盖边界错误。
- 同value不直接覆盖旧entry，否则会错误改变旧贡献的TTL。若题目要求更新权重而非追加，改API为entry_id或明确聚合规则，不能擅自选择。
- 线性算法每次O(e)，题目强调维护性可先写正确基线。高更新/抽样量时给entry分槽，用Fenwick树存权重，抽样做前缀选择O(log e)，expiry最小堆按now弹出并清零权重。
- 过期堆若entry可更新须携generation，忽略陈旧expiry记录；抽样、total与清理必须原子，否则ticket上界和候选不一致。时间单位与系统墙钟跳变要明确，持续TTL宜用单调时间。
手动走一遍
题目权重1、1、3共5，票0给value1、票1给value2、票2..4给value5；加value3权重5后total10，各概率10%、10%、30%、50%。训练例value5在t=10失效，draw(10)必须先删除其3张票，不能按旧total抽到空区间。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
import random
class WeightedSampler:
def __init__(self, choose_ticket=None):
self.entries = []
self.now = float("-inf")
self.choose_ticket = choose_ticket or random.randrange
def advance(self, now):
if now < self.now:
raise ValueError("time must be nondecreasing")
self.now = now
self.entries = [(value, weight, expiry) for value, weight, expiry in self.entries
if expiry is None or now < expiry]
def add(self, value, weight, now, expire_after_ms=None):
if not isinstance(weight, int) or weight <= 0:
raise ValueError("positive integer weight required")
if expire_after_ms is not None and expire_after_ms < 0:
raise ValueError("nonnegative expiry required")
self.advance(now)
expiry = None if expire_after_ms is None else now + expire_after_ms
if expiry is None or now < expiry:
self.entries.append((value, weight, expiry))
def draw(self, now):
self.advance(now)
total = sum(weight for _, weight, _ in self.entries)
if total == 0:
raise LookupError("no active entries")
ticket = self.choose_ticket(total)
if not 0 <= ticket < total:
raise ValueError("invalid ticket")
for value, weight, _ in self.entries:
if ticket < weight:
return value
ticket -= weight
raise AssertionError("unreachable")
复杂度
示例add/draw各O(e)清理或扫描、O(e)空间；树+过期堆版本约O(log e)更新/抽样、过期一次O(log e)，单次批量过期仍可O(k log e)。41,201张票独立枚举核对活跃value的票数，覆盖重复值、ttl0、相同时间与边界。
易错点与追问
容易失分的边界
- 按value覆盖entry，失去独立TTL。
- ticket使用闭区间[0,total]多一张票。
- 权重先归一化浮点产生边界误差。
- 过期堆只删一条而不清理所有已到期项。
- 声称线性基线每次O(1)。
继续深挖
- 支持remove(entry_id)时索引与过期堆怎样协调？
- 权重允许实数时精度与抽样合同怎么定？
- 并发add/draw需要锁住哪些状态？
- 总权重溢出时如何检测？
