題幹與適用情境
集合要判斷成員、插入、刪除，並從目前元素中等機率回傳一個值。雜湊表適合成員定位，動態陣列適合按隨機索引取值；難點是刪除中間元素會留下空洞。
面試官考察什麼
- 是否組合雜湊表與陣列，而非硬用單一結構。
- 是否保存「值到陣列索引」的映射，並在交換後同步更新。
- 是否理解平均 O(1) 與陣列擴容的攤銷意義。
- 是否明確 getRandom 的等機率和重複值語意。
- 是否處理空集合、刪除不存在元素與並行邊界。
作答前需要釐清的問題
- 元素是否唯一？允許重複時需要把映射改成索引集合。
- getRandom 要求等機率，還是只要回傳任意隨機元素？驗收不同。
- O(1) 是平均攤銷還是嚴格最壞情況？雜湊衝突策略會改變承諾。
- 回傳的是值還是控制代碼？可變物件需要定義雜湊與相等性。
- 是否需要執行緒安全、固定記憶體或可重現隨機來源？
30 秒回答框架
“我維護陣列 items 和雜湊表 indexOf。插入時把新值放在陣列尾端並記錄索引；隨機取值使用均勻隨機索引。刪除時找到目標索引，把尾元素搬到該位置，更新尾元素索引，再彈出陣列尾端並刪除目標映射，因此避免 O(n) 的中間搬移。雜湊與動態陣列操作按平均攤銷 O(1) 計算；空集合回傳約定錯誤，重複值則把映射改成索引集合。”
分步驟深入解答
步驟 1：建立不變量。 對每個值 v，indexOf[v] 指向 items 中唯一位置；陣列沒有空洞，所有索引都在範圍內。
步驟 2：實作 insert。 若映射已有值，依題意回傳 false；否則追加到尾端並寫入索引，平均 O(1)。
步驟 3：實作 remove。 取得目標索引 i 與尾索引 last。若 i !== last，把尾值寫到 items[i] 並把它的映射改成 i；接著彈尾並刪除目標映射。
步驟 4：實作 getRandom。 對非空陣列取均勻索引；Python 文件的 choice 說明序列元素等機率，不能從雜湊表迭代順序推斷隨機性。
步驟 5：說明複雜度。 雜湊查找、尾端追加、交換和彈尾平均攤銷 O(1)，陣列與映射空間 O(n)。雜湊最壞衝突或擴容暫停需在嚴格 SLO 下另行討論。
步驟 6：處理重複值。 將 indexOf[v] 改成保存多個索引的集合；刪除一個實例時先移除其索引，再用同樣的尾端交換更新集合。
步驟 7：驗證邊界。 測試空集合、單元素、重複刪除、刪除尾端、連續擴容和固定種子；大量 getRandom 檢查頻數接近均勻，不只斷言回傳值屬於集合。
高品質示範回答
“我用陣列保存目前值，用雜湊表保存每個值的陣列索引。刪除中間項時，把尾項搬過來並更新它的索引，再刪除尾端；這樣不需要整體左移。隨機取值從陣列的均勻隨機索引讀取，所以每個唯一值等機率。這個 O(1) 是雜湊操作和動態陣列擴容的平均攤銷保證；若允許重複值，我會把單索引映射擴充成索引集合，並重新定義刪除一個實例的語意。”
常見錯誤
- 只用雜湊表 → getRandom 需要遍歷全部鍵 → 增加緊湊陣列。
- 刪除後整體左移 → 刪除變成 O(n) → 交換尾端元素。
- 交換後忘記更新尾值索引 → 後續刪除定位錯誤 → 把映射更新視為同一原子步驟。
- 從雜湊迭代器取隨機項 → 順序不保證均勻或穩定 → 按陣列索引取樣。
- 把平均 O(1) 宣稱為最壞 O(1) → 忽略衝突與擴容 → 明確攤銷與實作前提。
追問及應對
追問 1：刪除陣列最後一個元素時怎麼辦？
目標索引等於尾索引，直接彈尾並刪除映射，不需交換。
追問 2：如何支援重複值？
映射保存值對應的索引集合；交換尾元素後同步移除舊索引、加入新索引，再從目標集合刪除一個實例。
追問 3：如何證明 getRandom 等機率？
陣列每個位置只保存一個目前實例，隨機索引在 0..n-1 均勻，因此唯一值各占一個位置時等機率。
追問 4：雜湊衝突會破壞 O(1) 嗎？
平均複雜度依賴負載因子和雜湊品質；嚴格最壞情況需要樹化桶、隨機化雜湊或不同資料結構。
追問 5：如何並行讀取與刪除？
讀取隨機索引與刪除交換必須使用同一鎖或版本檢查，否則讀者可能拿到已彈出的索引。
追問 6：如何做統計測試？
固定集合執行大量取樣，統計每個值的次數並設定統計容差；同時驗證每次回傳值仍存在於集合。