题目重点：题目给 0–999 桶、对照组和实验组及 20% 扩容示例；用可验证的确定性分配规则解释空桶优先与缩容再分配。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版先把百分比换算成整数目标桶数；输入各组互不相交且桶 ID 在 [0,U)，目标总数不超过 U。
- 尽量保留每组原桶；缩容时优先释放该组最大 ID。扩容先取原本从未分配的最小桶，再取其他组释放的最小桶。组处理顺序沿输入映射顺序。
- 题目未规定负载均衡、哈希流量映射或实际用户迁移；本文只实现桶集合重配，不能将其视为完整实验平台。
解题路线
- 扫描各组建立 owner 映射，拒绝重复归属和越界 ID；从 0…U−1 找原本未分配的桶。
- 先对所有超额组裁剪，再对短缺组补桶；必须先统一裁剪，否则前一组补桶时可能错过后面组释放的桶。
- 补桶先消耗原本未分配队列，然后消耗释放队列；两个队列都按 ID 升序，保证结果可重复。
- 校验每组输出大小等于目标、所有桶仍互斥、原组保留数量最大化；随机小 U 对照守恒和优先规则。
手动走一遍
U=1000，control=0–99、enabled1=100–199，两组目标各 200。原未分配桶从 200 开始；control 先拿 200–299，enabled1 再拿 300–399，与题目例子一致。若 control 目标降到 50 且 enabled1 升到 150，先释放 control 的 50–99，但 enabled1 仍先取原空桶 200–249。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Rebalance 0..999 buckets, preferring originally unallocated buckets."""
from collections import deque
def rebalance_buckets(groups: dict[str, set[int]], targets: dict[str, int], universe_size: int = 1000):
if set(groups) != set(targets) or any(not 0 <= count <= universe_size for count in targets.values()):
raise ValueError("invalid target groups")
if sum(targets.values()) > universe_size:
raise ValueError("target total exceeds universe")
owner = {}
current = {}
for name, buckets in groups.items():
current[name] = set(buckets)
for bucket in buckets:
if not 0 <= bucket < universe_size or bucket in owner:
raise ValueError("invalid or overlapping bucket")
owner[bucket] = name
never_assigned = deque(bucket for bucket in range(universe_size) if bucket not in owner)
released = []
for name in groups:
excess = len(current[name]) - targets[name]
if excess > 0:
for bucket in sorted(current[name], reverse=True)[:excess]:
current[name].remove(bucket)
released.append(bucket)
released = deque(sorted(released))
for name in groups:
need = targets[name] - len(current[name])
while need and never_assigned:
current[name].add(never_assigned.popleft())
need -= 1
while need and released:
current[name].add(released.popleft())
need -= 1
if need:
raise ValueError("not enough buckets")
return current
复杂度
设 U 为桶总数、G 为组数；扫描 O(U)，组内排序与释放桶排序最坏 O(U log U)，队列补桶 O(U)，空间 O(U+G)。当前题 U=1000，映射百分比到桶数还需先确认舍入规则。
易错点与追问
容易失分的边界
- 允许同一桶同时属于两组，线上流量会进多个实验分支。
- 直接清空所有组重分配，导致不必要的流量迁移。
- 把释放桶当成原空桶，违背先取未分配桶的题目要求。
- 各组独立取最小空桶，却未统一更新 owner，发生重复分配。
- 百分比不能整除桶总数时静默截断，导致目标总数和流量比例不一致。
继续深挖
- 若所有组目标总和大于 U，如何在接口层拒绝并解释？
- 若要求最小化用户实验组迁移，如何定义桶→用户哈希和跨版本迁移成本？
- 目标比例出现 33.3% 时，用最大余数法还是固定舍入？
- 高并发修改同一实验分配时如何做版本化原子发布与回滚？
