题目与使用场景
实现 reset() 返回初始顺序，shuffle() 返回一个均匀随机排列。题目考察随机算法、原地交换、随机数边界和可测试性；抽样播放、随机抽签和测试夹具都可复用同一模式。
面试官考察什么
- 是否选择 Fisher–Yates，而不是反复交换两个随机位置。
- 是否让第
i次交换从未固定的区间取下标。 - 是否区分闭区间随机数与半开区间随机数，避免越界或偏差。
- 是否保存不可变的初始快照，让
reset()不受洗牌影响。 - 是否给出 O(n) 时间、O(1) 额外空间和均匀性的理由。
- 是否说明伪随机种子、空数组、重复元素和统计测试边界。
作答前的澄清问题
shuffle()应返回新数组，还是可以修改工作数组后返回它？reset()是否必须返回独立副本，防止调用方继续修改内部状态？- 随机源是可注入的伪随机生成器，还是系统安全随机源？
- 元素是否允许重复？重复值相同但位置不同是否仍视为不同排列？
- 是否需要并发调用安全、可复现种子或加密级不可预测性？
- 输入规模是否要求在线处理或只能使用常数额外空间？
30 秒回答框架
“我保存一份初始快照和一份工作数组。洗牌时从末尾向前遍历位置 i，在 [0, i] 取一个均匀下标 j，交换 a[i] 与 a[j]。每轮固定一个位置，剩余前缀继续处理，所以时间 O(n)、额外空间 O(1)。reset() 返回初始快照的副本；随机源可注入以便复现和统计测试。”
分步骤深入解答
步骤 1：隔离状态。 构造函数复制输入为 original 和 working；reset() 重新复制 original，避免调用方持有引用改变基准。
步骤 2：定义随机边界。 令 i 从 n - 1 递减到 1，使用半开 API randomInt(i + 1) 得到 0..i；若 API 是闭区间，则明确传入 0 和 i。
步骤 3：原地交换。 交换 working[i] 与 working[j]，位置 i 从此固定；不创建与输入同规模的临时数组。
步骤 4：说明均匀性。 第一个位置有 n 种等概率选择，第二个有 n-1 种，依次相乘得到 n! 个排列且概率相同。随机源必须在每个候选下标上等概率。
步骤 5：处理重复元素。 算法对元素位置均匀；若值重复，多个位置排列可能呈现相同值序列，不能把可见序列数量误当作位置排列数量。
步骤 6：实现 reset。 返回 original 的副本并将 working 恢复为副本；若允许直接暴露内部数组，后续 shuffle 会产生别名污染。
步骤 7：验证和复杂度。 用固定种子检查复现，用小数组枚举排列频数检查近似均匀，测试空数组和单元素。每次洗牌 O(n) 时间、O(1) 额外空间；保存快照本身占 O(n) 状态。
高质量示范回答
“我维护 original 与 working 两个数组。shuffle 对 i = n-1..1 调用均匀的 j ∈ [0,i]，交换两项；reset 返回 original 的副本并重建 working。反复交换两个任意随机位置会让前面的位置被重复改写，排列概率不均。Fisher–Yates 每轮只从尚未固定的前缀选择，因此所有位置排列等可能，运行时间 O(n)，除状态快照外不需要额外数组。随机源可注入，便于种子复现、统计测试和安全场景替换。”
常见错误
- 每轮都在
[0,n-1]取随机位置 → 后固定的位置会被再次改写 → 使用[0,i]。 - 生成
floor(random * i)→ 漏掉下标i→ 使用i + 1作为半开上界。 - 交换两个任意随机位置 n 次 → 不保证均匀排列 → 采用逐位固定的 Fisher–Yates。
- reset 返回同一内部引用 → 调用方会污染初始快照 → 返回副本并隔离状态。
- 把伪随机当作安全随机 → 可预测抽签结果 → 按威胁模型注入 CSPRNG。
追问及应对
追问 1：为什么从后往前也可以从前往后？
前向版本在位置 i 从 [i,n-1] 选取并固定 i，证明完全对称；关键是每轮只从未固定区间取样。
追问 2：如何证明均匀？
位置 n-1 有 n 个等概率选择，位置 n-2 有 n-1 个，以此类推；任一完整选择路径概率为 1/n!。
追问 3：如何测试随机性？
对小数组运行大量次，统计每个位置排列的频数并设置允许误差；同时用固定种子验证结果可复现，避免把一次样本当成证明。
追问 4：什么时候不能用普通伪随机？
抽签、令牌或洗牌结果会影响安全与权益时，应使用系统 CSPRNG；普通模拟、游戏和测试可使用可播种 PRNG。
追问 5：输入是链表怎么办？
先转为数组会占 O(n) 空间；若必须原地，可采用链表节点交换但随机访问代价高，需重新讨论约束。
追问 6：并发调用如何处理？
给每个实例独立状态并加锁，或返回不可变快照；不要让一个线程在另一个线程 reset 时观察到半次交换。
追问 7：为什么 Java 官方 shuffle 也采用这种思路？
Oracle 文档明确说明从后向前遍历，并把随机元素交换到当前位置；在公平随机源下所有排列等可能。