プロンプトとコンテキスト
get、put、および立ち退きをサポートする有界なLRU-Kキャッシュを実装してください。キーごとに最新K件のアクセス履歴を保持します。アクセス回数がK回未満のエントリは履歴不完全ティアを形成し、ホットなエントリよりも先に立ち退かせる必要があります。K、容量、既存キーの更新、並行呼び出し、および存在しないキーの扱いを明確にしてください。
面接官がテストしていること
- アクセス履歴と2つの候補ティアを正しく維持できるか。
- ヒープ、ハッシュマップ、または順序付き構造を選択し、コストを分析できるか。
- 上書き、容量ゼロ、無効なK、および並行処理の可視性を適切に処理できるか。
- LRU-Kがすべてのワークロードで勝るわけではなく、スキャン汚染をフィルタリングするものであることを理解しているか。
回答前の明確化のための質問
スレッドセーフ性、近似立ち退き、ミュータブルな値、TTL要件、およびヒット率の指標を確認します。厳密な順序付けには通常ロックやシリアライズされた更新が必要ですが、より高いスループットにはシャーディングや近似ポリシーが必要になる場合があります。
30秒の回答フレームワーク
キーごとに値、最新K個の論理タイムスタンプ、およびバージョンを保存します。候補を履歴不完全ティアとホットティアに分割します。容量を超過した場合は不完全ティアの最も古いアイテムを立ち退かせ、それ以外の場合はK番目に新しいタイムスタンプが最も小さいホットアイテムを立ち退かせます。ハッシュマップによりO(1)の検索が可能になり、ヒープで候補を維持します。バージョン情報によって古いヒープノードを破棄します。厳密なgetとputはO(log n)が期待され、履歴の空間計算量はO(capacity·K)となります。
ステップバイステップの詳細解説
1. アクセス履歴の記録
ヒットまたは書き込みごとに論理クロック値を追加し、最新のK個の値のみを保持します。論理クロックはウォールクロックのジャンプなしに順序を比較し、同一ミリ秒内のアクセスを区別します。プロンプトで書き込みはカウントしないと明記されていない限り、上書きもアクセスとしてカウントします。
2. 立ち退き候補の維持
不完全ティアは最新のアクセス順で並べられ、ホットティアはK番目に新しいアクセス順で並べられます。(key, version, rank)の2つの最小ヒープ（min-heap）を維持します。新しいアクセスがあると新しいノードがプッシュされてバージョンがインクリメントされ、立ち退き処理ではバージョンと現在のランクを検証して古いノードをスキップします。
3. 境界条件と並行性
容量がゼロまたは負の場合はキャッシュを行わず、Kがゼロまたは負の場合は拒否します。並行するputの呼び出しが容量を超えないようにするため、立ち退きと値の更新はクリティカルセクションを共有する必要があります。シャーディングされたロックはスループットを向上させますが、その場合グローバルな容量の調整が必要になります。
質の高い模範解答
エントリを履歴不完全ティアとホットティアに分離します。各エントリには値、最新K個の論理時間、およびバージョンが格納されます。アクセスがあると履歴が更新され、関連する最小ヒープに新しいランクノードがプッシュされます。立ち退き処理では不完全ヒープを先にチェックし、次にホットヒープをチェックして、バージョンを検証することで古いノードをスキップします。マップによる検索はO(1)、ヒープ操作はO(log n)、履歴の空間計算量はO(capacity·K)です。テストでは、K=1の時にLRUとして動作すること、繰り返しのアクセスによる昇格、1回限りのスキャン、上書き、容量ゼロ、並行処理での容量超過書き込み、古いヒープノード、およびヒット率をカバーします。LRU-Kはスキャン汚染対策を対象としています。RedisはサンプリングされたLRU近似を使用し、PostgreSQLはクロックスイープを使用するため、それらのコストと挙動を混同すべきではありません。
よくある間違い
- タイムスタンプを1つしか保持せず、誤って通常のLRUを実装してしまうこと。
- 最新のアクセスをK番目に新しいアクセスとして扱ってしまうこと。
- 重複した古いノードを処理せずにヒープのルートを削除してしまうこと。
- 並行する
putの呼び出しで容量を超過させたり、ロックの外で履歴を更新してしまったりすること。 - LRU-Kが常にLRUに勝ると主張すること。
フォローアップの質問と回答
Kが1に等しい場合はどうなりますか？
最初のアクセスでエントリにホットなセマンティクスが付与されるため、立ち退きは最新のアクセス順となり、ポリシーは通常のLRUの順序に帰着します。
ヒープノードのメモリをどのように削減できますか？
インデックスとミュータブルなヒープを使用して重複ノードを削減するか、世代別キューやサンプリングによる立ち退きを選択します。順序付けが近似的になることを明記し、ヒット率を再測定します。
スキャン汚染の低減をどのように測定しますか？
循環するホットなセットを作成し、1回だけアクセスされる多数のキーを挿入します。容量に近いホットセットを含め、ホットセットのヒット率、立ち退き回数、レイテンシ、およびメモリについてLRUとLRU-Kを比較します。