題目與使用情境
實作 reset() 回傳初始順序，shuffle() 回傳均勻隨機排列。題目考察隨機演算法、原地交換、隨機數邊界與可測試性；抽樣播放、隨機抽籤和測試夾具都可重用同一模式。
面試官考察什麼
- 是否選擇 Fisher–Yates，而非反覆交換兩個隨機位置。
- 是否讓第
i次交換只從尚未固定的區間取索引。 - 是否區分閉區間與半開區間隨機數，避免越界或偏差。
- 是否保存不可變的初始快照，讓
reset()不受洗牌影響。 - 是否給出 O(n) 時間、O(1) 額外空間和均勻性的理由。
- 是否說明偽隨機種子、空陣列、重複元素與統計測試邊界。
作答前的釐清問題
shuffle()要回傳新陣列，還是可修改工作陣列後回傳？reset()是否必須回傳獨立副本，避免呼叫方修改內部狀態？- 隨機來源是可注入的偽隨機產生器，還是系統安全隨機源？
- 元素是否允許重複？相同值但不同位置是否仍視為不同排列？
- 是否需要並行呼叫安全、可重現種子或加密級不可預測性？
- 輸入規模是否要求串流處理或只能使用常數額外空間？
30 秒回答框架
“我保存一份初始快照和一份工作陣列。洗牌時從尾端向前走，在 [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 文件明確說明從後向前走，並把隨機元素交換到目前位置；在公平隨機源下所有排列等可能。