問題と範囲
固定容量の LFUCache を実装します。キーが存在する場合、get(key) はその値を返し、アクセス頻度をインクリメントします。存在しない場合は -1 を返します。put(key, value) は新しいキーを挿入するか、既存の値を変更します。既存のキーの更新も 1 回のアクセスとしてカウントされます。新しいキーは頻度 1 から開始します。満杯のキャッシュに挿入する場合は、最も頻度の低いキーを削除します。複数のキーが同じ頻度を共有している場合は、その中で最も古く使用されたキーを削除します。
get と put の両方は、ハッシュマップの通常の平均性能の仮定のもとで、期待計算量 O(1) で動作する必要があります。容量 0 も有効であり、すべての put は何もしない操作（no-op）になります。スコープはシングルスレッドのインメモリデータ構造です。TTL、バイトベースの容量制限、永続化、分散整合性は除外されます。
2025年12月の中国の公開面接記録には LFU Cache が明示的に記載されており、2026年の公開面接ページでも同じ問題が維持されています。LeetCode 460 が安定した仕様を提供し、O(1) LFU の原著論文が 2 レベルの連結構造を文書化しています。これは、個別に検証された特定の企業への帰属を確定することなく、この問題の現在の代表性を裏付けるものであるため、companyName は null のままとなります。
面接官が評価するポイント
第一に、候補者が 2 つのエビクション基準からデータ構造を導き出せるか。キーの検索にはハッシュマップが必要です。頻度による選択には頻度インデックスが必要です。同じ頻度のキーにはさらに新旧（recency）の順序が必要です。単一のヒープでも最低頻度を見つけることはできますが、アクセスのたびに優先度が変化し、通常 O(log capacity) のコストがかかります。
第二に、候補者が不変条件を明確に述べられるか。すべてのキーは正確に 1 つのノードを指す必要があります。すべてのノードは、その頻度に一致する正確に 1 つのバケットに属している必要があります。各バケットは最も新しいものから最も古いものの順に並んでいます。minFrequency は現在存在する最小の頻度を特定しなければなりません。「2つのマップと双方向連結リスト」と暗記した内容を唱えるだけでは、空バケットの削除、更新、容量 1 の挙動を説明できません。
第三に、タイブレーク（同点処理）が正しく保たれているか。ノードが頻度 f から f + 1 に移動するとき、トリガーとなったアクセスが発生したばかりであるため、そのノードは新しいバケットの最も新しい側（先頭）に入ります。エビクションは最小頻度バケットから最も古いノードを削除します。順序のないセット（unordered set）では LFU の第 1 ルールは満たせても、LRU によるタイブレークが失われます。
最後に、面接官は計算量の証明とテスト戦略を期待しています。各操作は、定数個のマップ操作、バケット検索、連結リストの変更のみを実行しなければなりません。テストには、頻度の重複、古い最小バケットが空になるケース、既存キーの更新、容量ゼロ、および長いランダムシーケンスに対する低速な参照モデルとの差分比較を含める必要があります。
回答前の確認事項
- 既存のキーを更新すると頻度はインクリメントされますか？ はい。値を変更した後、
putは成功したgetと同じプロモーションパスを使用します。 - 頻度が同じ場合はどのように解決されますか？ その頻度内での LRU によって解決されます。最後に成功した
getまたは更新のputが最も古いキーを削除します。 - 新しいキーの初期頻度は 0 ですか、それとも 1 ですか？ 挿入自体が 1 回の使用としてカウントされるため、1 から始まります。
- 容量 0 は有効ですか？ はい。すべての
putは即座にリターンし、すべてのgetはミスになります。 - 目標は厳密な最悪計算量 O(1) ですか？ 連結リストの変更は最悪でも定数時間です。通常のマップは平均または期待定数時間の保証を提供するため、全体の主張は期待計算量
O(1)となります。 - 頻度は無制限に増加する可能性がありますか？ 面接の実装では通常、整数が安全な範囲にとどまると仮定します。長期稼働する本番キャッシュではオーバーフロー、エージング、または再正規化を定義する必要があり、仕様が変わります。
- キャッシュはスレッドセーフである必要がありますか？ いいえ。
getが頻度と順序を変更するため、並行バージョンでは複数構造の更新を 1 つのクリティカルセクションにする必要があります。
30秒の回答フレームワーク
「キーからノードへのマップと、頻度から双方向連結リストへのマップの 2 つを使用します。各リストには同じ頻度のノードのみが含まれ、先頭が最も新しく、末尾が最も古い順序になります。minFrequency は削除対象のバケットを直接特定します。get の成功または更新を伴う put では、ノードを頻度 f から削除し、必要に応じて空になった古いバケットを削除し、頻度をインクリメントして新しいバケットの先頭にノードを挿入します。新しいキーの場合、キャッシュが一杯であれば minFrequency バケットの末尾ノードを削除し、新しいノードを頻度 1 に追加して最小値を 1 に設定します。すべてのステップは定数個のマップおよびポインタ操作を使用するため、get と put は期待計算量 O(1)、空間計算量は O(capacity) となります。」
ステップごとの解決策
ステップ 1: 計算量要件を満たさない直接的なアプローチを排除する
key から {value, frequency, lastUsed} へのマップが 1 つだけの場合、エビクション時にすべてのキーを走査するため O(capacity) のコストがかかります。最小ヒープを使用するとエビクションは O(log capacity) に削減されますが、アクセスが成功するたびに頻度と新旧の両方が変化するため、位置インデックスとヒープの再構成が必要になります。(frequency, time) でソートされた平衡木も O(log capacity) のコストがかかります。
期待計算量 O(1) を実現するには、順序の管理を分離する必要があります。マップによって頻度を直接特定します。双方向連結リストは同一頻度のノード間でのみ新旧の順序を維持し、既知のノードに対する削除、先頭への挿入、末尾からの削除をサポートします。1 つの整数変数で現在の最小頻度を記録します。
ステップ 2: 4 つの不変条件を定義する
nodes内のすべてのキーは正確に 1 つの実ノードを指し、すべての実ノードはnodesに現れる。- 頻度
fを持つノードはfrequencyLists.get(f)にのみ現れ、マップは空のリストを保持しない。 - すべての頻度リストは、先頭が最も新しく使用されたもの、末尾が最も古く使用されたものとして並んでいる。
- キャッシュが空でないとき、
minFrequencyは全ノードの最小頻度であり、キャッシュが空のときは 0 である。
1 回の昇格（promotion）では、ノードは f から f + 1 へとしか移動しません。f が最小値であり、そのバケットが空になった場合、新しい最小値は正確に f + 1 になります。それより低いバケットは存在せず、昇格したノードによって f + 1 のバケットが存在することが保証されるためです。新しく挿入されたノードの頻度は 1 であるため、挿入によって minFrequency は直接 1 にリセットされます。
ステップ 3: ノードと頻度リストの実装
双方向連結リストでは、空、1 ノード、端点のケースで別個の分岐を避けるためにヘッドとテールの番兵（sentinel）を使用します。ノードには自身のキーが格納されているため、逆引き検索を行うことなく nodes から一致するエントリを削除してエビクションを実行できます。
class Entry {
frequency = 1
prev: Entry | null = null
next: Entry | null = null
constructor(
readonly key: number,
public value: number,
) {}
}
class FrequencyList {
private readonly head = new Entry(0, 0)
private readonly tail = new Entry(0, 0)
size = 0
constructor() {
this.head.next = this.tail
this.tail.prev = this.head
}
addFirst(node: Entry): void {
node.prev = this.head
node.next = this.head.next
this.head.next!.prev = node
this.head.next = node
this.size += 1
}
remove(node: Entry): void {
node.prev!.next = node.next
node.next!.prev = node.prev
node.prev = null
node.next = null
this.size -= 1
}
removeLast(): Entry {
const node = this.tail.prev
if (!node || node === this.head) {
throw new Error("cannot remove from an empty frequency list")
}
this.remove(node)
return node
}
}番兵はキャッシュエントリではなく、nodes には現れず、容量としてもカウントされません。remove はそのリストに現在存在する実ノードのみを受け入れます。LFUCache の不変条件によってこの事前条件が確立されます。
ステップ 4: 昇格、読み取り、書き込みの実装
class LFUCache {
private readonly nodes = new Map<number, Entry>()
private readonly frequencyLists = new Map<number, FrequencyList>()
private minFrequency = 0
constructor(private readonly capacity: number) {
if (!Number.isInteger(capacity) || capacity < 0) {
throw new RangeError("capacity must be a non-negative integer")
}
}
get(key: number): number {
const node = this.nodes.get(key)
if (!node) return -1
this.promote(node)
return node.value
}
put(key: number, value: number): void {
if (this.capacity === 0) return
const existing = this.nodes.get(key)
if (existing) {
existing.value = value
this.promote(existing)
return
}
if (this.nodes.size === this.capacity) {
const victimList = this.frequencyLists.get(this.minFrequency)
if (!victimList) throw new Error("missing minimum-frequency list")
const victim = victimList.removeLast()
this.nodes.delete(victim.key)
if (victimList.size === 0) {
this.frequencyLists.delete(this.minFrequency)
}
}
const node = new Entry(key, value)
this.getOrCreateList(1).addFirst(node)
this.nodes.set(key, node)
this.minFrequency = 1
}
private promote(node: Entry): void {
const oldFrequency = node.frequency
const oldList = this.frequencyLists.get(oldFrequency)
if (!oldList) throw new Error("missing source frequency list")
oldList.remove(node)
if (oldList.size === 0) {
this.frequencyLists.delete(oldFrequency)
if (this.minFrequency === oldFrequency) {
this.minFrequency = oldFrequency + 1
}
}
node.frequency = oldFrequency + 1
this.getOrCreateList(node.frequency).addFirst(node)
}
private getOrCreateList(frequency: number): FrequencyList {
let list = this.frequencyLists.get(frequency)
if (!list) {
list = new FrequencyList()
this.frequencyLists.set(frequency, list)
}
return list
}
}既存キーの処理分岐は容量チェックの前に実行する必要があります。エントリ数は増加せず、無関係なキーを削除してはなりませんが、ノードを昇格させて新しいバケット内での新旧順序を更新します。新しいキーの場合、エビクションは挿入の前に行われ、その時点では minFrequency が依然として削除対象のバケットを特定しています。
ステップ 5: 正当性と計算量の証明
初期化後、4 つの不変条件はすべて保持されます。ミスによって状態が変化することはありません。アクセスが成功すると、正しい古いバケットから 1 つのノードが削除され、その同じノードが新しい頻度とともに新しいバケットの最も新しい側（先頭）に挿入されます。要素の所属（存在有無）は変化せず、バケットの割り当てと新旧順序が更新され、空になった最小バケットの処理によって正しい最小値が維持されます。
既存のキーを更新する場合、同じ昇格処理を実行する前に値のみを変更します。挿入時にキャッシュが一杯である場合、最小頻度バケットの末尾ノードは両方のエビクションルールを満たします（最も頻度が低く、その頻度の中で最も古い）。それをリストおよび nodes から削除することで、1対1の所属不変条件が維持されます。新しいノードは頻度 1 の最も新しい側に入り、minFrequency = 1 によってすべての不変条件が復元されます。
各メソッドは、一定回数のマップ検索、挿入、または削除と、一定回数の連結リストのポインタ変更のみを実行します。マップの平均性能の仮定のもとで、get と put は両方とも期待計算量 O(1) となります。すべての実ノードは 1 つのキーマップと 1 つのリストに存在し、バケットの数がノード数を超えることはないため、空間計算量は O(capacity) です。
ステップ 6: トレースと差分テストによる検証
容量 2 の場合、次のシーケンスを実行します：
put(1, 10) -> key 1 has frequency 1
put(2, 20) -> keys 1 and 2 tie; 2 is newer
get(1) -> returns 10; key 1 moves to frequency 2
put(3, 30) -> evicts key 2 at frequency 1
get(3) -> returns 30; key 3 moves to frequency 2 and is newer than 1
put(4, 40) -> keys 1 and 3 tie; evicts older key 1テストセットには、容量 0 および 1、状態を変更しないミス、既存キーの更新、最小バケットを空にする連続昇格、および同一頻度キー間での繰り返される新旧順序の変更も含める必要があります。より強力な検証として、全探索で削除対象を探す O(capacity) 参照モデルを実装し、決定論的なランダム操作ストリームに対してすべての get の結果と最終的に可視な key-value 状態を比較します。これにより、長いトレースの後にのみ現れる可能性のある minFrequency のズレや壊れたリストポインタを検出できます。
質の高い模範解答
「まず仕様を確認します。新しいキーの頻度は 1、get の成功および更新を伴う put は頻度をインクリメントし、同一頻度の場合は LRU を適用し、容量 0 も有効です。目標は通常のマップの挙動のもとでの期待計算量 O(1) です。
key -> node、frequency -> doubly linked list、および minFrequency を保持します。ノードにはキー、値、頻度、リストリンクが格納されます。同一頻度内では、先頭が最も新しく、末尾が最も古くなります。ヒット時には、バケット f からノードを切り離し、空になった場合は古いバケットを削除します。そのバケットが最小頻度であった場合は、最小頻度を f+1 に進めます。その後、バケット f+1 の先頭にノードを挿入します。
put については、既存のキーは値を変更し、エビクションなしで昇格します。満杯のキャッシュへの新しいキーの挿入では、最小頻度バケットの末尾ノードを削除し、そのキーインデックスを削除します。その後、新しいノードを頻度 1 に挿入し、最小頻度を 1 にリセットします。主要な不変条件は、ノードごとに 1 つのキー、ノードごとに 1 つの正しいバケット、各バケット内での新旧順序、および正確な最小頻度です。すべてのステップは定数個のハッシュおよびポインタ操作を使用し、空間計算量は容量に対して線形です。
テストとしては、容量 2 のタイブレークのトレース、容量 0 と 1、既存キーの更新、空になった最小バケットをテストし、全探索モデルに対する決定論的な差分テストを実行します。本番向けの拡張には、頻度のエージング、オーバーフロー、並行性、TTL に関する個別の仕様が必要であり、これらを現在の計算量の主張にそのまま含めることはできません。」
よくある間違い
key -> frequencyのみを保持する → エビクション時に依然としてすべてのキーを走査することになる → 最小頻度バケットを直接追跡する。- 各頻度バケットで順序のないセットを使用する → 同一頻度の中で最も古いキーが不明になる → バケットごとに双方向連結 LRU リストを維持する。
- 昇格したノードを末尾に追加する → アクセスされたばかりのキーが最も古いものになってしまう → 昇格したノードは最も新しい側（先頭）に挿入する。
- 空になった古いバケットを保持し続ける →
minFrequencyが削除対象のない場所を指す可能性がある → 空のバケットを削除し、必要に応じて最小頻度を進める。 - 既存キーの処理前に容量をチェックする → サイズが増加していないにもかかわらず無関係なエントリが削除される → 先に更新、昇格、リターンを行う。
- 削除対象をリストからのみ削除する → キーマップにゴーストノードが残る → 両方の構造から同じキーを削除する。
- 挿入後に最小頻度をリセットし忘れる → 以降のエビクションで頻度 1 がスキップされる可能性がある → 新しいキーごとに 1 に設定する。
- ヒープによる解決策を O(1) と呼ぶ → アクセスによって引き起こされる優先度の変更にはヒープの再構成が必要 →
O(log capacity)を受け入れるか、頻度バケットを使用する。 - 厳密な O(1) と主張する → 通常のマップは平均ハッシュ性能に依存する → 期待計算量 O(1) と述べる。
- 公開されているサンプルのみを実行する → 空バケットやタイブレーク順序のズレが見逃される → 不変条件チェックとランダムな差分テストを追加する。
フォローアップの質問
フォローアップ 1: 最小バケットが空になったとき、なぜ minFrequency は正確に 1 だけ増加するのですか？
ノードは f から f + 1 へとしか移動しません。f が現在の最小値であり、その古いバケットが空になった場合、他のすべてのノードはすでに少なくとも f + 1 の頻度を持っており、昇格したノードによって f + 1 のバケットが存在することが保証されます。したがって、新しい最小値は正確に f + 1 となり、上方向への探索は不要です。エビクションの直後に新しい挿入が続く場合は、どのみち最終的な最小値は 1 にリセットされます。
フォローアップ 2: TTL はどのように追加しますか？
TTL は有効期限に基づく第 2 の順序を導入します。ヒット時に有効期限をチェックする必要があり、容量によるエビクションでは期限切れのエントリを優先して削除する場合があります。最小ヒープで有効期限を順序付けることができますが、更新や削除は通常 O(log n) になります。タイミングホイールは一部のコストを削減しますが、精度と状態のトレードオフが発生します。有効期限と LFU のどちらが優先されるかを定義し、計算量を再説明します。
フォローアップ 3: 頻度が長期間増加し続けると何が起こりますか？
カウンタがオーバーフローする可能性があり、過去に頻繁にアクセスされたキーがキャッシュを無期限に占有し続ける可能性があります。選択肢としては、定期的な減衰、グローバル最小値がしきい値を超えたときの再正規化、または時間減衰を伴う近似ポリシーなどがあります。完全な再正規化は、時折 O(n) のタスクを発生させます。安定したレイテンシを実現するには、インクリメンタルな移行または償却された仕様が必要であり、厳密な通算カウントとのセマンティクスの違いを明示する必要があります。
フォローアップ 4: どのようにスレッドセーフにしますか？
最もシンプルな正しい拡張は、完全な get および put のそれぞれを 1 つのミューテックスで囲むことです。成功した読み取りによってノード、2 つのバケット、および最小値が変更されるためです。シャーディングは競合を減らしますが、各シャードが独立したエビクションポリシーを持つことになり、厳密なグローバル LFU とは異なります。きめ細かいロック（fine-grained locking）を行う場合は、キーインデックス、古いバケット、新しいバケットに対する固定の順序を定義し、エビクションと昇格がインターリーブしないようにする必要があります。
フォローアップ 5: LFU は常に LRU より優れていますか？
アクセスの分布に依存します。LFU は繰り返しアクセスされる長期的なホットキーを維持しますが、過去のホットキーがコールドになった場合の適応が遅くなります。LRU はワーキングセットの変化により迅速に反応し、実装も小さくなります。本番環境のキャッシュでは、エージング、アドミッション制御、または近似ポリシーを組み合わせることがよくあります。面接の実装は複合的なエビクションルールを的確に練習するためのものであり、すべてのワークロードに対して純粋な LFU を推奨するものではありません。
フォローアップ 6: 既存の動的 Top-K 頻度バケットを変更せずに再利用できないのはなぜですか？
動的 Top-K はカウント順に結果を列挙するだけであり、通常は同一カウント間の順序を指定しないままにできます。このキャッシュは容量制限時に正確にエビクションを行う必要があり、LRU によるタイブレークが求められるため、すべてのバケットに新旧順序が必要であり、アクセスのたびにそれを更新する必要があります。どちらの構造も頻度バケットを使用しますが、インターフェース、不変条件、および正当性の目標が異なります。