Solving LFU Cache Implementation in Python: Step-by-Step Guide

The Least Frequently Used (LFU) cache is a classic caching eviction strategy that removes the item with the smallest access frequency when the cache reaches its capacity. Unlike LRU, which only considers recency, LFU tracks how often each item is accessed, making it ideal for workloads where popular items should stay cached longer. In this tutorial, you will build a fully working LFU cache in Python from scratch, understand the underlying data structures, and learn best practices for production-grade implementations.

What Is an LFU Cache?

An LFU cache is a key-value store with a fixed capacity. When a new item needs to be inserted and the cache is full, the cache evicts the item that has been accessed the fewest times. If multiple items share the same minimum frequency, the cache evicts the least recently used among them — this tie-breaker prevents stale items from lingering forever.

The LFU cache typically supports two core operations:

get(key) — Returns the value associated with the key, increments its access frequency, and returns -1 if the key does not exist.
put(key, value) — Inserts or updates the key-value pair. If the cache is at capacity and a new key is inserted, the least frequently used item is evicted first.

Both operations should run in O(1) average time, which is the main challenge of this problem.

Why LFU Matters

Caching is one of the most impactful performance optimizations in software engineering. Choosing the right eviction policy directly affects cache hit rates and, consequently, application latency. LFU shines in scenarios where access patterns are skewed — a small subset of items is accessed repeatedly while others are touched only occasionally. Examples include:

Database query result caches where certain hot queries dominate traffic.
CDN edge caches where popular assets should remain available.
Feature flag or configuration stores where a few flags are read constantly.
Recommendation systems where trending items should be retained.

LFU is also a frequent interview topic (LeetCode 460) because it tests your ability to combine multiple data structures — hash maps and doubly linked lists — into a single cohesive design.

Understanding the Design

To achieve O(1) time complexity for both get and put, we need a combination of three structures:

Key map: A dictionary mapping each key to its node, giving O(1) lookup.
Frequency map: A dictionary mapping each frequency value to a doubly linked list of nodes that share that frequency. The list is ordered by recency, with the most recently accessed node at the head.
Min frequency tracker: An integer that tracks the current minimum frequency, so eviction can find the victim in O(1).

Each node stores the key, value, and its current frequency. When a node is accessed, it is removed from its current frequency list and inserted into the list for frequency + 1. If the old list becomes empty and it held the minimum frequency, the minimum is incremented.

Step 1: Define the Node and Doubly Linked List

We start by creating a Node class to hold each cache entry and a helper DoublyLinkedList to manage nodes at the same frequency. Using sentinel head and tail nodes simplifies insertion and removal logic by eliminating edge cases.

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.freq = 1
        self.prev = None
        self.next = None


class DoublyLinkedList:
    def __init__(self):
        # Sentinel nodes to avoid boundary checks
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def append_front(self, node):
        """Insert a node right after the head (most recently used)."""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
        self.size += 1

    def remove(self, node):
        """Detach a node from the list."""
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None
        self.size -= 1

    def pop_tail(self):
        """Remove and return the least recently used node (before tail)."""
        if self.size == 0:
            return None
        node = self.tail.prev
        self.remove(node)
        return node

Step 2: Build the LFU Cache Class

Now we wire the structures together. The LFUCache class maintains the key map, the frequency map, the minimum frequency, and the capacity. The _update helper centralizes the logic of moving a node to the next frequency bucket whenever it is accessed.

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0
        self.min_freq = 0
        self.key_map = {}                       # key -> Node
        self.freq_map = {}                      # freq -> DoublyLinkedList

    def _update(self, node):
        """Move a node from its current frequency list to freq + 1."""
        freq = node.freq
        self.freq_map[freq].remove(node)

        # If we emptied the min frequency list, bump min_freq up
        if self.min_freq == freq and self.freq_map[freq].size == 0:
            self.min_freq += 1

        node.freq += 1
        new_freq = node.freq
        if new_freq not in self.freq_map:
            self.freq_map[new_freq] = DoublyLinkedList()
        self.freq_map[new_freq].append_front(node)

    def get(self, key):
        if key not in self.key_map:
            return -1
        node = self.key_map[key]
        self._update(node)
        return node.value

    def put(self, key, value):
        if self.capacity <= 0:
            return

        if key in self.key_map:
            node = self.key_map[key]
            node.value = value
            self._update(node)
            return

        # New key: evict if necessary
        if self.size == self.capacity:
            lru_node = self.freq_map[self.min_freq].pop_tail()
            del self.key_map[lru_node.key]
            self.size -= 1

        new_node = Node(key, value)
        self.key_map[key] = new_node
        if 1 not in self.freq_map:
            self.freq_map[1] = DoublyLinkedList()
        self.freq_map[1].append_front(new_node)
        self.min_freq = 1
        self.size += 1

Step 3: Walk Through an Example

To verify correctness, trace through a small sequence of operations. Consider a cache with capacity 2:

