プロンプトと適用可能なコンテキスト
4つの操作を持つ単語のセットを格納する Trie を実装してください。
insert(word): 単語を追加します。単語が既に存在する場合はべき等です。search(word): その完全な単語が格納されているかどうかを返します。startsWith(prefix): そのプレフィックスパスが存在するかどうかを返します。空でないプレフィックスの場合、これは少なくとも1つの格納された単語がそのプレフィックスを持つことを意味します。delete(word): 完全な単語を削除し、それが存在していたかどうかを返します。
insert、search、および delete は、空でない英小文字の単語を受け取ると想定します。startsWith は空のプレフィックスも受け入れ、この API では挿入前であってもルートパスを空のプレフィックスとして定義するため、true を返します。実装はインメモリのシングルスレッドであり、サジェストの列挙、結果のランク付け、データの永続化、Unicode の正規化は行いません。入力の検証はクラスの外部で行われます。
これはソフトウェアエンジニアリング職の代表的なコーディング面接問題です。中心となるタスクは、共有プレフィックスをモデル化し、「このパスが存在する」ことと「ここで単語が終わる」ことを区別することです。削除を追加することで、候補者がそのモデルを真に理解しているかが明らかになります。app を削除しても apple は保持される必要があり、一方で最後のユニークなサフィックスを削除する際にはそのノードを回収できます。
面接官が評価するポイント
最初の評価シグナルは、操作からデータ構造を導出できるかです。ハッシュセットは完全一致のメンバーシップを処理できますが、プレフィックスクエリでは格納された単語を検査するか、別のインデックスを維持する必要があります。Trie は各プレフィックスをルートからのパスにするため、クエリのコストは格納されている単語の数ではなく、入力の長さに依存します。
2番目のシグナルは終端マーカーです。app のパスは apple を挿入した後に存在しますが、そのノードが完全な単語としてマークされるまで search("app") は false のままです。startsWith("app") はパスのみを必要とします。1つの走査ヘルパーで両方の操作に対応でき、それぞれの最終条件は区別されたままになります。
3番目のシグナルは削除の安全性です。終端マーカーをクリアするだけで論理的な削除としては十分です。物理的なプルーニング（刈り込み）は任意であり、子が終端でなく子ノードを持たない場合にのみ上方向へと進めることができます。このルールにより、削除されたパスを共有するより長い単語とより短い単語の両方が保持されます。
最後に、面接官は正確な計算量とテストケースを求めます。マップを使用したノードは、まばらなノードごとに26個の子スロットを割り当てるのを回避できますが、マップ操作は言語ランタイムの平均パフォーマンスの前提を使用します。また、削除では O(L) パススタックを保持します。補助空間が定数であると主張することはコードと矛盾します。
回答前に明確にすべき質問
- 使用可能な文字は何ですか？ 小文字の
a-zであれば、26スロットの配列が使用可能です。Unicode、大文字小文字の混在、またはまばらなアルファベットの場合はマップが適しており、正規化の取り決めが必要になる場合があります。 - 重複した挿入はカウントされますか？ この問題ではセットを格納するため、2回目の挿入はべき等です。マルチセットの場合は終端カウンターとプレフィックスカウンターが必要になります。
- 削除は何を報告すべきですか？ 存在しない単語には
falseを返し、格納されていた完全な単語が削除された場合にのみtrueを返します。 - 削除時にノードを回収する必要がありますか？ ここでは安全なプルーニングを行います。削除が稀でメモリの制約がない場合は、終端マーカーをクリアするだけでもシンプルかつ正確です。
- 空の単語は有効ですか？ いいえ。空のプレフィックスは許可されますが、このコントラクトでは空文字列を単語として挿入または検索することはできません。
- プレフィックスの結果は列挙しますか、それとも検出するだけですか？ この API はブール値を返します。一致するものをリスト化すると、サブツリーの走査と出力サイズに応じたコストが追加されます。
- 並行処理は必要ですか？ いいえ。並行した読み書きには、同期やイミュータブルなスナップショットの設計が必要になります。
30秒の回答フレームワーク
「各プレフィックスを1つのルートからのパスとして表現します。すべてのノードは次の文字を子ノードにマップし、isWord フラグを持ちます。Insert は欠落しているノードを作成し、最後のノードをマークします。Search はパスをたどってそのフラグをチェックし、プレフィックス検索はパスが存在することのみを要求します。Delete はまずパスを記録し、最後のフラグをクリアしてから、子を持たず他の単語の終端でもないノードのみを逆方向に削除します。各操作はマップを用いた子ノードで期待値 O(L) であり、総ストレージは O(C)、削除は O(L) の補助空間を使用します。」
ステップごとの詳細な回答
単語のリストやソートされていないセットでは、プレフィックスクエリが単語数に依存してしまいます。ソート済み配列は二分探索で最初のプレフィックス一致候補を見つけることができ、読み取りが中心の静的な辞書には魅力的ですが、挿入や削除にはシフトや再構築が必要です。Trie は文字ごとのノードオーバーヘッドを支払うことで、4つのオンライン操作すべてを直接サポートします。
以下の不変条件を使用します：
格納されたすべての単語について、その文字はルートからノードへのパスを形成し、ノードで isWord が true になるのは、そのノードを綴るパスが格納された完全な単語である場合と正確に一致する。
この不変条件がすべての操作を説明します。Insert は1つのパスを拡張し、その最後のマーカーをオンにします。Search はパスとマーカーの両方を必要とします。プレフィックス検索はパスのみを必要とします。Delete は正確に1つのマーカーをオフにし、残りの単語が使用できない場合にのみサフィックスを削除します。
class TrieNode {
readonly children = new Map<string, TrieNode>()
isWord = false
}
class Trie {
private readonly root = new TrieNode()
insert(word: string): void {
let node = this.root
for (const character of word) {
let child = node.children.get(character)
if (!child) {
child = new TrieNode()
node.children.set(character, child)
}
node = child
}
node.isWord = true
}
search(word: string): boolean {
return this.walk(word)?.isWord ?? false
}
startsWith(prefix: string): boolean {
return this.walk(prefix) !== undefined
}
delete(word: string): boolean {
let node = this.root
const path: Array<[TrieNode, string, TrieNode]> = []
for (const character of word) {
const child = node.children.get(character)
if (!child) return false
path.push([node, character, child])
node = child
}
if (!node.isWord) return false
node.isWord = false
for (let index = path.length - 1; index >= 0; index -= 1) {
const [parent, character, child] = path[index]
if (child.isWord || child.children.size > 0) break
parent.children.delete(character)
}
return true
}
private walk(text: string): TrieNode | undefined {
let node = this.root
for (const character of text) {
const child = node.children.get(character)
if (!child) return undefined
node = child
}
return node
}
}削除は、2つの反例を用いると最も簡単に検証できます。app と apple が格納されている場合、app を削除すると2番目の p のマーカーはクリアされますが、そのノードには子 l があるためプルーニングは停止します。apple は検索可能なままです。app と apt が格納されている場合、app を削除すると最後の p のみが削除され、共有されている ap ノードにはまだ子 t があるため、プルーニングはそこで停止します。
正しさは帰納法によって導かれます。空の Trie は不変条件を満たします。Insert は1つのパスとその最終マーカーのみを変更します。Search とプレフィックス検索は状態を変更しません。成功した削除は、まず対象のマーカーのみを正確に削除します。プルーニングされるすべてのノードは終端ではなく子も持たないため、格納された単語を表すことも、そこへ至ることもありません。それを削除しても、残りの格納されたすべてのパスは保持されます。最初の終端ノードまたは分岐ノードで停止することで、共有プレフィックスが保持されます。
L を入力の長さ、C を現在割り当てられている文字ノードの数とします。マップの平均的なルックアップにおいて、insert、search、およびプレフィックス検索の所要時間は期待値 O(L) です。Delete は前方に走査し、最大でも同じ L 個のエッジをプルーニングするため、これも期待値 O(L) です。Trie は O(C) の空間を使用し、これは格納された個別のプレフィックス文字の合計によって制限されます。delete のパスは O(L) の補助空間を使用します。
固定の英小文字アルファベットの場合、TrieNode | undefined[26] は直接的なインデックスアクセスと予測可能な1文字あたりの処理を提供しますが、ノードごとに26個の参照を予約します。マップは存在するエッジのみを格納し、ハッシュとオブジェクトのオーバーヘッドを伴いますが、より広いアルファベットに対応します。回答では、どちらか一方の表現が常に優れていると主張するのではなく、アルファベットと密度に基づいて選択する必要があります。
検証では、単一の検索だけでなく状態遷移も確認する必要があります。まず startsWith("") === true、search("") === false、および空の Trie からの削除から始めます。app、apple、および apt を挿入し、app を再挿入し、search("ap") と startsWith("ap") を区別し、apple を保持しながら app を削除し、2回目の削除を拒否し、その後残りの単語を削除してそれらのプレフィックスが消えることを確認します。ランダム化テストでは、単純な Set<string> リファレンスとすべての操作を比較し、プレフィックスクエリのためにセットをスキャンできます。
要件が完全一致のメンバーシップのみである場合は、ハッシュセットの方が短く、通常は好ましいです。辞書が静的でソートされている場合、二分探索を使用すればノードを多用するストレージなしでプレフィックスの存在に応答できます。長い単一の子チェーンがメモリを圧迫する場合、基数木（Radix Tree）はより複雑な分割とマージのロジックを犠牲にしてそれらのチェーンを圧縮します。
高品質な回答例
「まず、アルファベット、重複のセマンティクス、および削除時にメモリを回収する必要があるかどうかを確認します。ここでは空でない小文字の単語、セットのセマンティクス、一致する空のプレフィックス、および削除時の安全なプルーニングを前提とします。
各 Trie ノードは、外向きの文字エッジと終端フラグを格納します。ルートからノードへのパスはプレフィックスであり、フラグはその同じパスが完全に格納された単語でもあるかどうかを示します。Insert は欠落している子を作成し、最後のノードのみをマークします。Search は最後のフラグをチェックしますが、startsWith は走査が成功するかどうかのみをチェックします。
Delete では、単語をたどりながら各親、エッジ、および子を記録します。パスが存在しないか最後のノードが終端でない場合、状態を変更せずに false を返します。それ以外の場合は、マーカーをクリアして逆方向にたどります。子が子ノードを持たず、終端でもない場合にのみエッジを削除し、別の単語でまだ必要とされている最初のノードで停止します。これが、app を削除するときに apple をそのまま保持する仕組みです。
マップを用いた子ノードを使用する場合、すべての操作は期待値 O(L) です。総ストレージは O(C) 個の文字ノードであり、delete は O(L) のパススタックを使用します。空の場合や見つからないケース、重複した挿入、別の単語のプレフィックスである単語、分岐する2つの単語、最後の単語が削除された後の完全なプルーニングなどをテストします。もし完全一致検索が唯一の操作であるなら、代わりにハッシュセットを使用します。」
よくある間違い
- 到達可能なすべてのパスを単語として扱う →
appleのみを挿入した後にsearch("app")が true になる → 完全検索にはisWordを必須とする。 startsWithでisWordをチェックしてしまう → 別途挿入されない限り有効なプレフィックスが拒否される → パスが存在するときに成功を返す。- 削除中にパス全体をクリアまたは削除してしまう →
appを削除するとappleが破壊される → まず終端マーカーをクリアし、終端でない葉ノードのみをプルーニングする。 - 分岐ノードを超えてプルーニングしてしまう →
aptなどの無関係な単語が消える → 子ノードがまだ子を持っている場合は停止する。 - 別の終端ノードを超えてプルーニングしてしまう → より長い単語を削除すると、そのより短いプレフィックス単語が削除される → 子ノードが終端である場合は停止する。
- 削除パスが存在するだけで true を返す →
appleのみを挿入した後にappを削除すると、状態が変更されるか誤って報告される → 最後のノードが終端であることを必須とする。 - 誤って重複挿入をカウントしてしまう → セットのセマンティクスが隠れたマルチセットになってしまう → 1つのブールマーカーを使用するか、明示的にカウンターを使用するコントラクトに変更する。
- 4つの操作すべてが定数時間を使用すると主張する → 処理量は入力の長さに応じて増加する → 期待値
O(L)とマップの前提を述べる。 - 削除は余分な空間を使用しないと主張する → 実装では逆方向のプルーニングのためにパスを格納している →
O(L)の補助空間を報告するか、同じスタック境界を持つ妥当な再帰的代替手段を使用する。 - 常に26個の子を割り当てる → まばらなデータや Unicode データでは空間が無駄になるか、アルファベットの前提が崩れる → 文字セットを明確にした上で、配列かマップかを選択する。
- 完全一致検索のみに Trie を使用する → ノードのオーバーヘッドを支払って製品が決して使わないプレフィックス機能を得ることになる → 完全一致のメンバーシップだけならハッシュセットを優先する。
フォローアップの質問と回答
フォローアップ 1: 重複する単語と「1つだけ削除する」セマンティクスによって設計はどう変わりますか？
isWord を wordCount に置き換え、プレフィックスカウントが照会される場合はノードに prefixCount を保持します。Insert はパスに沿ってカウントをインクリメントします。Erase はまず wordCount > 0 を確認し、同じパスをデクリメントして、関連するカウントがゼロに達したときにのみプルーニングします。ブール値の実装では、1回の挿入と5回の挿入を区別できません。
フォローアップ 2: オートコンプリートの上位 K 件の結果を返すにはどうすればよいですか？
プレフィックスノードの検索には依然として O(L) のコストがかかりますが、そのサブツリーの列挙は出力サイズおよびサブツリーに依存します。クエリ数が少ない場合は、オンデマンドで走査してランク付けします。クエリ数が多い場合は、各ノードに制限付きのランク付けされた候補リストをキャッシュし、書き込み時に更新することで、追加のメモリと書き込み増幅と引き換えに読み取りレイテンシを削減します。ランキングスコアとタイブレークのルールを明示する必要があります。
フォローアップ 3: Unicode と大文字小文字を区別しないマッチングはどのように機能しますか？
表現を選択する前に正規化を定義します。たとえば、1つの Unicode 形式に正規化し、挿入時とクエリ時の両方でロケールに対応した大文字小文字のポリシーを適用します。合意された単位（コードポイントまたは書記素クラスタ）で反復処理を行い、マップを用いたエッジを使用します。クエリのみ、または挿入のみを正規化すると、決して一致しないパスが作成されてしまいます。
フォローアップ 4: Trie をスレッドセーフにするにはどうすればよいですか？
Trie 全体を1つの読み書きロック（Read-Write Lock）で囲むのが最もシンプルで正しい答えです。insert と delete は書き込みロックを取得し、search とプレフィックス検索は読み取りロックを取得します。より細かいノードロックには、固定の取得順序とプルーニングの慎重な保護が必要です。更新が稀な場合は、イミュータブルなスナップショットやコピーオンライトのルートを使用することでリーダーを単純化できます。
フォローアップ 5: メモリが制限要因である場合はどうしますか？
まずノード密度を測定します。固定配列はまばらなデータでメモリを圧迫する可能性があり、マップには独自のオブジェクトおよびハッシュのオーバーヘッドが伴います。基数木（Radix Tree）は単一の子チェーンを圧縮します。三次元探索木（Ternary Search Tree）は子ノードのストレージを削減します。最小決定性有限状態トランスデューサ/オートマトン（FST/FSA）構造は、静的な辞書をさらに圧縮できます。これらの選択により、更新の複雑さと実装のリスクが変わります。
フォローアップ 6: ワイルドカードや最長プレフィックスマッチングによって走査はどのように変わりますか？
最長プレフィックスマッチングは、最も深い終端ノードを記憶しながらクエリをたどるため、クエリの長さに対して線形のままです。. などのワイルドカードは、その位置にあるすべての子ノードに分岐するため、最悪ケースの処理量は探索されるサブツリーとともに拡大する可能性があります。API はワイルドカードの構文と、それが存在を返すのか、1つの結果を返すのか、すべての結果を返すのかを規定する必要があります。