題目與範圍
實作一個整數有序集合，支援 search、insert 和 delete。目標是期望 O(log n)，並避免平衡樹旋轉。先說明重複鍵規則；本文選擇集合，因此插入既有鍵時不改變結構。
公開面經和實作討論包含跳表題目，例如 Google 面試題和 LeetCode 面試貼。重點是維護多層前向指標並證明不變量，不是記住某個函式庫類別。
面試官考察什麼
- 是否保持第 0 層包含完整有序鏈，所有高層都是它的子序列。
- 插入和刪除是否更新每一層前驅而不破壞底層連結。
- 是否區分期望
O(log n)與隨機性不利時的O(n)，並測試隨機層高邊界。
Redis 的有序集合編碼使用跳表，MIT 演算法講義給出機率分析。它們分別是實作和理論證據，不代表所有工作負載都應以跳表取代樹。
作答前澄清
- 集合還是多重集合？ 集合拒絕重複鍵；多重集合需要計數或唯一節點識別。
- 是否需要排名或範圍查詢？ 排名需要跨度元資料；基礎題只要求成員判斷。
- 是否需要確定性重播？ 測試使用帶種子的隨機來源，生產使用無偏隨機產生器。
- 記憶體上限是多少？ 節點擁有可變數量的前向指標，層數上限和晉升機率都會影響記憶體。
30 秒回答
「我用一個每層都有前向指標的哨兵，以及按鍵排序的第 0 層鏈。查找從最高層開始，只有下一個鍵較小時才前進，並記錄每層最後一個前驅。插入產生隨機層高，把新節點接到這些前驅之後；既有鍵直接返回。刪除使用同一組前驅，在節點出現的每層解除連結，再在頂層為空時降低活動層數。幾何層高帶來期望 O(log n) 的查找、插入和刪除，期望空間為 O(n)；隨機序列極端時仍可能是 O(n)。」
分步深答
第一步：定義不變量。
第 0 層包含所有鍵且嚴格遞增。第 i + 1 層是第 i 層的子序列，每個節點的前向指標按鍵排序。哨兵沒有使用者鍵，但有 MAX_LEVEL 個指標。活動層是最高的非空層。
第二步：查找並收集前驅。
從哨兵的最高活動層開始。只要下一個節點存在且鍵小於目標就向前走；下降一層後繼續。把每層最後存取的節點放入 update[i]。到達第 0 層後，update[0].next[0] 要麼是目標，要麼是插入位置。
第三步：用隨機層高插入。
用晉升機率 p = 1/2 的幾何過程產生層高，並限制在 MAX_LEVEL。若第 0 層候選鍵相同，回傳 false。對新節點涵蓋的每一層，先保存前驅的下一個節點，再讓前驅指向新節點。若層高超過目前活動層，就擴展活動層。
第四步：在所有出現的層刪除目標。
前驅陣列給出每層目標節點的前驅。只有當 update[i].next[i] 正是目標時才解除該層連結；更高層可能沒有目標。刪除後，只要哨兵頂層指標為空，就降低活動層。
第五步：分析複雜度和記憶體。
當晉升機率在 0 和 1 之間時，期望層高為常數，期望搜尋路徑為對數級。查找、插入和刪除期望 O(log n)，隨機不利時最壞 O(n)。期望指標數與 n/(1-p) 同階，因此 p = 1/2 用約兩倍指標換取較短路徑。
第六步：測試結構、隨機性和邊界。
測試使用帶種子的隨機來源。涵蓋空集合、首尾鍵、重複插入、刪除唯一節點、跨多層刪除、負數和反覆插刪。每次操作後把第 0 層與參考 Set 對照，並驗證每個高層有序且節點都出現在第 0 層。執行多組種子捕捉層高和指標損壞。
高品質示範回答
「我把它建模為帶哨兵的集合，第 0 層是有序鏈，所有高層都是第 0 層的子序列。查找從最高活動層下降，同時記錄每層前驅。插入拒絕重複鍵，產生幾何隨機層高並在前驅之後插入；刪除找到同一前驅陣列，在節點出現的每層解除連結，並清理空的頂層。
操作期望 O(log n)、期望空間 O(n)，但隨機層高不利時最壞是 O(n)。我會在測試中使用帶種子的隨機來源，每次操作都和參考集合比較，並檢查排序及子序列不變量。」
常見錯誤
- 只更新第 0 層 → 高層查找會跳過或保留該鍵 → 在節點出現的每層插入或解除連結。
- 把隨機層高當成保證 → 極端序列可能形成線性路徑 → 同時說明期望和最壞邊界。
- 無意中允許重複節點 → 查找和刪除語義不明確 → 先選擇集合或多重集合。
- 刪除後不清理空頂層 → 搜尋檢查過時層，狀態逐漸漂移 → 刪除後降低活動層。
- 只測試最終成員 → 損壞的高層指標可能隱藏 → 每次操作都檢查排序和子序列不變量。
追問與回答
追問 1：如何支援重複鍵？
先定義合約。多重集合可在每個鍵節點儲存計數，讓重複插入和刪除只修改計數；也可以把唯一序號併入比較鍵。記憶體允許時計數更簡單；需要刪除某個具體出現時，唯一識別更合適。
追問 2：如何加入排名查詢？
在每個前向指標旁保存跨度。查找向右移動時累加跨度，插入和刪除在每層更新受影響跨度。簡單集合實作沒有足夠元資料，不能直接以對數時間回答排名。
追問 3：什麼時候選擇平衡樹？
當最壞邊界、確定性迭代形態或豐富有序操作比實作簡潔更重要時，選擇平衡樹。跳表適合接受期望效能、希望實作指標型有序索引或需要容易擴充並行變體的場景。應測量記憶體和工作負載，不要聲稱一種結構總是更快。