如何實作 LRU-K 快取？
題目與使用情境
實作固定容量的 LRU-K 快取，支援 get、put 與淘汰。每個鍵記錄最近 K 次存取；存取次數不足 K 次的項目屬於歷史不足區，應先於「已熱」項目淘汰。需要說明 K、容量、更新既有鍵、並發呼叫與不存在鍵的行為。
面試官考察什麼
- 能否正確維護存取歷史與兩類候選集合。
- 是否能用堆、雜湊表或有序結構維持淘汰順序並分析複雜度。
- 能否處理重複寫入、容量為零、K 非法與並發可見性。
- 是否理解 LRU-K 的目標是過濾一次性掃描，不代表所有負載都更快。
作答前的釐清問題
確認是否要求執行緒安全、是否允許近似淘汰、值是否可變、是否需要 TTL，以及是否要統計命中率。若要求嚴格順序，通常需要鎖或序列化更新；若追求吞吐，可採用分片與近似策略。
30 秒回答框架
我會為每個鍵保存值、最近 K 次時間戳與版本。候選分為歷史不足區與已熱區：容量超限時先淘汰歷史不足區中最久未存取者，否則淘汰已熱區中第 K 近時間最小者。雜湊表負責 O(1) 定位，堆保存候選順序，更新堆時用版本號丟棄過期節點。嚴格實作的 get 與 put 期望 O(log n)，空間 O(capacity·K)。
分步驟深入解答
1. 記錄存取歷史
每次命中或寫入都追加邏輯時鐘值，並只保留最近 K 次。邏輯時鐘比牆上時間更適合比較順序，也避免同一毫秒存取難以區分。既有鍵的 put 應更新值並計為一次存取，除非題目明確要求寫入不計存取。
2. 維護淘汰候選
歷史不足區的排序鍵是最近一次存取時間；已熱區的排序鍵是第 K 近存取時間。兩個最小堆分別存 (key, version, rank)。鍵再次存取時插入新節點並增加版本，彈出時驗證版本與目前 rank，失效節點直接跳過。
3. 邊界與並發
容量為零或負數時不快取；K 為零或負數時應拒絕參數。淘汰與值更新必須在同一臨界區完成，避免兩個執行緒同時看到空位而超容量。分片鎖能提高吞吐，但跨分片的全域容量需要額外協調。
高品質示範回答
我先把項目分成歷史不足與已熱兩區。每個項目保存值、最近 K 次邏輯時間與版本；存取更新歷史後，把新排序節點壓入對應最小堆。淘汰時先檢查歷史不足堆，再檢查已熱堆，並用版本校驗跳過舊節點。這樣定位是雜湊表 O(1)，每次堆操作 O(log n)，空間為 O(capacity·K)。測試會涵蓋 K=1 與普通 LRU 等價、重複存取晉級、一次性掃描、覆寫、容量零、並發超容量、堆中失效節點與命中率。LRU-K 適合希望降低掃描污染的情境；Redis 的 LRU 是採樣近似，PostgreSQL 使用 clock-sweep，不能混淆三者的複雜度與效果。
常見錯誤
- 只維護一次存取時間，實際做成普通 LRU。
- 把第 K 近存取時間誤寫成最近一次存取時間。
- 直接刪除堆頂卻不處理重複節點，造成錯誤淘汰或記憶體洩漏。
- 允許並發
put突破容量，或在鎖外更新存取歷史。 - 宣稱 LRU-K 在所有負載下都優於 LRU。
追問及應對
K=1 時應該發生什麼？
每個項目第一次存取就進入已熱語意，淘汰鍵按最近一次存取排序，因此退化為普通 LRU 的排序規則。
如何降低堆節點的記憶體成本？
可用索引與可變堆減少重複節點，或採用分代佇列、採樣淘汰等近似方案，但要明確順序從嚴格變為近似，並重新測試命中率。
如何驗證一次性掃描污染是否降低？
建立循環熱點集合後插入大量只存取一次的鍵，比較 LRU 與 LRU-K 的熱點命中率、淘汰數量、延遲與記憶體占用；同時測試熱點集合大小接近容量的邊界。