Hard
Hash TableLinked ListDesign
Updated Sep 2026

LFU Cache

Asked at Apple, Ripple, Salesforce, Walmart

Problem

Design and implement a data structure for a Least Frequently Used (LFU) cache. Implement get and put operations in O(1) time. When the cache reaches capacity, the least frequently used item is evicted. If there is a tie, the least recently used item is evicted.

Asked At

CompanyDifficulty
AppleHardView all Apple questions →
RippleHardView all Ripple questions →
SalesforceHardView all Salesforce questions →
WalmartHardView all Walmart questions →

How to Think About It

1.

Three data structures: (1) hash map key -> node, (2) hash map frequency -> doubly linked list of nodes, (3) variable minFreq tracking the current minimum frequency.

2.

Each node stores key, value, frequency, prev, and next pointers. The doubly linked list per frequency maintains insertion order (most recent at tail, least recent at head).

3.

On get(key): if key exists, remove from current frequency list, increment frequency, add to new frequency list. Update minFreq if the old list became empty.

4.

On put(key, value): if key exists, update value and frequency (same as get). If at capacity, remove head of minFreq list (least recently used among least frequently used). Add new node to freq=1 list.

5.

Visual walkthrough for capacity=2:
put(1,1): freq=1 list: [node(1,1)]. minFreq=1.
put(2,2): freq=1 list: [node(1,1), node(2,2)]. minFreq=1.
get(1): node(1) freq 1->2. Remove from freq=1, add to freq=2. freq=2 list: [node(1,1)]. minFreq=2 (freq=1 list not empty? yes it has node(2)). Actually minFreq stays 1.
put(3,3): full. Evict head of minFreq=1 list: node(2,2). freq=1 list: [node(3,3)]. minFreq=1.
get(3): node(3) freq 1->2. freq=2 list: [node(1,1), node(3,3)].

6.

Why O(1): hash map lookups are O(1), doubly linked list insert/delete at known nodes is O(1).

Optimal Approach

Data structures:

  • keyToNode: key -> Node (for O(1) lookup)
  • freqToList: frequency -> doubly linked list (for O(1) eviction)
  • minFreq: current minimum frequency

get(key):

  1. If key not in keyToNode, return -1.
  2. Remove node from current frequency list.
  3. Increment node frequency.
  4. Add node to new frequency list.
  5. If old frequency list is empty and it was minFreq, increment minFreq.
  6. Return node value.

put(key, value):

  1. If key exists: update value, call get (triggers frequency update).
  2. If key does not exist:
    a. If at capacity: remove head of minFreq list, delete from keyToNode.
    b. Create new node with freq=1, add to freq=1 list, add to keyToNode.
    c. Set minFreq = 1.

Time: O(1) for both operations. Space: O(capacity).

What Trips People Up in Real Interviews

1.

Confusing LFU with LRU. LFU evicts the least frequently used item. On ties, it evicts the least recently used among the tied items. Both frequency and recency matter.

2.

Not maintaining a separate doubly linked list per frequency. Without per-frequency lists, you cannot achieve O(1) eviction of the least recently used item within a frequency tier.

3.

Forgetting to update minFreq when a frequency list becomes empty. If the list at minFreq is emptied after a get/put, minFreq must increment to the next occupied frequency.

4.

Not storing the key in the node. When evicting from a frequency list, you need the key to remove the entry from keyToNode. Without it, the hash map entry leaks.

5.

Evicting the most recently used item instead of the least recently used within a frequency tier. The doubly linked list must maintain insertion order so the head is always the LRU item for that frequency.

Solution Code

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

class DoublyLinkedList:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def add(self, node):
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node
        self.size += 1

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

    def popFront(self):
        if self.size == 0:
            return None
        node = self.head.next
        self.remove(node)
        return node

class LFUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.keyToNode = {}
        self.freqToList = {}
        self.minFreq = 0

    def _removeFreq(self, freq):
        if freq in self.freqToList and self.freqToList[freq].size == 0:
            del self.freqToList[freq]

    def get(self, key):
        if key not in self.keyToNode:
            return -1
        node = self.keyToNode[key]
        self.freqToList[node.freq].remove(node)
        if self.freqToList[node.freq].size == 0:
            del self.freqToList[node.freq]
            if self.minFreq == node.freq:
                self.minFreq += 1
        node.freq += 1
        if node.freq not in self.freqToList:
            self.freqToList[node.freq] = DoublyLinkedList()
        self.freqToList[node.freq].add(node)
        return node.val

    def put(self, key, value):
        if self.cap == 0:
            return
        if key in self.keyToNode:
            node = self.keyToNode[key]
            node.val = value
            self.freqToList[node.freq].remove(node)
            if self.freqToList[node.freq].size == 0:
                del self.freqToList[node.freq]
                if self.minFreq == node.freq:
                    self.minFreq += 1
            node.freq += 1
            if node.freq not in self.freqToList:
                self.freqToList[node.freq] = DoublyLinkedList()
            self.freqToList[node.freq].add(node)
            return
        if len(self.keyToNode) >= self.cap:
            evict = self.freqToList[self.minFreq].popFront()
            del self.keyToNode[evict.key]
            self._removeFreq(self.minFreq)
        newNode = Node(key, value, 1)
        self.keyToNode[key] = newNode
        if 1 not in self.freqToList:
            self.freqToList[1] = DoublyLinkedList()
        self.freqToList[1].add(newNode)
        self.minFreq = 1

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the LFU Cache problem?

Design and implement a data structure for a Least Frequently Used (LFU) cache. Implement get and put operations in `O(1)` time. When the cache reaches capacity, the least frequently used item is evicted. If there is a tie, the least recently used item is evicted.

How do you solve LFU Cache?

The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.

What companies ask LFU Cache?

LFU Cache is asked at Apple, Ripple, Salesforce, Walmart. It is a hard difficulty problem.

What are common mistakes on LFU Cache?
  • Confusing LFU with LRU. LFU evicts the least frequently used item. On ties, it evicts the least recently used among the tied items. Both frequency and recency matter.
  • Not maintaining a separate doubly linked list per frequency. Without per-frequency lists, you cannot achieve `O(1)` eviction of the least recently used item within a frequency tier.
  • Forgetting to update `minFreq` when a frequency list becomes empty. If the list at `minFreq` is emptied after a get/put, `minFreq` must increment to the next occupied frequency.
  • Not storing the key in the node. When evicting from a frequency list, you need the key to remove the entry from `keyToNode`. Without it, the hash map entry leaks.
  • Evicting the most recently used item instead of the least recently used within a frequency tier. The doubly linked list must maintain insertion order so the head is always the LRU item for that frequency.