1. 問題
キーの検索、挿入、削除、および範囲スキャンをサポートする順序付き辞書が必要です。データセットは動的に増加し、面接官は AVL 木や赤黒木を必要とせずに平均 O(log N) に近い操作を求めています。スキップリストを設計し、ランダム性、境界条件、メモリレイアウトを分析してください。
2. 制約と確認事項
- キーが一意であるかどうかを決定します。一意でない場合は、上書き、カウント、または安定した順序付けを定義します。
- 最大レベルと昇格確率
pを選択し、最下層の連結リストから上方へインデックスを構築します。 - 検索、挿入、削除では各レベルの先行ノードを保持し、範囲イテレーションは最下層のリストを辿ります。
- まずシングルスレッド構造について説明します。並行性には、追加のロック、バージョニング、またはロックフリーアルゴリズムの証明が必要です。
3. コアとなる考え方
各ノードは、ランダムなサイズの前方ポインタ配列を保持します。検索は最高レベルのヘッドから開始し、次のキーがターゲット未満である限り進み、そうでなければ1レベル下降します。挿入では先行ノードを記録し、ランダムな高さを選択して、ノードを各レベルに挿入します。削除では同じ先行ノード配列を使用してリンクを解除します。疎な上位レベルにより、期待ポインタ数は O(N) となり、期待される検索、挿入、削除は O(log N) となります。
4. 参照実装
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 リスクについて説明します。ポインタの書き込みを1つのロックでラップするだけでは、ロックフリー設計とは言えません。
7. よくある間違い
- 先行ノード配列なしで検索を実装し、挿入や削除でリストの再スキャンを強いられること。
- 重複キーのポリシーを無視し、不安定な範囲順序を生成してしまうこと。
- ランダム性や敵対的入力について議論することなく、期待される
O(log N)を最悪ケースの保証として扱ってしまうこと。 - メモリを浪費する固定長配列を使用することや、配列をオーバーフローさせる無制限の高さを許可すること。
8. 面接の評価ポイント
上位レベルから下方へ検索しているか
候補者が各レベルの進む条件、下降するタイミング、およびなぜ最下層のリストにすべての要素が含まれているのかを説明できているか。
先行ノードを正しく維持しているか
候補者が各レベルの更新配列（update 配列）を保存し、上書き、nil ポインタ、最高アクティブレベルの縮小を処理できているか。
確率的計算量を説明しているか
候補者が期待時間計算量 O(log N)、期待空間計算量 O(N)、および O(N) への退化を引き起こす条件を述べているか。
並行性の境界を特定しているか
候補者がシングルスレッドのコードを並行処理可能として扱うのではなく、ロック、バージョン、論理削除、メモリ回収、ABA について議論できているか。