题目重点：把整数人口映射为等大小 ticket 区间，用 bisect_right 精确选择并验证零权重边界。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 人口作为非负整数权重，所有人口总和必须为正；国家可重复命名但输出仅返回名字，若需要区分同名实体应引入唯一 ID。
- 固定权重可多次抽样；本文用均匀整数 ticket ∈[0,total)，避免浮点随机数刚好落在 total 时越界。
- 随机源 `randrange(total)` 按均匀整数抽取；测试注入确定性 ticket。密码学用途须另评估随机源。
解题路线
- 按输入顺序累加权重，prefix[i] 是前 i+1 个权重之和；第 i 个国家拥有整数区间 [prefix[i−1],prefix[i])，长度恰为其人口。
- 均匀抽 0..total−1 的 ticket，用 `bisect_right(prefix,ticket)` 找第一个严格大于 ticket 的前缀值，返回对应国家。
- 零权重会产生相同的前缀值，但不拥有任何 ticket；`bisect_right` 的严格大于规则自然跳过它。
- 用把每个国家名称按权重重复展开的独立参考桶，穷尽短输入的每个 ticket 核对归属。
手动走一遍
A:2、B:0、C:3 的前缀是 [2,2,5]。ticket 0/1 给 A；ticket 2/3/4 给 C；B 概率为 0。若误用 `bisect_left`，ticket=2 会错落到 A 或零权重 B 的边界。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from bisect import bisect_right
from collections.abc import Callable
from random import randrange
class WeightedCountrySampler:
def __init__(self, countries: list[tuple[str, int]]):
if not countries:
raise ValueError("at least one country is required")
self.names: list[str] = []
self.prefix: list[int] = []
total = 0
for name, population in countries:
if population < 0:
raise ValueError("population must be non-negative")
total += population
self.names.append(name)
self.prefix.append(total)
if total == 0:
raise ValueError("at least one population must be positive")
self.total = total
def sample(self, draw: Callable[[int], int] = randrange) -> str:
ticket = draw(self.total) # Uniform integer in [0, total).
if ticket < 0 or ticket >= self.total:
raise ValueError("draw must return a ticket inside [0, total)")
return self.names[bisect_right(self.prefix, ticket)]
复杂度
预处理 O(n) 时间与空间，单次抽样 O(log n) 时间、O(1) 额外空间。若权重频繁修改，前缀数组每次更新需 O(n)，可改 Fenwick 树或线段树达 O(log n) 更新/抽样。
易错点与追问
容易失分的边界
- 随机数取闭区间 [0,total]，total 无对应国家。
- 零权重项与重复前缀使用错误二分方向。
- 没有拒绝负人口或总权重为零。
- 用有偏 `random()%total` 代替均匀整数源。
- 把动态更新仍说成前缀数组 O(log n) 更新。
继续深挖
- 有千万个国家但只抽一次时，预处理是否值得？
- 权重动态增减时如何用 Fenwick binary lifting 抽样？
- 如何支持无法放进固定宽度整数的总人口？
- 如何用统计测试发现随机源或区间映射偏差？
