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...

Source: DEV Community
π 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