Design and implement a data structure for a Least Frequently Used (LFU) cache.
Implement the LFUCache
class:
LFUCache(int capacity)
Initializes the object with thecapacity
of the data structure.int get(int key)
Gets the value of thekey
if thekey
exists in the cache. Otherwise, returns-1
.void put(int key, int value)
Update the value of thekey
if present, or inserts thekey
if not already present. When the cache reaches itscapacity
, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently usedkey
would be invalidated.
Example 1:
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] This we are going to implement using a combination of a hash table (unordered_map) to store the key-value pairs, the frequency of each key, and a list to maintain the order of the keys based on their frequency. The put function adds a new key-value pair to the cache and removes the least frequently used key if the capacity is exceeded. The get function retrieves the value of a key and updates its frequency. The update_freq function updates the frequency of a key and rearranges it in the list accordingly. Below is the implementation:
#include <unordered_map>
#include <list>
class LFUCache {
public:
int capacity;
std::unordered_map<int, std::pair<int, int>> key_val_freq;
std::unordered_map<int, std::list<int>::iterator> key_iter;
std::list<int> freq_list;
LFUCache(int _capacity) : capacity(_capacity) {}
int get(int key) {
if (key_val_freq.find(key) == key_val_freq.end()) return -1;
update_freq(key);
return key_val_freq[key].first;
}
void put(int key, int value) {
if (capacity <= 0) return;
if (key_val_freq.find(key) != key_val_freq.end()) {
update_freq(key);
key_val_freq[key].first = value;
return;
}
if (key_val_freq.size() == capacity) {
int k = freq_list.back();
freq_list.pop_back();
key_val_freq.erase(k);
key_iter.erase(k);
}
freq_list.push_front(key);
key_iter[key] = freq_list.begin();
key_val_freq[key] = { value, 1 };
}
private:
void update_freq(int key) {
auto it = key_iter[key];
int freq = key_val_freq[key].second;
key_val_freq[key].second++;
freq_list.erase(it);
for (auto i = freq_list.begin(); i != freq_list.end(); i++) {
if (key_val_freq[*i].second > freq) {
freq_list.insert(i, key);
key_iter[key] = --i;
return;
}
}
freq_list.push_back(key);
key_iter[key] = --freq_list.end();
}
};