1. 題目
你需要一個有序字典，支援按鍵搜尋、插入、刪除與範圍掃描。資料量會動態增長，面試官要求平均操作接近 O(log N)，但不要求實作 AVL 或紅黑樹。請設計 Skip List 並分析隨機性、邊界與記憶體配置。
2. 約束與澄清
- 明確鍵是否唯一；若重複，定義覆蓋、計數或穩定順序。
- 設定最大層數與每層晉升機率
p，通常從底層鏈結串列開始向上建立索引。 - 搜尋、插入與刪除需要維護每一層的前驅節點；範圍遍歷只需沿底層鏈結串列前進。
- 先討論單執行緒結構；若要並發，需要額外的鎖、版本或無鎖演算法證明。
3. 核心思路
每個節點擁有高度隨機的 forward 指標陣列。搜尋從最高層頭節點開始：若下一個鍵仍小於目標，就沿目前層前進；否則下降一層。插入先記錄每層前驅，再隨機產生新高度並逐層接入。刪除同樣使用前驅陣列斷開指標。隨機層高讓高層節點稀疏，期望總指標數為 O(N)，搜尋、插入與刪除的期望時間為 O(log N)。
4. 參考實作
text
randomLevel(rng, p, maxLevel):
level = 1
while level < maxLevel and rng.uniform01() < p:
level += 1
return level
findPredecessors(key):
update = array(maxLevel)
node = head
for level from maxLevel - 1 down to 0:
while node.forward[level] != nil and node.forward[level].key < key:
node = node.forward[level]
update[level] = node
return update
insert(key, value):
update = findPredecessors(key)
if update[0].forward[0].key == key:
update[0].forward[0].value = value
return
node = Node(key, value, randomLevel(rng, p, maxLevel))
for level in 0 .. node.height - 1:
node.forward[level] = update[level].forward[level]
update[level].forward[level] = node實作中必須先檢查 nil 再讀取鍵，並保證新節點高度不超過 maxLevel。刪除時把所有指向目標節點的層級一次接到後繼節點；最高層為空後可降低目前有效層數，但不必移動節點。
5. 複雜度與最壞情況
當晉升機率固定且隨機源獨立時，層數與路徑長度的期望為對數級，空間期望為 O(N)。隨機性失效或敵手能預測層高時，結構可能退化成單鏈結串列，操作變為 O(N)。可使用高品質隨機源、限制最大高度、定期重建或採用確定性平衡樹來處理對抗性工作負載。
6. 驗證與並發取捨
- 用有序、重複、空結構與極端鍵測試搜尋、更新、刪除及範圍遍歷。
- 統計不同 N 下的高度分布、平均路徑長度與指標數量，檢查是否符合預期。
- 做隨機操作序列，與標準有序映射對拍，驗證內容和順序一致。
- 並發版本要說明讀寫鎖粒度、刪除標記、記憶體回收與 ABA 風險；不能只把指標寫入包在一個鎖裡就宣稱無鎖安全。
7. 常見誤區
- 只寫搜尋，不維護每層前驅，導致插入或刪除退化為重新掃描。
- 忽略重複鍵策略，插入後範圍遍歷順序不穩定。
- 把期望
O(log N)當作最壞保證，未討論隨機源與對抗性輸入。 - 使用固定高度陣列浪費記憶體，或允許高度無界導致陣列越界。
8. 面試評分點
能從高層向下搜尋
應說明每層前進條件、下降時機，以及為什麼底層鏈結串列包含全部元素。
能正確維護前驅
應在插入和刪除中保存各層 update 陣列，處理覆蓋、空指標與最高層收縮。
能解釋機率複雜度
應給出 O(log N) 期望時間、O(N) 期望空間和退化到 O(N) 的條件。
能識別並發邊界
應討論鎖、版本、標記刪除、記憶體回收與 ABA，而不是把單執行緒程式直接當作並發實作。