1. 题目
广告系统有 N 个候选项，每个选项的权重表示被抽中的相对概率。初始化后会执行数百万次单项采样，要求每次采样尽量为 O(1)，并允许权重批量更新。请设计并实现 alias table，说明零权重、浮点误差和随机数边界。
2. 约束与澄清
- 先讨论有放回的单项采样；不放回抽样和动态单项更新是延伸。
- 权重必须非负且总和大于零；零权重选项不应被采到。
- 采样器可以使用均匀随机整数和
[0, 1)的均匀随机数。 - 权重变化后可以接受
O(N)重建，但不能假装旧表仍代表新分布。
3. 核心思路
把每个权重归一化为 pi = wi * N / sum(w)，平均值为 1。维护长度为 N 的 prob 和 alias 数组：每个桶先以概率 prob[i] 返回自身，否则跳转到 alias[i]。预处理时将小于 1 的桶放入 small，大于 1 的桶放入 large；从两边取出一对，把大桶剩余容量填入小桶，直到所有桶完成。
采样先均匀选桶 i，再用一次均匀小数与 prob[i] 比较。每个原始选项在若干桶中占据的面积总和等于其归一化概率，因此长期频率与目标权重成比例。
4. 参考实现
build(weights):
n = len(weights)
scale = n / sum(weights)
scaled = [w * scale for w in weights]
prob = array(n)
alias = array(n)
small, large = [], []
for i, value in enumerate(scaled):
(small if value < 1 else large).append(i)
while small and large:
s = small.pop()
l = large.pop()
prob[s] = scaled[s]
alias[s] = l
scaled[l] -= 1 - scaled[s]
(small if scaled[l] < 1 else large).append(l)
for i in small + large:
prob[i] = 1
alias[i] = i
return prob, alias
sample(prob, alias, rng):
i = rng.uniform_int(0, len(prob))
return i if rng.uniform01() < prob[i] else alias[i]5. 复杂度与正确性
预处理时间和空间都是 O(N)；每次采样只需一次均匀桶选择、一次比较和最多一次数组访问，时间为 O(1)。prob 应被限制在 [0, 1]，剩余浮点误差可在构建结束时钳位；随机整数上界必须明确为半开区间，避免最后一个桶被遗漏。
验证不能只抽几次看结果。应运行足够样本，比较每个选项的观测频率与目标 w_i / sum(w)，使用置信区间或卡方检验发现明显偏差。重建时要原子替换整张表，避免采样线程看到混合版本。
6. 追问与陷阱
- Alias Method 适合静态或批量更新分布；单个权重频繁变化时，Fenwick tree 或 segment tree 可能更合适。
- 归一化前总权重溢出会破坏比例，应使用更宽精度或先缩放。
- “O(1)”不包括重建成本，也不代表随机数生成器本身没有开销。
- 非负权重总和为零时分布未定义，应拒绝输入，而不是平均返回所有选项。
7. 延伸阅读
可以比较前缀和二分、Fenwick tree、reservoir sampling 和 alias table：前缀结构支持动态更新但采样为 O(log N)，reservoir 适合流式样本，alias table 则以 O(N) 预处理换取高吞吐 O(1) 采样。
8. 面试评分点
能构造 small/large 桶
应说明缩放权重、平均容量为 1，以及如何用小桶和大桶互相填充容量。
能证明采样概率
应解释“均匀选桶加一次别名跳转”如何让每个选项获得目标总面积，而不是只背代码。
能处理数值和边界
应覆盖零权重、总和为零、浮点钳位、随机整数半开区间和表版本原子替换。
能判断数据结构取舍
应比较批量重建与动态更新成本，说明何时选 Fenwick tree 或前缀和，而非盲目使用 alias table。