LFU Cache

Hard

0/120

Average time to solve is 41m

Contributed by

19 upvotes

Problem statement

Design and implement an LFU (Least Frequently Used) cache data structure that supports the following operations:

1. LFUCache(int capacity): Initializes the cache object with a given capacity.

2. int get(int key): Retrieves the value of the key from the cache. If the key does not exist, returns -1.

3. void put(int key, int value): Inserts or updates the value of the key in the cache. If the cache is at its capacity, it removes the least frequently used key before inserting a new item. If multiple keys have the same frequency, it removes the least recently used key.

To determine the least frequently used key, each key in the cache has a use counter associated with it. The key with the smallest use counter is considered the least frequently used key. The use counter is incremented whenever a get or put operation is performed on the key.

Note: Both the get and put operations should run in O(1) average time complexity.

For Example:

Input:
6
2
2 1 1
2 2 2
1 1 
2 3 3
1 2
1 3

Output: 
1 -1 3

Explanation:
Line 1: Contains number of put and get operations.

Line 2: Initialize LFUCache with capacity 2: LFUCache lfu = new LFUCache(2);
        Creates an LFUCache object with a capacity of 2.

Line 3: Insert key=1, value=1 into the cache: lfu.put(1, 1);
        The cache initially looks like this: [1, _]
        The counter for key=1 is set to 1: count(1)=1

Line 4: Insert key=2, value=2 into the cache: lfu.put(2, 2);
        The cache is updated: [2, 1]
        The counters for key=2 and key=1 are both set to 1: count(2)=1, count(1)=1

Line 5: Retrieve value of key=1 from the cache: lfu.get(1);
        Returns 1 because key=1 exists in the cache.
        The cache becomes: [1, 2]
        The counter for key=1 is incremented to 2: count(1)=2

Line 6: Insert key=3, value=3 into the cache: lfu.put(3, 3);
        Since the cache is full (capacity reached), the least frequently used key needs to be invalidated.
        Among keys 1 and 2, key 2 has the lowest use counter (1). 
        Therefore, key 2 is removed.
        The cache is updated: [3, 1]
        The counters for key=3 and key=1 are set to 1: count(3)=1, count(1)=2

Line 7: Retrieve value of key=2 from the cache: lfu.get(2);
        Returns -1 because key=2 does not exist in the cache.
        The cache remains the same: [3, 1]

Line 8: Retrieve value of key=3 from the cache: lfu.get(3);
        Returns 3 because key=3 exists in the cache.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line contains the number of operations ‘Q’.
The second line contains the capacity.
For the next Q line, there will be either 2 or 3 integers on every new line
If there are 2 integers separated by space, the first integer will be 1 which means it's a get request followed by an integer which is a ‘key’.
If there are 3 integers separated by space, the first integer will be 2 which means it's a put request followed by 2 integers i.e. ‘key’ and ‘value’.

Output Format:

The output contains integers from the get function separated by space.

Note:-

You don’t need to print anything. Just implement the given function.

Sample Input 1:

Sample Output 1:

Explanation Of Sample Input 1:

Line 1: Contains number of put and get operations i.e. 3.

Line 2: Initialize LFUCache with capacity 2: LFUCache lfu = new LFUCache(2);
        Creates an LFUCache object with a capacity of 2.

Line 3: Insert key=5, value=2 into the cache: lfu.put(5, 2);
        The cache initially looks like this: [5, _]
        The counter for key=5 is set to 1: count(5)=1

Line 4: Insert key=4, value=3 into the cache: lfu.put(4, 3);
        The cache is updated: [4, 5]
        The counters for key=4 and key=5 are both set to 1: count(4)=1, count(5)=1

Line 5: Retrieve value of key=5 from the cache: lfu.get(5);
        Returns 2 because key=5 exists in the cache.
        The cache is updated: [5,4]
        The counter for key=5 is incremented to 2: count(5)=2

Sample Input 2:

Sample Output 2:

10 -1 30

Constraints:

1 <= Q <= 10^5
1 <= capacity <= 10^4
0 <= key <= 10^5
0 <= value <= 10^9


Time Limit: 1 sec

Console