LFU Cache

LFU Cache

What is this problem about?

The "LFU Cache interview question" asks you to design and implement a Least Frequently Used (LFU) cache data structure. When the cache is full, the element with the lowest frequency of access should be removed. If there's a tie in frequency, the Least Recently Used (LRU) element among them is evicted. This "LFU Cache coding problem" is a high-level design challenge that tests your ability to combine multiple data structures for constant time O(1) operations.

Why is this asked in interviews?

This is one of the most famous "Design interview pattern" questions, frequently asked at top-tier companies like Google, Microsoft, and Amazon. It evaluates a candidate's mastery of complex data structures like "Hash Table interview pattern", "Doubly-Linked List interview pattern", and their ability to synchronize multiple state variables (frequency, time, and values) in a performant way.

Algorithmic pattern used

To achieve O(1) for both get and put, you typically use three hash maps:

1. keyToVal: Stores the key and its corresponding value.
2. keyToFreq: Stores the access count for each key.
3. freqToList: Maps each frequency to a doubly-linked list of keys that have that frequency. The list itself is managed as an LRU queue. You also maintain a minFreq variable to quickly locate the frequency bucket from which to evict an item.

Example explanation

Capacity = 2.

1. put(1, 1): Cache: {1}, minFreq: 1.
2. put(2, 2): Cache: {1, 2}, minFreq: 1.
3. get(1): Freq of 1 becomes 2. minFreq stays 1 (because key 2 still has freq 1).
4. put(3, 3): Cache is full. Evict least frequent. Only key 2 has freq 1. Evict 2. Add 3. New state: {1, 3}, minFreq: 1.

Common mistakes candidates make

• O(n) eviction: Using a simple list and searching for the min frequency every time, which is too slow.
• MinFreq update errors: Forgetting to increment the minFreq when the only element in the lowest frequency bucket is accessed and moves to a higher bucket.
• Complex logic: Overcomplicating the move between frequency buckets, leading to pointer errors in the doubly-linked lists.

Interview preparation tip

Master the LRU Cache first. LFU is essentially an LRU Cache for every possible frequency. If you can visualize it as a map of frequency buckets, where each bucket is an LRU list, the implementation becomes much clearer.