プロンプトとコンテキスト
/api、/api/users、/api/users/admin のような文字列キーが与えられます。各エッジが空でない文字列を保持し、各ノードが値を保持できる基数木を実装してください。insert(key, value)、get(key)、longestPrefix(key)、および delete(key) をサポートしてください。空のキーはルート値としてのみ許可されます。面接官はライブラリの呼び出しではなく、データ構造とその論理的根拠を求めています。
面接官が見ているポイント
- ルート以外のすべてのエッジラベルが空でなく、兄弟ノードが異なる先頭文字を持つという不変条件を維持できているか。
- サブツリーや値を失うことなく、最初の不一致箇所でエッジを分割できるか。
- 完全一致検索と最長プレフィックス検索を明確に区別できているか。
- 削除後に値を持たない単項ノード（unary node）を圧縮し、キー長に基づく真の計算量を提示できているか。
確認すべき明確化のための質問
キーがバイト列か Unicode コードポイントか、大文字と小文字を区別するか、重複挿入時に値を置換するか、並行アクセスが必要かを確認します。longestPrefix が一致したキー、値、またはその両方を返すかどうかも尋ねます。バイト指向の実装が最もシンプルであり、計算量はバイト数に依存します。明示的に要求されない限り、Unicode の正規化はツリーの外部で処理すべきです。並行性が必要な場合は、アルゴリズムがスレッドセーフであると暗黙的に主張するのではなく、構造体の周囲に同期処理を追加します。
30秒で答えるフレームワーク
各ノードはエッジラベル、オプションの値、および先頭バイトでインデックス付けされた子ノードを保持します。挿入時は、残りのキーと子のラベルを比較します。完全に一致した場合は下降し、部分的に一致した場合は子を共通プレフィックスノードと2つのサフィックスノードに分割します。完全一致検索は、キー全体が値を持つノードで消費された場合にのみ成功します。最長プレフィックス検索は、下降中に見つかった最も深い値ノードを記録します。削除時は値をクリアし、そのノードに値がない場合は唯一の子ノードとマージします。
ステップごとの詳細解説
- 不変条件の提示。 ルートにはエッジラベルがありません。その他のすべてのノードは空でないラベルを持ちます。同一ノードの2つの子が同じバイトで始まることはありません。ノードは子を持つ場合でも値を保持できるため、
/apiと/api/usersは共存できます。 - 最長共通プレフィックスによる挿入。 残りのキーと子ラベルの間の共通プレフィックスを
pとします。pが空の場合は別の子を選択します。pが子ラベルと等しい場合は、それを消費して再帰します。pの方が短い場合は、pというラベルの新しい親を作成し、古い子をそのサフィックスの下に移動させてから、新しいキーのサフィックスを付加するか、キーが分割点で終了する場合は値を置換します。 - 検索。 完全一致検索は一度に1つのエッジを消費し、不一致または子が存在しない場合に失敗します。最長プレフィックス検索では、まずルート値を記録し、次にキーが終了するまでに到達したすべての値ノードを記録して、最後の記録を返します。
- 削除と圧縮。 対象ノードの値をクリアします。ノードに値がなく、子が1つだけの場合は、2つのラベルを連結してその子の持つ子ノードを昇格させます。複数の子を持つか、まだ値を保持している場合は、ノードをそのまま維持します。これにより兄弟ノードの不変条件が保たれます。
- 計算量。 ハッシュマップによる子ノードの選択を行う場合、各操作は最大でも入力キーのバイト数分しか比較しないため、時間計算量は O(k) ＋ ハッシュマップのオーバーヘッドとなり、空間計算量は O(格納された合計キーバイト数) です。パス圧縮は疎な単項ノードを削減しますが、長いキーの処理を定数時間にするわけではありません。
- エッジケースのテスト。 空キーや1文字のキー、既存のキーのプレフィックスとなるキーの挿入、既存のキーを拡張するキーの挿入、エッジの途中での分割、重複の置換、リーフの削除、プレフィックス値の削除、唯一のキーの削除、および一致がない場合の最長プレフィックスクエリをテストします。
質の高い模範解答
エッジを空でないバイト文字列として表現し、先頭バイトで子を保持します。唯一自明でない操作は挿入です。子ラベルと残りのキーを比較し、最初の不一致箇所で分割します。この分割により共通プレフィックスノードが作成され、古いサフィックスとサブツリーが維持され、新しいサフィックスが付加されます。検索は完全なラベルを辿り、最長プレフィックス検索は値を保持する最も深いノードを記憶します。削除は値をクリアし、値を持たないノードをその唯一の子とマージします。以下は Go 風の擬似コードによるコアな分割ロジックです。
type node struct {
label string
value any
hasValue bool
child map[byte]*node
}
// When common is shorter than child.label:
parent := &node{label: common, child: map[byte]*node{}}
oldSuffix := child.label[len(common):]
child.label = oldSuffix
parent.child[oldSuffix[0]] = child
parent.child[newSuffix[0]] = &node{label: newSuffix, value: v, hasValue: true}本番のコードでは、newSuffix が空の場合に parent に値を格納するように処理し、hasValue が false でかつ子が1つだけの場合にのみ削除時のマージを行います。サンプルの検索が通ることだけを確認するのではなく、変更操作のたびに不変条件をテストします。
よくある間違い
- 基数木を1文字単位のトライノードとして扱う → パス圧縮が失われる → 空でないエッジラベルを格納し、ラベル全体を比較する。
- エッジを分割する際に古い値や子ノードを破棄してしまう → 既存のキーが失われる → 新しいサフィックスを付加する前に古いノードをそのサフィックスの下に移動する。
- 最長プレフィックス検索で最初に一致した値を返してしまう → より具体的なルートが無視される → 各値ノードで候補を更新し続ける。
- まだ値を保持しているノードをマージしてしまう → より短いキーが誤って削除される → 値を持たない単項ノードのみをマージする。
- 検索が O(1) であると主張する → それでもキーの比較が必要である → キー長に基づく O(k) を提示し、子マップのコストを説明する。
フォローアップ質問と回答
キーが大文字と小文字を区別しない場合、何が変わりますか？
ASCII 小文字化など、文書化された単一のルールを使用して、挿入および検索の前にキーを正規化します。検索時のみ正規化することは避けてください。さもないと、2つの表記が矛盾したパスを占有する可能性があります。Unicode のケースフォールディングと正規化は、別途明確に規定されたポリシーとする必要があります。
ワイルドカードを含むルートセグメントをどのようにサポートしますか？
明示的な優先順位ルールを追加します（例：静的エッジ ＞ パラメータエッジ ＞ キャッチオールエッジ）。基数木の不変条件はリテラルプレフィックスを処理しますが、マッチングはエッジ種別に対する探索になるため、ワイルドカード分岐の最大数を規定し、曖昧なルートをテストします。
ツリーを並行した読み取りおよび書き込みに対して安全にすることはできますか？
読者/著者ロック（Read-Write Lock）またはコピーオンライト（Copy-On-Write）スナップショットを使用します。ロックフリーを主張するにはメモリ回収（Memory Reclamation）の設計が必要です。ルートをアトミックにするだけでは、インプレースでの分割やマージを安全に行うことはできません。アルゴリズムの不変条件と同期ポリシーは明確に分離してください。