課題と範囲
search、insert、delete を持つ整数キーの順序付き集合を実装します。この構造は期待値 O(log n) の操作を使用し、平衡木で必要とされる回転を回避する必要があります。重複を拒否するかカウントするかを明示してください。本記事では集合（set）を採用するため、既存のキーを挿入する操作は no-op となります。
この質問は、Google の面接の課題や LeetCode の面接投稿など、公開されている面接レポートや実装の議論に登場します。コーディングのシグナルとして評価されるのは、ライブラリクラスの暗記ではなく、複数の前方ポインタレベルを維持し、その不変条件を証明できるかどうかです。
面接官が評価するポイント
- レベル0を完全なソート済みリストとして維持し、それより上の各レベルをその部分列として維持しているか。
- 挿入と削除において、ベースリストのリンクを失うことなく、すべての前駆（predecessor）レベルを更新しているか。
- 期待値
O(log n)と不運なO(n)操作を区別し、ランダムレベルの境界をテストしているか。
Redis はソート済みセットのエンコーディングの1つにスキップリスト表現を使用しており、MIT のアルゴリズム講義ノートには確率的解析が記載されています。これらは実装と理論の証拠ですが、あらゆるワークロードで木構造をスキップリストに置き換えるべきであることを意味するものではありません。
回答前の確認事項
- 集合（Set）か多重集合（Multiset）か？ 集合は重複キーを拒否します。多重集合はカウントまたは一意のノード識別子を必要とします。
- 呼び出し元は順位（Rank）クエリや範囲クエリを必要とするか？ 順位にはスパン（span）や幅のメタデータが必要です。基本問題では要素の存在確認（membership）のみが必要です。
- 決定論的な再現性は必要か？ テスト用にはシード付き乱数生成器を注入し、本番環境では偏りのない生成器を使用します。
- メモリ制限はどの程度か？ 各ノードは可変数の前方ポインタを持つため、レベルの上限と確率がメモリに影響します。
30秒での回答
「各レベルの前方ポインタを持つ番兵（sentinel）と、ソート済みのレベル0リストを保持します。検索は最高レベルから開始し、次のキーが小さい間進み、各レベルで最後の前駆ノードを記録します。挿入はランダムな高さを選択し、それらの前駆ノードの後ろに新しいノードを挿入し、既存のキーに対しては何もしません。削除は同じ前駆ノード配列を使用して、対象ノードが存在するすべてのレベルでリンクを解除し、上位リストが空になったらアクティブな高さを下げます。幾何分布の高さ確率により、検索、挿入、削除の期待値は O(log n)、空間の期待値は O(n) です。ただし、病的な乱数列では O(n) になる可能性があります。」
ステップバイステップの詳細な回答
ステップ 1: 不変条件を定義する。
レベル0には、厳密に昇順ですべてのキーが含まれます。レベル i + 1 はレベル i の部分列であり、各ノードの前方ポインタはキー順に並んでいます。番兵は MAX_LEVEL 個のポインタを持ち、ユーザーキーは持ちません。アクティブレベルは、空でない最上位のリストです。
ステップ 2: 前駆ノードを収集しながら検索する。
番兵の最も高いアクティブレベルから開始します。次のノードが存在し、そのキーがターゲットより小さい間、前方に進みます。1レベル降りて続行します。訪問した最後のノードを update[i] に保存します。レベル0の処理後、update[0].next[0] はターゲットまたはその挿入位置になります。
ステップ 3: ランダムな高さで挿入する。
例えば確率 p = 1/2 で繰り返し昇格させ、MAX_LEVEL を上限とすることで幾何分布の高さを取得します。レベル0の候補がそのキーを持っている場合、false を返します。新しい高さ未満のすべてのレベルについて、新しいノードのポインタを前駆ノードの次のポインタに設定し、次に前駆ノードが新しいノードを指すようにします。必要に応じてアクティブレベルを拡張します。
type Node = { key: number; next: Array<Node | null> };
class SkipSet {
private readonly maxLevel = 16;
private readonly head: Node = { key: Number.NEGATIVE_INFINITY, next: [] };
private level = 1;
constructor() {
this.head.next = Array(this.maxLevel).fill(null);
}
private randomLevel(): number {
let h = 1;
while (h < this.maxLevel && Math.random() < 0.5) h += 1;
return h;
}
search(key: number): boolean {
let node = this.head;
for (let i = this.level - 1; i >= 0; i -= 1) {
while (node.next[i] && node.next[i]!.key < key) node = node.next[i]!;
}
return node.next[0]?.key === key;
}
insert(key: number): boolean {
const update = Array<Node>(this.maxLevel);
let node = this.head;
for (let i = this.level - 1; i >= 0; i -= 1) {
while (node.next[i] && node.next[i]!.key < key) node = node.next[i]!;
update[i] = node;
}
if (update[0].next[0]?.key === key) return false;
const height = this.randomLevel();
if (height > this.level) {
for (let i = this.level; i < height; i += 1) update[i] = this.head;
this.level = height;
}
const fresh: Node = { key, next: Array(height).fill(null) };
for (let i = 0; i < height; i += 1) {
fresh.next[i] = update[i].next[i];
update[i].next[i] = fresh;
}
return true;
}
delete(key: number): boolean {
const update = Array<Node>(this.maxLevel);
let node = this.head;
for (let i = this.level - 1; i >= 0; i -= 1) {
while (node.next[i] && node.next[i]!.key < key) node = node.next[i]!;
update[i] = node;
}
const target = update[0].next[0];
if (!target || target.key !== key) return false;
for (let i = 0; i < this.level; i += 1) {
if (update[i].next[i] !== target) break;
update[i].next[i] = target.next[i] ?? null;
}
while (this.level > 1 && !this.head.next[this.level - 1]) this.level -= 1;
return true;
}
}ステップ 4: ターゲットノードのすべての出現を削除する。
前駆ノード配列によって、各レベルにおけるターゲットの前駆ノードが特定されます。update[i].next[i] がそのターゲットであるレベルのみリンクを解除します。より上位のレベルには含まれていない可能性があります。その後、番兵の最上位ポインタが空である間、アクティブレベルを下げます。
ステップ 5: 計算量とメモリを分析する。
昇格確率 p が0より大きく1未満の場合、期待される高さは定数であり、期待される検索パス長は対数関数的です。検索、挿入、削除の期待値は O(log n) です。運の悪い乱数列の場合、最悪計算量は O(n) になります。期待されるポインタ数は定数項を除いて n/(1-p) であるため、p = 1/2 はノードあたり約2個のポインタと引き換えに短いパスを実現します。
ステップ 6: 構造、ランダム性、境界条件をテストする。
テストではシード付き生成器を使用します。空の状態での検索/削除、先頭および末尾のキー、重複、唯一のノードの削除、レベルを跨いだ削除、負の値、および反復的な挿入/削除サイクルをチェックします。各操作の後にレベル0を走査し、参照用の Set と比較します。各上位レベルがソートされており、すべてのノードがレベル0にも存在することを確認します。高さやポインタの破損を検出するために、多くのシードで実行します。
高品質な回答例
「番兵とソート済みのレベル0チェーンを持つセットをモデル化します。それより上のすべてのレベルはレベル0の部分列です。検索は最も高いアクティブレベルから降下し、各レベルでの前駆ノードを記録します。挿入は既存のキーを拒否し、幾何分布に基づくランダムな高さを選択し、それらの前駆ノードの後ろにノードを挿入します。削除は同じ前駆ノード配列を見つけ、対象が現れるすべてのレベルからリンクを解除し、空になった上位レベルを切り詰めます。
これらの操作は期待値 O(log n)、期待空間 O(n) ですが、ランダムな高さの運が悪い場合には最悪計算量 O(n) の時間が依然として発生し得ます。決定論的なテストのためにシード付き乱数ソースを使用し、すべての操作の後にレベル0を参照セットと比較し、すべての上位レベルに対してソート順および部分列の不変条件をアサートします。」
よくある間違い
- レベル0のみを更新する → 上位レベルの検索でキーがスキップされたり残ったりする可能性がある → ノードを含むすべてのレベルで挿入またはリンク解除を行う。
- ランダムな高さを保証として扱う → 病的なシーケンスにより線形パスが生成される可能性がある → 期待される境界と最悪ケースの境界を述べる。
- 意図せず重複ノードを許可する → 検索と削除のセマンティクスが曖昧になる → コーディング前にセットかマルチセットの挙動を選択する。
- 空の上位レベルの切り詰めを怠る → 検索が無効なレベルを検査し、管理状態がずれる → 削除後にアクティブレベルを下げる。
- 最終的な存在確認のみをテストする → 破損した上位ポインタが隠れたままになる可能性がある → 各操作の後に順序と部分列の不変条件を確認する。
フォローアップと回答
フォローアップ 1: 重複キーをどのようにサポートしますか？
仕様を定めます。マルチセットでは各キーノードにカウントを保持して挿入や削除の繰り返しでカウントを更新するか、比較キーに一意のシーケンス番号を保持します。メモリが許す場合はノードでカウントを保持します。特定の1つの出現を削除する場合には一意の識別子が役立ちます。
フォローアップ 2: 順位（Rank）クエリをどのように追加しますか？
各前方ポインタの横にスパン（span）または幅を保存します。検索中、右に進むにつれてスパンを累積します。挿入と削除では、各レベルで影響を受けるスパンを更新します。単純なセットの実装には、順位クエリに対数時間で答えるための十分なメタデータがありません。
フォローアップ 3: 代わりに平衡木を選択するのはどのような場合ですか？
最悪ケースの保証、決定論的な反復の形状、または豊富な順序付き操作が実装の単純さよりも重要である場合は、平衡木を使用します。スキップリストは、期待される対数パフォーマンス、容易な並行バリアント、またはポインタベースの順序付きインデックスで十分な場合に適しています。特定の構造が一律に高速であると主張するのではなく、メモリオーバーヘッドとワークロードを測定してください。