Netflix 音乐 Playlist：Add、Remove 与均匀 Shuffle

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版 track ID 唯一，重复 add 返回 False，remove 不存在返回 False；题目未明确重复歌曲是否允许。
• shuffle 返回新顺序，不修改 playlist 的原始排列；题目未说原地还是副本。
• 随机源提供 `randrange(n)`，生产默认独立 PRNG；测试可注入固定伪随机源，避免概率性测试不稳定。

解题路线

1. 有序数组保存曲目顺序，id→index 映射让重复检测 O(1)。remove 删除数组位置后重建后续索引，最坏 O(n)；若允许改变原顺序，可用尾部交换做到 O(1) 删除，但那会改变 playlist 语义。
2. shuffle 在副本上用 Fisher–Yates：从末尾 i 到 1，均匀选 j∈[0,i] 交换。只要每次选择独立均匀，n! 个排列等概率；不能每个元素任意选位置而不考虑重复/偏差。
3. 测试空表、单曲、重复 add、删除首/中/尾、shuffle 之后原表不变、输出恰好是同一批 ID。随机均匀性可用小 n 的统计检验辅助，单次运行不能证明均匀。

手动走一遍

训练例 add A、B、C 后删除 B，原序列为 [A,C]。注入的随机源若在 i=1 选 j=0，shuffle 返回 [C,A]，而 tracks() 仍是 [A,C]；再次 add B 放到末尾，返回 [A,C,B]。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from random import Random


class Playlist:
    """Unique track IDs; shuffle returns a new randomized order."""

    def __init__(self, tracks=()):
        self._tracks = []
        self._positions = {}
        for track in tracks:
            self.add(track)

    def add(self, track):
        if track in self._positions:
            return False
        self._positions[track] = len(self._tracks)
        self._tracks.append(track)
        return True

    def remove(self, track):
        if track not in self._positions:
            return False
        index = self._positions.pop(track)
        self._tracks.pop(index)
        for position in range(index, len(self._tracks)):
            self._positions[self._tracks[position]] = position
        return True

    def tracks(self):
        return list(self._tracks)

    def shuffle(self, rng=None):
        random = rng if rng is not None else Random()
        order = self._tracks.copy()
        for index in range(len(order) - 1, 0, -1):
            other = random.randrange(index + 1)
            order[index], order[other] = order[other], order[index]
        return order

复杂度

add 预期 O(1)，remove 最坏 O(n)（维护顺序与位置索引），tracks 和 shuffle O(n) 时间/空间。若需要 O(1) remove 且不在意顺序，可交换待删元素与尾元素；若要支持大量按位置插入，还需别的数据结构。

易错点与追问

容易失分的边界

• 不问重复歌曲是否允许，就把 ID set 当完整播放列表。
• remove 后忘记更新后续元素索引。
• shuffle 用随机 key 排序，遇碰撞或排序稳定性会改变分布。
• 只验证 shuffle 长度，不验证元素多重集和原列表状态。
• 把随机测试设为每次必须输出某个特定顺序。

继续深挖

• 若同一歌曲可以加入两次，id→index 如何改？
• 需要原地 shuffle 与 undo shuffle 时保存什么？
• 百万曲目且每次只取下一个随机不重复曲目，是否需要整表拷贝？