コーディング面接：Adaptive Radix Tree（ART）をどのように実装しますか？

プロンプトとコンテキスト

挿入、完全一致検索、最長プレフィックス一致、および削除を備えた、可変長バイトキーと値を格納するARTを実装してください。ノードはNode4、Node16、Node48、Node256の間で適応します。パス圧縮はキーのセマンティクスを保持する必要があります。これは、圧縮ツリー、インデックス、およびメモリレイアウトに関するcodingの質問です。

面接官が評価するポイント

単なる文字だけでなく、圧縮パス、キーの終端、および任意のバイトを適切に処理できるか。
4つのノードタイプすべての間でアップグレードとダウングレードを維持できるか。
最長プレフィックス一致を実装し、完全一致と祖先ノードの値を区別できるか。
削除処理が圧縮の不変条件を保持することを証明できるか。
計算量、メモリのトレードオフ、および並行性について説明できるか。

質問すべき確認事項

キーは不透明なバイト列であり、ゼロバイト（NULLバイト）を含むことができますか？
内部ノードは値を保持できますか、それともリーフのみですか？
最長プレフィックス検索は、どのプレフィックス長と残りを返すべきですか？
削除時に即座に縮小する必要がありますか、それとも回収（リクレイム）を遅延させてもよいですか？
ロックフリーな読み取りやスナップショットの公開は必要ですか？

30秒での回答

「不透明なバイト列を比較し、圧縮されたプレフィックスと終端値を内部ノードに格納します。疎なノードにはNode4/16を使用し、密なノードはNode48/256にアップグレードします。削除処理ではダウングレードを行い、値を持たない単一の子ノードのパスをマージします。完全一致検索はキー全体を消費し、最長プレフィックス検索は最も近い値を持つノードを記録します。ロックやイミュータブルなスナップショットを追加する前に、参照用マップに対してシングルスレッドでの不変条件を検証します。」

詳細な回答

ステップ 1: ノードとリーフを定義する

内部ノードは、圧縮プレフィックス、その長さ、オプショナルな値、および次のバイトによってインデックス付けされた子ノードを格納します。リーフは完全なキーまたは一意の値の参照を格納し、あるキーが別のキーのプレフィックスである場合を処理します。

text

Node { prefix, prefixLen, hasValue, value, children }
Leaf  { key, value }

キーはnull終端文字列ではなく任意のバイト列であるため、プレフィックス長は明示的です。

ステップ 2: 挿入と分割

ノードのプレフィックスとキーの残りの部分を比較します。一致する場合は、続行するか値を更新します。分岐する場合は、共通プレフィックスを含む親ノードを作成し、異なるバイトの下に古いノードと新しいリーフをアタッチします。新しいキーが共通プレフィックスで終了する場合は、親ノードの値フラグを設定します。

ステップ 3: 適応型レイアウトを選択する

Node4とNode16はコンパクトなキー配列とポインタ配列を保持します。検索はそれらをスキャンするかベクトル比較を使用できます。Node48は可能な256バイトすべてを48個のポインタスロットにマッピングし、256個の常駐ポインタを回避します。Node256はバイトによって直接インデックス付けします。プレフィックスや値の状態を失うことなく子ノードをコピーしてアップグレードします。

ステップ 4: 完全一致検索と最長プレフィックス検索

完全一致検索は、キーのすべてのバイトを消費し、hasValueまたは等しいリーフキーにヒットする必要があります。最長プレフィックス検索は、ノードが値を持つたびに候補を記録し、失敗またはキー消費まで次のバイトを通じて探索を続け、最後の候補とその長さを返します。

ステップ 5: 削除と縮小

値を削除した後、子のないノードを削除します。値を持たないノードに子が1つある場合は、そのプレフィックスとエッジバイトを子ノードにマージします。文書化された子ノード数の閾値でNode256、Node48、Node16、およびNode4をダウングレードします。マージ中もリーフの完全なキーを保持します。

ステップ 6: 不変条件と計算量

ルートからリーフへの任意のパスに沿ってプレフィックス、エッジバイト、およびリーフを連結すると、元のキーが復元されなければなりません。内部ノードは重複するエッジバイトを持つことはできません。hasValueは、キーがまさにそこで終了することを意味します。キー長をLとすると、検索はO(L)です。適応型レイアウトにより、疎なノードに対して256スロットを割り当てることを回避します。

ステップ 7: テストと並行性の追加

ランダム化された挿入、検索、削除、および最長プレフィックス操作を参照用マップと比較します。空のキー、ゼロバイト、プレフィックスキー、および全256分岐を含めます。並行バージョンはまず読み取り/書き込みロックから始めます。ロックフリーポインタが公開される前に回収が安全である必要があるため、その後に初めてcopy-on-write、エポック、またはRCUを検討します。

模範解答

「キーを不透明なバイト列として扱います。ノードには圧縮プレフィックス、オプショナルな終端値、および子ノードを保持させます。部分一致は共通プレフィックスの親ノードを分割します。子ノード数に応じてNode4、16、48、256へとアップグレードし、削除時はダウングレードして単一の子パスをマージします。完全一致検索はキー全体を消費し、最長プレフィックス検索は最も近い値を持つノードを記憶します。

すべてのパスは元のキーを再構築できなければなりません。ランダムテストはマップと比較し、ゼロバイト、空のキー、プレフィックスキー、および密な分岐をカバーします。シングルスレッドでの正しさを確認した後、ロックを使用します。copy-on-writeまたはロックフリーの設計には、エポックまたは同等の安全な回収メカニズムも必要です。」

よくある間違い

キーを文字として扱う → バイナリキーやゼロバイトで失敗する → バイト長と値を比較する。
内部ノードの値を忘れる → プレフィックスキーが一致しない → hasValueを維持する。
Node48に256個のポインタを持たせる → 疎なメモリの節約効果が失われる → インデックスマップを使用する。
マージせずに値をクリアする → 空のパスが残る → 閾値で縮小する。
祖先の候補を無視する → 最長プレフィックス検索で一致を見落とす → 最後に値を持っていたノードを記憶する。
安全な回収なしに生ポインタを公開する → リーダーが解放済みメモリを使用する → ロックから始め、その後にエポック/RCUを適用する。

フォローアップの質問と回答

フォローアップ 1: なぜ常にNode256を使用しないのですか？

ほとんどのノードは疎であるため、256スロットはメモリを浪費します。適応型レイアウトは疎な領域と密な領域のバランスを取ります。

フォローアップ 2: あるキーが別のキーのプレフィックスである場合はどうなりますか？

短いキーの値を内部ノードに格納し、長いキーのために子ノードを保持します。

フォローアップ 3: 削除後のマージはいつ行いますか？

値を持たない1つの子ノードを持つノードについて、そのプレフィックスとエッジバイトを連結してマージし、リーフキーを保持します。

フォローアップ 4: 並行スナップショットをどのように公開しますか？

新しいイミュータブルなルートに対してcopy-on-writeを使用し、エポックまたは参照カウントを使用して古いツリーを回収します。