問題と適用コンテキスト
正の整数 capacity に対する LRUCache(capacity) を実装してください。キーと値は非負の整数です。get(key) は格納されている値を返し、キーが存在しない場合は -1 を返します。put(key, value) はキーを挿入または更新します。成功した get とすべての put は、そのキーを最も最近使用された（most recently used）状態にします。キャッシュが満杯のときに新しいキーを挿入すると、最も古く使用された（least recently used）キーが正確に 1 つエビクトされます。両方の公開操作は、期待値 O(1) 時間で実行される必要があります。
これはデータ構造のコーディング問題であり、分散キャッシュの設計ではありません。実装はシングルプロセスかつシングルスレッドです。TTL、永続化、サイズに基づく重み付け、並行アクセスなどは含みません。「期待値 O(1)」は、ハッシュテーブル操作に関する通常の平均パフォーマンスの仮定に基づいています。連結リスト内のポインタ変更は最悪計算量 O(1) です。
重要な成果は、「ハッシュマップ＋双方向連結リスト」というフレーズを答えることではありません。完全な回答とは、なぜ両方の構造が必要なのかを導出し、マップとリストの不変条件を明示し、既存キーの更新時に誤ったエビクションを起こさずに処理し、各操作後の順序を検証することです。
面接官が評価するポイント
第 1 のシグナルは、要件を操作へと落とし込めているかです。キーはスキャンなしで見つけられる必要があるため、ハッシュマップが求められます。鮮度管理では、ヒットした任意の要素を最新の端へ移動し、最も古い端を削除できる必要があります。双方向連結リストなら、マップからノードが提供されていれば、その両方を定数回のポインタ操作で行うことができます。
第 2 のシグナルは、2 つの構造が 1 つの状態を形成しているかどうかです。マップは値だけを保持することはできず、各キーをそのリストノードにマップする必要があります。すべての実リストノードはマップ内に正確に 1 つのエントリを持ち、すべてのマップエントリはリスト内の正確に 1 つの実ノードを指している必要があります。したがって、エビクションでは両方の構造から同一のキーが削除されます。
第 3 のシグナルは、ポインタ操作の規律です。ダミーの head と tail ノードを設けることで、すべての実ノードを内部ノードとして扱うことができます。切り離しと挿入において、先頭、末尾、または唯一のエントリに対する特別な分岐が不要になります。候補者はコーディング前にどちら側が最新であるかを明言し、その規約を一貫して維持できる必要があります。
最後に、面接官は戻り値だけでなく、順序を検証するテストを確認します。満杯時の既存キーの更新、1 つのキーの連続読み取り、容量 1 のケース、ミス後の挿入などは、単純な正常系 1 回の例では見逃されるバグを浮き彫りにします。
回答前に確認すべき質問
getは鮮度を更新しますか？ 今回の契約では更新します。読み取り専用のpeekは別の操作であり、ノードを移動させません。- 既存キーの更新は容量を消費しますか？ いいえ。
putは同一エントリの値と鮮度を変更するものであり、他のキーをエビクトしてはなりません。 - ミス時には何を返しますか？ この問題では
-1を使用するため、値はその範囲外に制限されるか、API がオプショナルな値を返す必要があります。ここでは値は非負の整数であり、-1はミス時のために予約されています。 - 容量ゼロは有効ですか？ この実装では非正の容量を拒否します。ゼロをサポートする場合、すべての挿入が直ちに消失することになり、コンストラクタの契約が変わります。
- 保証は厳密な最悪ケース
O(1)である必要がありますか？ ハッシュテーブルは通常、期待定数時間を提供します。厳密な最悪ケースの保証には、別の検索構造またはより強い前提条件が必要です。 - 標準の順序付きマップ（ordered map）を使用できますか？ 本番環境や短い演習では許容されるかもしれませんが、面接官は依然として内部の連結リスト実装とその不変条件の説明を求めることがあります。
- スレッドセーフティは必要ですか？ いいえ。追加する場合、
getは鮮度を変更するため、同期の観点からは書き込み操作になることに留意してください。
30秒の回答フレームワーク
「期待定数時間の検索と鮮度更新が必要なため、各キーを双方向連結リストのノードにマップします。head 側を最新、tail 側を最古とし、番兵（sentinel）ノードを用いて切り離しと挿入を均一に処理します。ヒットまたは更新時はそのノードを先頭に移動します。容量を超えた新規挿入時は、両方の構造から tail.prev を削除します。マップとリストが同一の実ノードを保持するため、get と put は期待値 O(1)、空間計算量は O(capacity) となります。」
ステップバイステップの詳細な回答
リスト単体では鮮度を保持できますが、キーの検索や任意の要素の削除には O(n) がかかります。マップ単体では値を素早く検索できますが、スキャンするか 2 つ目の順序構造を持たない限り、最も古く使用されたキーを特定できません。配列＋マップの構成でも、O(n) のシフトや先行要素の特定が発生します。これら 2 つの要件から、検索インデックスと変更可能な順序構造が必然的に導かれます。
回答全体を通じて以下の向きを使用します。
head <-> most recent <-> ... <-> least recent <-> tail番兵ノードはマップに登録されることはなく、容量にもカウントされません。各実ノードは key、value、prev、next を保持します。エビクションは tail.prev から開始され、逆引きスキャンなしで一致するマップエントリを削除する必要があるため、ノードにキーを保持することが不可欠です。
以下の 4 つの不変条件により、実装の正しさをレビュー可能にします。
- キャッシュが空でない場合、
head.nextは最も最近使用された実ノードであり、tail.prevは最も古く使用された実ノードである。 - マップのキーと実リストノードは、同一のエントリ集合を一対一で表している。
- すべての隣接ペアにおいて、
left.next is rightかつright.prev is leftである。 - 各公開操作の終了後、
0 <= len(nodes) <= capacityである。
get と put の両方が真に共通して再利用するため、実装ではポインタ操作を 2 つのヘルパーにカプセル化します。
class Node:
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
if capacity <= 0:
raise ValueError("capacity must be positive")
self.capacity = capacity
self.nodes = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _detach(self, node: Node) -> None:
node.prev.next = node.next
node.next.prev = node.prev
def _attach_after_head(self, node: Node) -> None:
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _mark_recent(self, node: Node) -> None:
self._detach(node)
self._attach_after_head(node)
def get(self, key: int) -> int:
node = self.nodes.get(key)
if node is None:
return -1
self._mark_recent(node)
return node.value
def put(self, key: int, value: int) -> None:
node = self.nodes.get(key)
if node is not None:
node.value = value
self._mark_recent(node)
return
node = Node(key, value)
self.nodes[key] = node
self._attach_after_head(node)
if len(self.nodes) > self.capacity:
victim = self.tail.prev
self._detach(victim)
del self.nodes[victim.key]_attach_after_head におけるポインタ代入の順序は重要です。新しいノードがまず従来の先頭ノードを捉え、次にその従来のノードが新しいノードを逆向きに指し、その後に初めて head.next が変更されます。head.next を早く上書きしすぎると、prev の更新が必要な隣接ノードへの参照を見失う可能性があります。
正しさは操作に関する数学的帰納法によって導かれます。初期化時は 4 つの不変条件をすべて満たします。ミス時は何も変更されません。ヒットまたは既存キーの更新時は、マップされた 1 つのノードを切り離して先頭に再挿入するため、要素集合とサイズは変化しません。新しい挿入では両方の構造にノードを追加します。サイズが capacity + 1 になった場合、リストから tail.prev を削除し、マップからそのキーを削除することで、一対一の集合と容量制約が復元されます。正の容量が保証されているため、対象ノードは必ず実ノードです。
容量 2 の場合、トレース put(1,10)、put(2,20)、get(1)、put(3,30)、put(1,15) を実行すると、鮮度順は [1]、[2,1]、[1,2]、[3,1]、[1,3] となります。キー 2 はエビクトされますが、キー 1 の更新はその値を変更するのみで、キー 3 はエビクトされません。
ハッシュテーブルの平均的な性能のもとでは、各公開メソッドは 1 回の検索と固定回数のポインタおよびマップ操作を行うため、期待時間計算量は O(1) です。マップとリストは最大でも capacity 個の実ノードを保持するため、空間計算量は O(capacity) です。これは厳密な最悪ケースのハッシュテーブル保証ではありません。
検証では、例示トレースと不変条件チェックを組み合わせる必要があります。空のキャッシュでのミス、ゼロ容量の拒否、容量 1、異なるキーでの重複する値、満杯時の更新、連続ヒット、交互のエビクション、およびランダム操作の長いストリームをテストします。ランダムテストでは、結果と順序を単純な O(n) の参照モデルと比較し、すべての操作後に双方向ポインタ、重複ノードの不在、マップとリストの一致、および容量制約をアサートします。
ライブラリの使用が許可されている場合、アクセス順（access-ordered）マップを使用することで同じポリシーをより簡潔に表現できます。Java の LinkedHashMap はアクセス順と最古エントリ削除フックをサポートしています。これは本番環境では有用な選択肢ですが、面接での証明の代わりにはなりません。また、プロセス内の厳密な LRU と本番向けのエビクションを区別してください。サーバでは、グローバルなメタデータと競合を減らすためにサンプリングに基づく近似 LRU が使用されることがあります。
質の高い模範解答
「まず契約を確定させます。正の容量、ミス時に get は -1 を返し、すべてのヒットまたは put は鮮度を更新します。既存キーの更新はサイズを増やしません。目標はハッシュテーブルの平均検索に基づく期待値 O(1) です。
ハッシュマップはキー検索を解決しますが、エビクション順序は解決しません。双方向連結リストは順序を解決し、該当ノードをすでに保持していれば定数回のポインタ操作で任意のノードをリンク解除できます。したがって、マップには key -> node を格納し、ダミー head の直後の最新からダミー tail の直前の最古へとノードを順序付けます。tail からのエビクション時にマップエントリも削除できるよう、ノードには自身のキーを保持させます。
重要な不変条件は、マップと実リストノードが同一の集合であることです。ヒット時にはそのノードを切り離して head の直後に挿入します。更新時には値を変更して同様に移動します。新規 put 時には両方の構造に追加し、サイズが容量を超えた場合は両方から tail.prev を削除します。番兵ノードのおかげで、これらは先頭、末尾、唯一のエントリに対しても同一の操作になります。
テストとしては、容量 1、満杯時の更新、エビクション対象が変わる連続 get、順序を変えてはならないミスなどを確認します。また、ランダム操作ごとにリストを走査し、低速な参照モデルと比較します。最終的な計算量は、操作あたり期待値 O(1)、空間計算量は O(capacity) です。」
よくある間違い
- マップに値のみを格納する → ヒット時に依然として順序構造を探索する必要が生じる → 各キーを直接そのリストノードにマップする。
- 単方向連結リストを使用する → マップからノードは得られるが先行ノードが得られないため、任意のノード削除にスキャンが必要になる場合がある →
prevとnextの両方を保持する。 - 各ノード内のキーを保持し忘れる → tail からのエビクション時に逆引きなしでマップエントリを削除できなくなる → ノード内にキーと値の両方を保持する。
- 挿入順序を鮮度として扱う → 成功した
getが将来のエビクション対象を変更できなくなる → ヒットした要素はすべて最新の端へ移動する。 - 既存キーの更新時にエビクトしてしまう → サイズは増加していないため無関係なエントリが消失する → 新規エントリの容量チェックの前に更新と return を処理する。
- 一方の構造からのみ対象を削除する → 古いマップエントリやゴースト化したリストノードが以降の操作を破壊する → エビクションは両方対称に行い、マップとリストの一致をテストする。
- head、tail、単一要素の分岐を個別に書く → ポインタのケースが増加し、いずれかの境界で不整合が生じる → 永続的な 2 つの番兵ノードを使用する。
- 厳密な
O(1)を主張する → ハッシュテーブルは一般に期待値の保証であり、衝突により劣化する可能性がある → ハッシュに関する前提条件を明記する。 - 戻り値のみをテストする → 正しい値が返っていても順序の破損が隠蔽され、後のエビクションまで表面化しないことがある → 完全な鮮度シーケンスとポインタ不変条件をアサートする。
フォローアップの質問と回答
フォローアップ 1: スレッドセーフにするにはどうしますか？
get はリストを変更するため書き込み操作です。最もシンプルな正しい拡張は、get または put 全体を 1 つのミューテックスで保護し、マップとリストの更新をアトミックに保つことです。読み取り/書き込みロック（RWLock）を使用しても、通常のヒット操作をリーダー（読み取り）にすることはできません。シャーディングは競合を減らしますが、各シャードが独自の LRU 順序を持つことになり、共有の順序付け機構を再導入しない限り、厳密なグローバル LRU 1 つを実装することにはならなくなります。
フォローアップ 2: TTL（生存時間）による有効期限を追加するにはどうしますか？
TTL と鮮度は別個のエビクションルールです。ヒット時はまず期限切れエントリを拒否する必要があり、put では容量ポリシーを適用する前に期限切れエントリの削除が必要になる場合があります。有効期限の最小ヒープを使用すると遅延クリーンアップが可能になりますが、O(log n) の維持コストと古いヒープレコードが発生します。タイミングホイール（timing wheel）を用いると精度と実装が変わります。有効期限機構と計算量の境界を再定義することなく、両方の操作が依然として O(1) であると主張し続けないようにしてください。
フォローアップ 3: 厳密な最悪ケース O(1) を提供できますか？
連結リスト部分はすでに厳密に定数回のポインタ操作となっています。検索部分はハッシュテーブルの保証に依存します。厳密な最悪ケース定数時間の検索を実現するには、より強力な辞書モデル、直接アドレス指定が可能な制限されたキー空間、または特殊なハッシュの前提が必要です。通常のプログラミング言語のハッシュマップでは、その実装の契約に従って期待値または償却 O(1) として結果を説明してください。
フォローアップ 4: なぜ LinkedHashMap や OrderedDict を使用しないのですか？
アクセス順序とエビクションのセマンティクスがプロダクト要件に合致し、手動のポインタコードを書くメリットがない場合は、ライブラリを使用してください。面接では、まず基礎となるマップと連結順序の不変条件を説明し、その上でライブラリという代替案を提示します。更新、読み取り、反復処理、および最古要素の削除がアクセスとしてカウントされるかどうかを確認してください。似た名前の順序付きマップであっても、すべてが同一の鮮度セマンティクスを持つわけではありません。
フォローアップ 5: 大規模なキャッシュサーバで厳密な LRU を使用しますか？
無条件には使用しません。1 つの厳密なグローバルアクセス順序を維持することは、メタデータの書き込みを増やし、すべてのヒット時に競合ポイントを生み出します。本番のキャッシュでは、順序をシャード化したり、候補キーをサンプリングしたり、頻度による再利用予測がより適している場合は LFU を選択したりすることがあります。これらの選択肢は、メモリやスループットのために厳密な対象選定とトレードオフを行います。面接で扱うこのデータ構造は、厳密なポリシーとその不変条件をテスト可能にするという点で依然として有用です。