题目重点：完整 OOD 接口来自题目；用动态数组和 ID→下标映射实现增删及均匀取样，解释末尾交换不变量。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- ID 唯一；重复 add 返回 false、缺失 remove 返回 false；空集 pick 返回 -1，按题目接口。
- 随机源可等概率生成 [0,n) 整数，O(1) 指期望时间与动态数组均摊追加，不保证强密码学随机。
解题路线
- 用 ids 动态数组存现有参与者，用 position[id] 记录其下标；保持两个结构双向一致。
- 新增时先查映射，若不存在将 ID 追加并记录尾下标。
- 删除任意 ID 时取其位置，将数组末尾 ID 换到空位并更新该末尾 ID 的映射，再 pop；若删的本来就是末尾，无需覆盖。
- 抽取时均匀选择 [0,len(ids)) 下标；末尾交换改变顺序，不改变每个 ID 恰有一个下标，因此每人概率 1/n。并发版需在同一锁/事务内维护数组与映射。
手动走一遍
ids=[7,9,4]，删除 9：用末尾 4 覆盖下标 1，pop 后 ids=[7,4]，position[4]=1 并删 position[9]。现在 pick 的两个下标分别对应 7、4，各 1/2。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from random import randrange
class LotterySystem:
def __init__(self, pick_index=randrange):
self.ids = []
self.position = {}
self.pick_index = pick_index
def addParticipant(self, participant_id):
if participant_id in self.position:
return False
self.position[participant_id] = len(self.ids)
self.ids.append(participant_id)
return True
def removeParticipant(self, participant_id):
index = self.position.pop(participant_id, None)
if index is None:
return False
last = self.ids.pop()
if index < len(self.ids):
self.ids[index] = last
self.position[last] = index
return True
def randomPick(self):
if not self.ids:
return -1
return self.ids[self.pick_index(len(self.ids))]
复杂度
add/remove/pick 期望 O(1)，空间 O(n)；动态数组追加均摊 O(1)。若要求线程安全，锁竞争成本另算。
易错点与追问
容易失分的边界
- 数组中间直接删除导致 O(n) 位移。
- 末尾换入后忘记改 position。
- 空集调用随机数。
- 删除失败仍修改状态。
- 把伪随机均匀抽样说成安全随机。
继续深挖
- 若抽取后自动移除赢家怎么办？
- 按权重抽奖还能三操作都 O(1) 吗？
- 多线程并发增删如何保持不变量？
- 如何做可重复测试的随机源注入？
