Interview Guide: LFU Cache Problems and Solutions

Understanding LFU Cache

What is an LFU Cache?

An LFU (Least Frequently Used) cache is a caching strategy that evicts items based on how often they are accessed. When the cache reaches its capacity limit and a new item needs to be inserted, the algorithm identifies and removes the item with the lowest access frequency. If multiple items share the same lowest frequency, the one that was least recently used among them is evicted — this is the LFU-LRU tiebreaker.

The core idea is simple: items that are requested more often are more valuable and should be kept in the cache longer. This contrasts sharply with LRU (Least Recently Used), which only cares about recency, not frequency.

LFU vs LRU: Key Differences

Here is a quick comparison to ground your understanding:

• LRU evicts the item that hasn't been accessed for the longest time. It uses recency as the sole metric. Great for workloads with temporal locality (recently accessed items tend to be accessed again soon).
• LFU evicts the item with the smallest access count. It uses frequency as the primary metric. Great for workloads where popular items are accessed repeatedly over a long period, even if they go dormant for a while.
• LRU can be implemented with a simple doubly linked list and a hash map — one data structure handles everything.
• LFU requires more complex bookkeeping: you must track frequencies, maintain multiple buckets (one per frequency), and efficiently find the minimum frequency at any time.

Why LFU Matters in Interviews

LFU cache problems appear frequently in technical interviews at top-tier companies because they test a candidate's ability to:

• Design complex data structures that combine multiple simpler ones (hash maps, linked lists, frequency buckets).
• Reason about time complexity trade-offs and achieve true O(1) operations.
• Handle edge cases like capacity zero, frequency updates, and tiebreaking.
• Write clean, modular code under pressure — the implementation is nontrivial but bounded.

Mastering the LFU cache demonstrates advanced data structure fluency and signals that you can tackle real-world caching problems (like in-memory caches, CDN eviction policies, or database buffer pools) where frequency-based eviction is critical.

Core Data Structures for O(1) LFU Cache

The Frequency-List Approach

The optimal LFU cache achieves O(1) time for both get(key) and put(key, value). To do this, we combine three main components:

• Key-Node Map: A hash map from key to a Node object. This gives O(1) access to any cached item's data, including its current frequency.
• Frequency Map: A hash map from an integer frequency to a DoublyLinkedList of nodes that all share that frequency. Each list maintains insertion order, which serves as the LRU tiebreaker within the same frequency bucket.
• Min Frequency Tracker: A variable that always knows the smallest frequency currently present in the cache. When we need to evict, we go straight to the list at min_frequency and remove its oldest (tail) node.

When a node's frequency increases (due to a get or an overwriting put), we remove it from its current frequency list and insert it into the list for frequency + 1. If the old list becomes empty and it was the minimum frequency list, we increment min_frequency.

Detailed Implementation in Python

Below is a complete, production-ready implementation of an LFU cache. Study it line by line — every detail matters for interviews.

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


class DoublyLinkedList:
    """A doubly linked list that supports O(1) removal of any node."""
    def __init__(self):
        self.head = Node(0, 0)  # dummy head
        self.tail = Node(0, 0)  # dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def add_to_front(self, node: Node) -> None:
        """Insert node right after dummy head (most recently used position)."""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
        self.size += 1

    def remove_node(self, node: Node) -> None:
        """Remove an arbitrary node from the list in O(1)."""
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None
        self.size -= 1

    def remove_last(self) -> Node:
        """Remove and return the node just before dummy tail (least recently used)."""
        if self.size == 0:
            return None
        last_node = self.tail.prev
        self.remove_node(last_node)
        return last_node

    def is_empty(self) -> bool:
        return self.size == 0


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

    def _get_list_for_frequency(self, freq: int) -> DoublyLinkedList:
        """Return the DoublyLinkedList for a given frequency, creating it if needed."""
        if freq not in self.freq_map:
            self.freq_map[freq] = DoublyLinkedList()
        return self.freq_map[freq]

    def _update_frequency(self, node: Node) -> None:
        """Move a node from its current frequency list to freq+1 list."""
        old_freq = node.frequency
        old_list = self._get_list_for_frequency(old_freq)
        old_list.remove_node(node)

        # If the old list is now empty and it was the min frequency, increment min_frequency
        if old_freq == self.min_frequency and old_list.is_empty():
            self.min_frequency += 1

        node.frequency += 1
        new_list = self._get_list_for_frequency(node.frequency)
        new_list.add_to_front(node)

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

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return

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

        # Eviction needed before insertion
        if self.size == self.capacity:
            # Find the list for the minimum frequency
            min_list = self._get_list_for_frequency(self.min_frequency)
            evicted_node = min_list.remove_last()
            if evicted_node:
                del self.key_map[evicted_node.key]
                self.size -= 1
            # If the list is now empty, the next insertion will set a new min_frequency
            # (min_frequency will be updated when we insert the new node with frequency 1)

        # Insert new node
        new_node = Node(key, value)
        self.key_map[key] = new_node
        freq_list = self._get_list_for_frequency(1)
        freq_list.add_to_front(new_node)
        self.min_frequency = 1  # Reset min_frequency because we just added a frequency-1 node
        self.size += 1

Step-by-Step Walkthrough

Let's trace a concrete example to see how all the pieces interact. Assume a cache with capacity = 2.

Sequence: put(1, "A"), put(2, "B"), get(1), put(3, "C")

