Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C++

LFU Cache

Understand and implement the LFU Cache data structure that evicts the least frequently used keys with ties broken by least recently used. This lesson guides you through designing Get and Put operations to run in average constant time and maintain usage counts, enhancing your skills in advanced custom data structures.

We'll cover the following...

Statement

Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class. Here is how it should be implemented:

  • LFUCache(capacity): This function initializes the object with the capacity of the data structure.

  • Get(key): This function gets the value of the key if it exists in the cache. Otherwise, it returns -1.

  • Put(key, value): This function updates the value of the key if present, or inserts the key if it’s not present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there’s a tie, that is, two or more keys have the same frequency, the least recently used key is invalidated.

To determine the least frequently used key, a UseCounter is maintained for each key in the cache. The key with the smallest UseCounter is the least frequently used key. When a key is first inserted into the cache, its UseCounter is set to 1 (due to the Put() operation). The UseCounter for a key in the cache is incremented and either a Get() or Put() operation is called on it.

The Get and Put functions should both run with an average time complexity of O(1)O(1).

Constraints:

  • 0≤0 \leq capacity ≤104\leq 10^4

  • 0≤0 \leq key ≤105\leq 10^5

  • 0≤0 \leq value ≤105\leq 10^5

  • At most 2×1032×10^3 calls will be made to Get() and Put().

Examples

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

LFU Cache

1.

What is the output if the cache size is 2 and the following keys and values are given as input?

Put →[1, 1]
Put → [2, 2]
Get → [2]
Put → [3, 3]
Get → [1]
Get → [3]
Put → [4, 4]
Put → [5, 5]
Get → [1]
Get → [3]
Get → [5]

A.

[NULL, NULL, 2, NULL, 1, 3, NULL, NULL, -1, 3, 5]

B.

[NULL, NULL, 2, NULL, -1, 3, NULL, NULL, -1, 3, 5]

C.

[NULL, NULL, 2, NULL, -1, 3, NULL, NULL, 1, 3, 5]

1 / 2

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Note: As an additional challenge, we have intentionally hidden the solution to this puzzle.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3

Try it yourself

Implement your solution in lfu_cache.cpp in the following coding playground. We have provided a useful code template in the other file that you may build on to solve this problem.

C++
usercode > lfu_cache.cpp
// Definition for a Linked List node
// struct Node{
//     int key;
//     int val;
//     int useCounter;
//     Node* next;
//     Node* prev;
//     Node(int k, int v){
//         key = k;
//         val = v;
//         useCounter = 0;
//         next = prev = nullptr;
//     }
// };
class LFUCache {
    public:
        // Constructor that sets the size of the cache
        LFUCache(int capacity) {
            // Write your code here
        }
        int Get(int key) {
            // Replace this placeholder statement with your code
            return -1;
        }
        void Put(int key, int value) {
            // Write your code here
        }
};
LFU Cache