题目重点：把每面权重映射到不重叠的前缀区间，二分均匀随机阈值，处理零权重和概率和不为 1。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版输入非负权重，至少一个正值；即使和不为 1 也按总和归一化。面索引从 0 开始，半开区间 [0,total) 用均匀 u∈[0,1) 映射。
- 演示代码用 Fraction 精确表示十进制权重便于核对；生产可按精度/性能选浮点或整数权重，并使用适合场景的随机源。
解题路线
- 构建 prefix[i]=Σ_{j≤i} weight[j]，总和 W>0。取均匀 u∈[0,1)，令 t=uW，返回首个 prefix[i]>t 的下标（`bisect_right`）；零权重造成相同前缀，不会被返回。
- 正确性来自每个面的阈值区间长度恰好是该面权重，均匀 t 落入它的概率为 weight[i]/W。概率和不为 1 时无需逐项修改权重，只用 W 缩放阈值。
- 多次抽样且权重固定时预处理一次；若权重经常更新，普通前缀表修改 O(M)，可用 Fenwick/segment tree 支持 O(log M) 更新与按累计权重查找。
- 数据来自任意实数时需验证有限、非负与舍入；安全敏感抽签应选密码学随机源，面试普通模拟通常可用常规 PRNG。
手动走一遍
权重 [2,0,3]，前缀 [2,2,5]：u=0.1→t=0.5 抽面 0；u=0.4→t=2 抽面 2；面 1 权重 0 永不命中。概率为 2/5 与 3/5。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from bisect import bisect_right
from fractions import Fraction
from random import random
class WeightedDie:
def __init__(self, weights):
self.prefix = []
total = Fraction(0)
for value in weights:
weight = Fraction(str(value))
if weight < 0:
raise ValueError("negative weight")
total += weight
self.prefix.append(total)
if not self.prefix or total == 0:
raise ValueError("at least one positive face weight required")
self.total = total
def sample_from_unit(self, u):
"""Deterministic unit draw: 0 <= u < 1, faces numbered from 0."""
u = Fraction(str(u))
if not 0 <= u < 1:
raise ValueError("unit draw out of range")
return bisect_right(self.prefix, u * self.total)
def sample(self):
return self.sample_from_unit(random())
复杂度
预处理 O(M) 时间/空间；每次抽样 O(log M)。若只抽一次且无需保留前缀，线性扫 O(M) 更简单。训练代码 50,000 个随机权重/阈值组合与独立线性累积 oracle 对照通过。
易错点与追问
容易失分的边界
- 权重和不等于 1 就直接拒绝，忽略归一化追问。
- 二分用第一个≥阈值，零权重区间边界可能被抽中。
- 全零权重仍抽面 0。
- 每次采样重建前缀导致 O(M) 单次成本。
- 浮点累积误差或 NaN 没有验证。
继续深挖
- 如何证明每面概率正比于权重？
- 频繁更新一面权重时如何改数据结构？
- M 极大而只有少数非零面怎么办？
- 如何检验随机源是否均匀并复现测试？