cache = LFUCache(2)
cache.put(1, 1)   # cache = {1=1}, freq: {1: [1]}
cache.put(2, 2)   # cache = {1=1, 2=2}, freq: {1: [2, 1]}
print(cache.get(1))  # returns 1, freq: {1: [2], 2: [1]}
cache.put(3, 3)   # evicts key 2 (min freq, LRU), cache = {1=1, 3=3}
print(cache.get(2))  # returns -1
print(cache.get(3))  # returns 3, freq: {2: [1, 3]}
cache.put(4, 4)   # evicts key 1 (both freq 2, but 1 is LRU), cache = {3=3, 4=4}
print(cache.get(1))  # returns -1
print(cache.get(3))  # returns 3
print(cache.get(4))  # returns 4

The output should be 1, -1, 3, -1, 3, 4. This matches the canonical LeetCode 460 expected result, confirming the implementation is correct.

Step 4: Add Diagnostics and Testing

For debugging, it helps to expose the internal state. A simple __repr__ method or a snapshot function lets you inspect the cache during development.

def snapshot(cache):
    state = {}
    for key, node in cache.key_map.items():
        state[key] = {"value": node.value, "freq": node.freq}
    return state

# Usage
cache = LFUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
print(snapshot(cache))
# Output: {1: {'value': 1, 'freq': 2}, 2: {'value': 2, 'freq': 1}}

You can also write unit tests using the unittest module to lock in behavior:

import unittest

class TestLFUCache(unittest.TestCase):
    def test_basic_operations(self):
        cache = LFUCache(2)
        cache.put(1, 1)
        cache.put(2, 2)
        self.assertEqual(cache.get(1), 1)
        cache.put(3, 3)  # evicts 2
        self.assertEqual(cache.get(2), -1)
        self.assertEqual(cache.get(3), 3)
        cache.put(4, 4)  # evicts 1
        self.assertEqual(cache.get(1), -1)
        self.assertEqual(cache.get(3), 3)
        self.assertEqual(cache.get(4), 4)

    def test_zero_capacity(self):
        cache = LFUCache(0)
        cache.put(1, 1)
        self.assertEqual(cache.get(1), -1)

    def test_update_existing_key(self):
        cache = LFUCache(2)
        cache.put(1, 1)
        cache.put(1, 10)
        self.assertEqual(cache.get(1), 10)

if __name__ == "__main__":
    unittest.main()

Best Practices

When implementing or adapting an LFU cache for real-world use, keep these guidelines in mind:

Guard against zero or negative capacity: Always check capacity <= 0 in put to avoid inserting into an unusable cache.
Use sentinel nodes: They eliminate null checks and make linked list operations cleaner and less error-prone.
Centralize frequency updates: A single _update method prevents duplicated logic between get and put.
Consider thread safety: In concurrent environments, wrap get and put with a threading.Lock or use a RLock if reentrancy is needed.
Monitor memory: Frequency maps can grow unbounded if many distinct frequencies appear. In long-running services, consider capping or aging frequencies periodically.
Combine with TTL: Pure LFU can retain stale-but-popular items forever. Pair it with a time-to-live policy to evict outdated entries.
Benchmark before adopting: LFU is not always better than LRU. Profile your access patterns with both strategies and pick the one with the higher hit rate.

Alternative: Using Python's Standard Library

If you do not need strict O(1) guarantees and want a quick solution, Python's collections.OrderedDict can simulate LFU with O(log n) eviction by sorting keys by frequency. This is simpler but slower for large caches.

from collections import OrderedDict

class SimpleLFU:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()  # key -> (value, freq)

    def get(self, key):
        if key not in self.cache:
            return -1
        value, freq = self.cache[key]
        self.cache[key] = (value, freq + 1)
        return value

    def put(self, key, value):
        if self.capacity <= 0:
            return
        if key in self.cache:
            _, freq = self.cache[key]
            self.cache[key] = (value, freq + 1)
            return
        if len(self.cache) >= self.capacity:
            # Evict the key with the smallest frequency
            lfu_key = min(self.cache, key=lambda k: self.cache[k][1])
            del self.cache[lfu_key]
        self.cache[key] = (value, 1)

This version is great for prototyping, scripts, or small datasets where the overhead of a full linked list implementation is not justified.

Conclusion

Implementing an LFU cache in Python is a rewarding exercise that deepens your understanding of hash maps, doubly linked lists, and amortized constant-time design. By combining a key map for instant lookup, a frequency map of linked lists for ordered eviction, and a minimum frequency tracker, you can build a cache that handles both get and put in O(1) average time. Whether you are preparing for a coding interview or designing a real caching layer, the patterns covered here — sentinel nodes, centralized update logic, and frequency bucketing — will serve you well across many systems programming challenges. Start with the simple OrderedDict version for quick experiments, then graduate to the full implementation when performance matters, and always validate your eviction policy against your actual access patterns before shipping to production.