题目重点：用随机可播池和冷却队列实现均摊常数时间，证明候选集合及均匀性，处理重复歌曲与曲库不足。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练合同每一步在当前合法的不同song_id中均匀选择，输入重复song_id只算同一首。若同歌不同版本应不同id，不按显示歌名误合并。
- 冷却N表示之后N次播放均不选该歌，不是两次播放下标差≥N。无限持续播放需独立歌曲数M>N；不满足时构造抛错，正式失败格式待核。
- 随机源能生成[0,available_count)的均匀整数；不把整个播放历史宣称为所有合法长序列的等概率抽样。
解题路线
- 初始化去重，available数组保存当前可播歌曲，recent队列保存最后最多N首。所有歌曲恰好位于一处，两集合不相交且并集是曲库。
- play均匀抽一个available下标；取该歌曲后用数组最后一首覆盖被取下标，再pop。这个swap删除只改池内顺序，不改变合法集合，每个歌曲对应一个下标，故抽样仍均匀。
- 把刚播放歌曲追加recent；若队列长度>N，最老歌曲已经经历N次后续抽样，出队追加available。释放发生在本次抽样之后，保证它没提前参加第N次抽样。
- N=0时刚播歌曲立即回池，下次可重复。M=N+1时经过初始阶段后每次只有一首可选，会成为循环；这符合合同，不能为了看起来更随机而破坏冷却。
- 如需动态增删歌曲，增加位置索引与禁用标记；处于冷却的歌曲删除后释放时不能重新加入。并发play必须把抽样、swap、队列更新放同一临界区，否则可能选同歌。
手动走一遍
训练例A/B/C、N=1。播A后池为B/C，第二次只能B或C；若第二次播B，之后释放A，第三次候选A/C。若第二次抽样前释放A，就会允许A连播，违反接下来一首不得重复。N=2且曲库仅两首则第三次没有合法歌曲，不能无限播放。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
import random
class Playlist:
def __init__(self, song_ids, cooldown: int, choose_index=None):
if cooldown < 0:
raise ValueError("cooldown must be nonnegative")
self.available = list(dict.fromkeys(song_ids))
if len(self.available) <= cooldown:
raise ValueError("indefinite playback requires more unique songs than cooldown")
self.cooldown = cooldown
self.recent = deque()
self.choose_index = choose_index or random.randrange
def play(self):
index = self.choose_index(len(self.available))
if not 0 <= index < len(self.available):
raise ValueError("invalid random index")
song = self.available[index]
self.available[index] = self.available[-1]
self.available.pop()
self.recent.append(song)
if len(self.recent) > self.cooldown:
self.available.append(self.recent.popleft())
return song
复杂度
初始化O(M)，每次随机下标、swap、入/出队均摊O(1)，空间O(M)。独立状态验证枚举M=1..5、合法N下六次播放的39,027个可达状态，按历史后缀直接计算合法集，核对所有可选输出与池；另检查4个非法输入。均匀性由每个合法歌一一对应均匀下标证明，频率抽样测试不能替代这个证明。
易错点与追问
容易失分的边界
- 冷却释放提前一轮，出现off-by-one。
- 重复歌曲保留多个槽位，既放大概率又可违规重复。
- 随机拒绝法在M接近N时耗时无上界，却声称每次O(1)。
- 从set转list每次抽样，仍花O(M)。
- M≤N时死循环寻找合法歌。
继续深挖
- 歌曲有权重时，swap数组怎样换成动态加权抽样？
- 用户删除冷却中的歌曲，如何更新状态？
- 要求同一艺人也冷却，会引入哪些新的不可行情形？
- 如何让随机种子复现事故但不影响生产随机源？
