In data management, efficient caching mechanisms are important in enhancing system performance. One of the cache replacement policies is the Least Frequently Used algorithm. In this article, we will discuss how to solve the LFU cache problem.
What is LFU Cache?
LFU, or Least Frequently Used, is a caching strategy where the system tracks the access frequency of cached elements and discards the element with the lowest number of accesses when the cache reaches its capacity.
This strategy prioritizes retaining the elements that have been accessed most often in the past, optimizing cache utilization for scenarios where recently accessed elements are likely to be needed again soon.
Let’s discuss how we can implement LFU Cache.
Using Hashing Approach
The hashing Approach is used to implement LFU Cache in this we will use Three hash-maps to implement LFU Cache.
Below are the steps to be followed to solve this Problem:-
- Firstly we will declare three hashmaps “frequencyList”, “keyNode” and “frequency”.
- In these hashmaps, we have key-value pairs in the following manner:
- frequencyList: the key is an integer and the value will be a list
- keyNode: the key is an integer and the value is an iterator containing the iterator for an element of a specific frequency of frequencyList.
- frequency: key is an integer value that is a pair of two other integers containing the frequency count and the value of a particular key.
- We will declare Two variables ‘minFrequency’ which will hold the minimum frequency from which we need to remove the number and ‘currentSize’ which determines the size of the LFU Cache.
Here are the 3 functions we need to solve the problem:
- LFUCache(int capacity) Initialize the LFU cache with positive size capacity.
- int get(int key)
- In LFU if the key is new. we need to return -1.
- If the key is not new, then we need to erase that key from the frequencyList. Also, increase the frequency count of the current element.
- Now Insert them into the frequencyList.
- If the minFrequency list is 0, then increase minFrequency by 1.
- Return the corresponding value for the given key.
- void put(int key, int value)
- If the capacity is less than 1, no put() operation will take place.
- Now, if the given key is a new one and we are at capacity then we need to remove the least used key.
- We will remove the very last element available from the frequencyList of minFrequency index. We also remove that element from frequency hashmap as well.
- As the item is a new one then, the minFrequency will be set to 1. And we will add them in frequencyList’s minFrequency index, frequency, and keyNode.
- If the key is not new, then we need to add the value to the frequency hashmap.
- Then we will call the get() function.
Let’s take an example:
Input:
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]Output:
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]Explanation:
cnt(x) = the use counter for key x
cache=[] will show the last used order for tiebreakers (the leftmost element is the most recent)
- In this firstly we are declaring LFU of size 2
- LFUCache.put(1,1) now cache = [1,_] and cnt(1) = 1;
- LFUCache.put(2,2) now cache = [2,1] and cnt(1) = 1, cnt(2) = 1
- LFUCache.get(1) and 1 is present so we will return 1, cache=[1,2], cnt(2)=1, cnt(1)=2
- LFUCache.put(3,3) now 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2. cache = [3,1] and cnt(3) = 1, cnt(1) = 2
- LFUCache.get(2); we will return -1.
- LFUCache.get(3); we will return 3. And now cache = [3,1] and cnt(3) = 2, cnt(1) = 2.
- LFUCache.put(4,4) now Both 1 and 3 have the same count, but 1 is LRU, invalidate 1. Now cache=[4,3], cnt(4)=1, cnt(3)=2
- LFUCache.get(1); we will return -1.
- LFUCache.get(3); we will return 3. Now cache=[3,4], cnt(4)=1, cnt(3)=3
- LFUCache.get(4); we will return 4. Now cache=[4,3], cnt(4)=2, cnt(3)=3
C++ Code
Here is the C++ program to implement LFU Cache problem:
#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;
class LFUCache {
public:
int Capacity, minFrequency = 0, currentSize = 0;
unordered_map<int, list<int>> frequencyList; // Map to store keys based on frequency
unordered_map<int, list<int>::iterator> keyNode; // Map to store iterator pointing to the position of keys in frequencyList
unordered_map<int, pair<int, int>> frequency; // Map to store frequency and value of each key
LFUCache(int capacity) {
Capacity = capacity;
minFrequency = 0, currentSize = 0;
}
// Function to get the value of a key
int get(int key) {
if (keyNode.find(key) == keyNode.end())
return -1; // Key not found
int keyFreq = frequency[key].first;
frequencyList[keyFreq].erase(keyNode[key]);
frequency[key].first++;
frequencyList[frequency[key].first].push_front(key);
keyNode[key] = frequencyList[frequency[key].first].begin();
if (frequencyList[minFrequency].size() == 0)
minFrequency++; // Update minFrequency if the list is empty
return frequency[key].second; // Return the value of the key
}
// Function to put a key-value pair into the cache
void put(int key, int value) {
if (Capacity <= 0)
return; // Capacity is zero or negative, do nothing
if (keyNode.find(key) != keyNode.end()) {
// Key already exists, update its value and frequency
frequency[key].second = value;
get(key);
return;
}
// New Element
if (currentSize == Capacity) {
// Cache is full, evict the least frequently used key
int minFreqBack = frequencyList[minFrequency].back();
keyNode.erase(minFreqBack);
frequency.erase(minFreqBack);
frequencyList[minFrequency].pop_back();
currentSize--;
}
// Add the new key to the cache
currentSize++;
minFrequency = 1;
frequencyList[minFrequency].push_front(key);
keyNode[key] = frequencyList[minFrequency].begin();
frequency[key].first = 1, frequency[key].second = value;
}
};
int main() {
// Example Usage
LFUCache lfuCache(2);
lfuCache.put(1, 1);
lfuCache.put(2, 2);
cout << lfuCache.get(1) << endl; // Output: 1
lfuCache.put(3, 3);
cout << lfuCache.get(2) << endl; // Output: -1
cout << lfuCache.get(3) << endl; // Output: 3
lfuCache.put(4, 4);
cout << lfuCache.get(1) << endl; // Output: -1
cout << lfuCache.get(3) << endl; // Output: 3
cout << lfuCache.get(4) << endl; // Output: 4
return 0;
}Python Code
Here is the Python solution for this problem:
from collections import defaultdict, OrderedDict
class LFUCache:
def __init__(self, capacity):
self.capacity = capacity
self.min_frequency = 0
self.current_size = 0
self.frequency_list = defaultdict(OrderedDict) # Dictionary to store keys based on frequency
self.key_node = {} # Dictionary to store the position of keys in frequency_list
self.frequency = {} # Dictionary to store frequency and value of each key
def get(self, key):
if key not in self.key_node:
return -1 # Key not found
key_freq = self.frequency[key][0]
del self.frequency_list[key_freq][key]
self.frequency[key][0] += 1
self.frequency_list[self.frequency[key][0]][key] = None
self.key_node[key] = next(iter(self.frequency_list[self.frequency[key][0]]))
if not self.frequency_list[self.min_frequency]:
self.min_frequency += 1 # Update min_frequency if the list is empty
return self.frequency[key][1] # Return the value of the key
def put(self, key, value):
if self.capacity <= 0:
return # Capacity is zero or negative, do nothing
if key in self.key_node:
# Key already exists, update its value and frequency
self.frequency[key][1] = value
self.get(key)
return
# New Element
if self.current_size == self.capacity:
# Cache is full, evict the least frequently used key
min_freq_key = next(iter(self.frequency_list[self.min_frequency]))
del self.key_node[min_freq_key]
del self.frequency[min_freq_key]
del self.frequency_list[self.min_frequency][min_freq_key]
self.current_size -= 1
# Add the new key to the cache
self.current_size += 1
self.min_frequency = 1
self.frequency_list[self.min_frequency][key] = None
self.key_node[key] = next(iter(self.frequency_list[self.min_frequency]))
self.frequency[key] = [1, value]
# Example Usage
lfu_cache = LFUCache(2)
lfu_cache.put(1, 1)
lfu_cache.put(2, 2)
print(lfu_cache.get(1)) # Output: 1
lfu_cache.put(3, 3)
print(lfu_cache.get(2)) # Output: -1
print(lfu_cache.get(3)) # Output: 3
lfu_cache.put(4, 4)
print(lfu_cache.get(1)) # Output: -1
print(lfu_cache.get(3)) # Output: 3
print(lfu_cache.get(4)) # Output: 4Java Code
You can do it in Java also:
import java.util.*;
class LFUCache {
private int capacity;
private int minFrequency;
private int currentSize;
private Map<Integer, LinkedHashMap<Integer, Void>> frequencyList; // Map to store keys based on frequency
private Map<Integer, Integer> keyNode; // Map to store the position of keys in frequencyList
private Map<Integer, int[]> frequency; // Map to store frequency and value of each key
public LFUCache(int capacity) {
this.capacity = capacity;
this.minFrequency = 0;
this.currentSize = 0;
this.frequencyList = new HashMap<>();
this.keyNode = new HashMap<>();
this.frequency = new HashMap<>();
}
public int get(int key) {
if (!keyNode.containsKey(key)) {
return -1; // Key not found
}
int keyFreq = frequency.get(key)[0];
frequencyList.get(keyFreq).remove(key);
frequency.get(key)[0]++;
frequencyList.computeIfAbsent(frequency.get(key)[0], k -> new LinkedHashMap<>()).put(key, null);
keyNode.put(key, frequencyList.get(frequency.get(key)[0]).keySet().iterator().next());
if (frequencyList.get(minFrequency).isEmpty()) {
minFrequency++; // Update minFrequency if the list is empty
}
return frequency.get(key)[1]; // Return the value of the key
}
public void put(int key, int value) {
if (capacity <= 0) {
return; // Capacity is zero or negative, do nothing
}
if (keyNode.containsKey(key)) {
// Key already exists, update its value and frequency
frequency.get(key)[1] = value;
get(key);
return;
}
// New Element
if (currentSize == capacity) {
// Cache is full, evict the least frequently used key
int minFreqKey = frequencyList.get(minFrequency).keySet().iterator().next();
keyNode.remove(minFreqKey);
frequency.remove(minFreqKey);
frequencyList.get(minFrequency).remove(minFreqKey);
currentSize--;
}
// Add the new key to the cache
currentSize++;
minFrequency = 1;
frequencyList.computeIfAbsent(minFrequency, k -> new LinkedHashMap<>()).put(key, null);
keyNode.put(key, frequencyList.get(minFrequency).keySet().iterator().next());
frequency.put(key, new int[]{1, value});
}
public static void main(String[] args) {
// Example Usage
LFUCache lfuCache = new LFUCache(2);
lfuCache.put(1, 1);
lfuCache.put(2, 2);
System.out.println(lfuCache.get(1)); // Output: 1
lfuCache.put(3, 3);
System.out.println(lfuCache.get(2)); // Output: -1
System.out.println(lfuCache.get(3)); // Output: 3
lfuCache.put(4, 4);
System.out.println(lfuCache.get(1)); // Output: -1
System.out.println(lfuCache.get(3)); // Output: 3
System.out.println(lfuCache.get(4)); // Output: 4
}
}Output:
1
-1
3
-1
3
4
The Time Complexity for this approach is O(1) because accessing and removing elements from the hashmap takes O(1) time complexity. The Space Complexity is O(capacity^2), which is mainly due to the storage of frequency lists using HashMaps. Here capacity is the size of the frequencylist.
Conclusion
In conclusion, we solved the LFU cache leetcode problem by implementing the Least Frequency Used algorithm using hashing. It is crucial for optimizing data retrieval in systems with limited resources.
