題目與範圍
給定固定整數宇宙 [0, U)，實作集合，支援 insert(x)、remove(x)、contains(x)、clear() 與走訪目前元素。前四項要求最壞 O(1)，走訪目前元素數為 O(k)。集合不允許重複值，刪除不存在的值不報錯。
公開面經記錄了 Pure Storage 的同型題目；真正考察的是 dense/sparse 陣列不變量，而不是記住某個函式庫的類別名稱。
面試官考察什麼
- 是否說明固定宇宙是前提，不能把
O(1)結論無條件推廣到任意整數。 - 是否同時維護
dense[sparse[x]] == x，並用它避免刪除後的誤判。 - 刪除是否採用末元素交換，保持 dense 前綴連續，讓走訪為
O(k)。 - 是否說明空間為
O(U)，集合很密或宇宙未知時要考慮其他結構。
作答前澄清
U是否已知，且能接受兩條長度為U的陣列？這是稀疏集合成立的資源前提。iterate()是否要求排序？本方案只保證走訪所有成員，不保證順序。- 是否需要穩定迭代器或並行存取？若需要，交換刪除和同步策略都要重新定義。
clear()是否必須避免掃描U？本題要求常數時間，因此只重設size。
30 秒回答
「我維護長度為 U 的 sparse 索引和長度為 U 的 dense 陣列，再保存目前 size。元素 x 存在，當且僅當 sparse[x] < size 且 dense[sparse[x]] == x。插入把 x 寫到 dense[size] 並記錄索引；刪除時用最後一個元素覆蓋被刪位置並修正它的索引；清空只把 size 設為零。四個核心操作都是最壞 O(1)，走訪 dense 前 size 個位置是 O(k)，空間是 O(U)。」
分步深答
第一步：定義不變量。
dense[0..size) 保存全部成員且沒有重複；若 x 在集合中，sparse[x] 是它在 dense 中的位置，且 dense[sparse[x]] == x。不在集合的值可能保留舊 sparse 內容，所以 contains 不能只檢查索引範圍。
第二步：查詢與插入。
contains(x) 先檢查 0 <= x < U，再驗證 sparse[x] < size 和反向連結。插入先呼叫 contains；若不存在，把它寫入 dense[size]，設定 sparse[x] = size，最後遞增 size。
第三步：交換刪除。
若 x 在位置 i，令 last = dense[size - 1]，把 last 寫入 dense[i]，更新 sparse[last] = i，再遞減 size。不必清理 sparse[x]，因為 size 改變後反向連結驗證會使它失效；刪除最後元素也遵循相同流程。
第四步：常數時間清空與線性走訪。
clear() 只設定 size = 0，舊陣列內容不會被視為有效成員。走訪只掃描 dense[0] 到 dense[size - 1]，因此耗時是 O(k)，不是 O(U)。
第五步：複雜度與適用邊界。
contains、insert、remove、clear 都是最壞 O(1)；走訪是 O(k)；空間是 O(U)。GCC 的實作也指出，稀疏集合適合固定宇宙且需要密集走訪的場景；宇宙未知、需要擴容或 U 遠大於可用記憶體時，雜湊集合或位圖可能更合適。
第六步：測試不變量。
用參考 Set 逐次對照隨機操作。涵蓋空集合、重複插入、刪除不存在值、刪除中間元素、刪除最後元素、清空後重用、0 與 U-1，並在每次操作後驗證 dense 前綴無重複、每個成員的反向連結成立。
高品質示範回答
「固定宇宙 [0, U) 讓我能用兩個陣列換取確定的常數時間。dense 保存目前成員的緊湊前綴，sparse 把值映射回 dense 下標；成員判斷必須同時檢查邊界、下標小於 size 和反向連結，不能只看 sparse 數值。刪除用最後元素覆蓋目標位置並更新其 sparse 下標，clear 只重設 size。如此更新和查詢是最壞 O(1)，走訪是 O(k)，空間是 O(U)；宇宙不可控時我會改用雜湊表或位圖。」
常見錯誤
- 只判斷
sparse[x] < size→ 未加入的值可能殘留合法下標 → 補上dense[sparse[x]] == x。 - 刪除後整體搬移 → 刪除退化為
O(U)或O(k)→ 用最後元素交換。 - 把 clear 寫成填零迴圈 → 清空變成
O(U)→ 只重設 size。 - 忽略固定宇宙 → 陣列索引越界或記憶體不可接受 → 先確認
[0, U)與容量限制。 - 聲稱走訪是 O(1) → 取到視圖是常數，處理全部元素仍需
O(k)→ 區分返回視圖與消費元素。
追問與回答
追問 1：如何支援任意整數？
先做座標壓縮，把實際值映射到 [0, U)；若值域持續增長或無法預掃描，雜湊集合更自然，但其常數時間是攤銷或期望意義，不能複用本題的最壞 O(1) 結論。
追問 2：如何保證走訪順序？
目前 dense 的順序會被交換刪除改變。若要求插入順序，需要額外鏈結串列或穩定陣列，刪除和空間開銷都會變化；應先確認順序是否屬於介面契約。
追問 3：什麼時候選擇位圖？
若只需要成員判斷、宇宙規模適中且希望每個值佔一位，位圖更省空間。若還需要快速列舉成員，稀疏集合的 dense 前綴通常更適合；最終選擇取決於 U、成員數和存取模式。