Implement LFU using LRU

📌 Core Idea LFU (Least Frequently Used) means: Remove the least frequently used key If multiple keys have same frequency → remove least recently used (LRU) 📦 Data Structures Used We maintain: key → node (for O(1) access) freq → doubly linked list (group nodes by frequency) minFreq (track minimum frequency in cache) 🧱 Structure Visualization Freq = 1 → [ most recent .... least recent ] Freq = 2 → [ most recent .... least recent ] Freq = 3 → [ most recent .... least recent ] Each frequency has its own LRU list 🚀 Example Walkthrough Capacity = 2 Step 1: put(1,10) Freq 1: [1] minFreq = 1 Step 2: put(2,20) Freq 1: 2, 1 minFreq = 1 Step 3: get(1) Access key 1 Increase its frequency: 1 → 2 Freq 1: [2] Freq 2: [1] minFreq = 1 👉 We removed 1 from freq 1 and added to freq 2 Step 4: put(3,30) Cache is FULL → eviction needed minFreq = 1 Look at Freq 1 → [2] 👉 Remove 2 After insertion: Freq 1: [3] Freq 2: [1] minFreq = 1 Step 5: get(3) Move 3 from freq 1 → freq 2 Freq 1: [] Freq 2: [3, 1] min