プロンプトとユースケース
ラディックスヒープは、抽出されるキーが非減少であるダイクストラ法などのアルゴリズムで役立つ、単調優先度付きキュー用の整数データ構造です。直近に抽出されたキーを境界として使用し、最上位の異なるビットによってバケット分けします。
面接官が評価するポイント
- 挿入されるキーが直近に抽出されたキーによって制約されているか。
- 最上位の異なるビットとバケットの範囲が正しいか。
- 最小の空でないバケットが新しいベースで再分配されているか。
- バケットおよび最小キーの不変条件が維持されているか。
- 空のキュー、オーバーフロー、後退キーが適切に処理されているか。
- 再分配とならし計算量が正確に説明されているか。
回答前の確認事項
- キーは固定幅の符号なし整数ですか、それとも任意精度ですか？
- 挿入されるキーは直近に抽出されたキーより小さくてもよいですか？
- 同一キーのペイロードは安定（stable）であるべきですか？
pop-minのみが必要ですか、それとも decrease-key や削除も必要ですか？- 空の pop やオーバーフローは何を返すべきですか？
- 明瞭さ、低い定数係数、漸近的限界のどれが優先事項ですか？
30秒の回答フレームワーク
「直近に抽出されたキーである last と W+1 個のバケットを維持します。last に等しいキーはバケット 0 に入り、そうでない場合のバケットは bit_length(key XOR last) です。バケット 0 が空の場合、最小の空でないバケットを見つけ、その最小キーを新しい last として走査し、そのバケットを再分配してバケット 0 から pop します。last 未満のキーは拒否されます。」
ステップごとの詳細解説
ステップ 1: 不変条件を定義する。 last は決して減少せず、保留中のすべてのキーは key >= last を満たし、バケット i には last との最上位の異なるビットが i であるキーが含まれます。
ステップ 2: バケットを計算する。 key == last のときインデックスは 0 であり、それ以外の場合は bit_length(key XOR last) を使用します。W ビットのキーには W+1 個のバケットが必要です。
ステップ 3: push を実装する。 非負性、ビット幅、key >= last を確認し、(key, value) をそのバケットに配置します。等しいキーは共存できます。
ステップ 4: pop を実装する。 空でない場合はバケット 0 から返します。それ以外の場合は、最も低い空でないバケットを見つけ、その最小キーを走査して last に代入します。
ステップ 5: 再分配する。 そのバケットを空にし、新しい last に対して各アイテムのインデックスを再計算します。インデックスは減少し、少なくとも 1 つのアイテムがバケット 0 に到達します。
ステップ 6: 境界を処理する。 定義された空の結果を返します。未定義の XOR およびインデックス動作を回避するため、ビット幅を超えるキーや last 未満のキーは拒否します。
ステップ 7: 計算量を定義する。 各アイテムが再分配される回数はワードサイズ W によって制限されます。一般的なならしコストは O(W)、空間計算量は O(n + W) であり、二分ヒープより普遍的に高速というわけではありません。
質の高い模範解答
「64ビットの符号なしキーと 65 個のバケットを使用します。last はゼロから始まります。last 未満のキーは拒否され、そうでない場合は bit_length(key XOR last) によってバケットが選択されます。pop はバケット 0 から取得するか、最も低い空でないバケットを見つけてその最小キーを走査して last に設定し、再分配します。等しいキーは個別のペイロードを保持します。空の pop は空の値を返し、オーバーフローや後退キーは失敗します。各アイテムはワードサイズによって制限された回数だけ再分配され、アイテムとバケットのための空間を使用します。」
よくある間違い
- 後退キーを許可する → バケットの不変条件が破綻する →
key < lastを拒否する。 - バケットに
log2(key)を使用する → 現在のベースが無視される →key XOR lastを使用する。 - 再分配後に
lastを変更しないままにする → 抽出が誤る可能性がある → 最初に最小値を走査する。 - バケット内の最初のアイテムを取得する → 最小値でない可能性がある → 最小キーを走査する。
- すべての操作が O(1) だと主張する → ワードサイズと再分配が無視される →
Wとならしの前提条件を明記する。
フォローアップの質問と回答
フォローアップ 1: なぜダイクストラ法に適しているのですか？
抽出される距離は非減少であり、新しい候補距離は現在の最小値以上であるため、単調キーの要件を満たします。
フォローアップ 2: 任意の decrease-key が必要な場合はどうなりますか？
ラディックスヒープは後退キーには適していません。二分ヒープやペアリングヒープを使用するか、バージョンを保持して古いエントリを遅延破棄（lazy discard）してください。
フォローアップ 3: なぜバケット 0 から直接 pop できるのですか？
バケット 0 のすべてのキーは last に等しいため、すべて現在の最小キーです。
フォローアップ 4: なぜ再分配されたインデックスは減少するのですか？
新しい last はバケットの最小値です。他のすべてのアイテムの最上位の異なるビットは古いバケットインデックス以下であり、少なくとも 1 つがバケット 0 に到達します。
フォローアップ 5: 等しいキーの安定性をどのように維持しますか？
ペイロードに単調シーケンス番号を追加し、バケット 0 で (key, sequence) を選択します。それ以外の場合、安定性は任意です。
フォローアップ 6: 負のキーについてはどうですか？
符号なしの順序付けられた空間にマップするか、非負のキーのみを指定します。順序の定義がない符号付き XOR は安全ではありません。
フォローアップ 7: 二分ヒープの方が優れているのはどのような場合ですか？
キーが単調整数でない場合、ワードサイズが大きい場合、更新が複雑な場合、または特化した計算量制限よりも単純さと汎用性が重視される場合に使用します。