• put(1, "A"): Node(1,"A",freq=1) is created. Added to freq_map[1] list. min_frequency = 1. Size = 1.
• put(2, "B"): Node(2,"B",freq=1) created. Added to freq_map[1] list (now has two nodes: 1 then 2). Size = 2, at capacity.
• get(1): Node 1 is found. Its frequency updates: removed from freq_map[1], freq becomes 2, added to freq_map[2]. min_frequency remains 1 (node 2 is still at freq 1).
• put(3, "C"): Cache is full. We look at min_frequency=1 list. It contains node 2. We evict node 2 (the LRU among freq=1 nodes). Delete key 2 from key_map. Insert Node(3,"C",freq=1) into freq_map[1]. min_frequency = 1. Size remains 2.

This trace reveals the elegance of the design: frequency updates are O(1) linked-list manipulations, eviction is an O(1) removal from the tail of the min-frequency list, and the min_frequency tracker never requires scanning all frequencies.

Alternative Approaches

Min-Heap + HashMap

Another valid approach uses a min-heap keyed by (frequency, timestamp) alongside a hash map for direct key access. Each operation is O(log N) due to heap insertion and removal. This is easier to implement but not optimal. In interviews, presenting the O(1) solution shows deeper understanding, but the heap approach is a solid fallback if you're stuck.

import heapq
import time

class LFUCacheHeap:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.key_map = {}
        self.heap = []  # (frequency, timestamp, key, value)
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.key_map:
            return -1
        freq, _, value = self.key_map[key]
        self.key_map[key] = (freq + 1, time.monotonic_ns(), value)
        # Rebuild heap lazily — or use a more sophisticated approach
        # For simplicity in interview: push new entry and invalidate stale ones on pop
        heapq.heappush(self.heap, (freq + 1, time.monotonic_ns(), key, value))
        return value

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.key_map:
            freq, _, _ = self.key_map[key]
            self.key_map[key] = (freq + 1, time.monotonic_ns(), value)
            heapq.heappush(self.heap, (freq + 1, time.monotonic_ns(), key, value))
            return
        if self.size == self.capacity:
            while self.heap:
                freq, ts, evict_key, evict_val = heapq.heappop(self.heap)
                if evict_key in self.key_map:
                    stored_freq, _, _ = self.key_map[evict_key]
                    if stored_freq == freq:
                        del self.key_map[evict_key]
                        self.size -= 1
                        break
        new_freq = 1
        ts = time.monotonic_ns()
        self.key_map[key] = (new_freq, ts, value)
        heapq.heappush(self.heap, (new_freq, ts, key, value))
        self.size += 1

Note that this implementation uses lazy eviction: stale entries accumulate in the heap and are discarded when they no longer match the current frequency in key_map. This is a common pattern in heap-based cache designs.

Balanced BST Approach

In languages like Java, you can use a TreeSet or TreeMap (red-black tree) to maintain frequencies in sorted order, achieving O(log N) operations similarly to the heap approach. The principle is identical — use a comparator that sorts by (frequency, last_access_time).

Common Interview Pitfalls

When solving LFU cache problems in an interview setting, watch out for these traps:

• Forgetting the tiebreaker: Simply tracking frequency isn't enough. You must define behavior when two items have the same frequency. The standard is "least recently used among same-frequency items."
• Not updating min_frequency correctly: When you increment a node's frequency and its old frequency bucket becomes empty, you must check if that bucket was the current minimum. If so, increment min_frequency. When inserting a brand-new node (frequency=1), always reset min_frequency to 1.
• Handling capacity zero: Always add an early return for capacity == 0 in put. Forgetting this causes division-by-zero-like logic errors.
• Overwriting existing keys: When put is called with an existing key, you must update its value and increment its frequency — it counts as an access. Many candidates forget the frequency bump on overwrite.
• Memory leaks in linked list: When removing nodes, always clear their prev and next pointers to avoid dangling references that could confuse debugging or cause subtle bugs.

Best Practices for LFU Cache Problems

Here are battle-tested recommendations for interview success:

• Start with the API: Before writing any data structure code, define the interface: get(key) returns value or -1, put(key, value) inserts/updates. Clarify capacity behavior and eviction policy with the interviewer.
• Draw the data structure: Use the whiteboard to sketch the key_map pointing to nodes, and the freq_map pointing to doubly linked lists. Visualizing helps you avoid off-by-one errors in the linked-list operations.
• Implement modularly: Separate the Node class, the DoublyLinkedList class, and the main LFUCache class. This keeps the code organized and lets you test each piece mentally.
• Write helper methods: Methods like _update_frequency and _get_list_for_frequency reduce repetition and make the main get/put methods elegantly short.
• Test with a concrete trace: After coding, run through a small example aloud. Interviewers value candidates who verify their own work.
• Discuss time complexity explicitly: State clearly that every operation is O(1) because hash map lookups, linked-list insertions/removals, and min_frequency updates are all constant time.
• Mention real-world context: Briefly connect LFU to systems you know — Redis supports LFU eviction via the allkeys-lfu policy, and CPU caches sometimes use frequency-based schemes. This shows breadth.

Conclusion

The LFU cache is a classic data structure problem that elegantly combines hash maps, doubly linked lists, and a frequency-tracking mechanism into a single cohesive design. Mastering it requires understanding not just the "how" but the "why" — why each component exists, why the tiebreaker matters, and why the min_frequency tracker is essential for O(1) eviction. By studying the complete implementation above, internalizing the common pitfalls, and practicing the step-by-step trace, you will be thoroughly prepared to tackle any LFU cache problem in your next technical interview. Remember: clarity of thought, modular code, and explicit complexity analysis are what interviewers look for. You now have all three.