LFU Cache
unknown
c_cpp
a month ago
1.7 kB
7
Indexable
Never
class LFUCache { public: unordered_map<int, int> freq; // key, kitne baar used unordered_map<int, list<int>> freqKeys; // 2 -> {_ _} // lru // 3 -> {_ _ [] _ [3]} // 4 -> {} unordered_map<int, pair<int, list<int>::iterator>> mp; // p.first = key // p.second = {value, iterator} int lfu; // least frequenty used ka frequency int capacity; LFUCache(int capacity) { this->capacity = capacity; lfu = 0; } void touch(int key) { int count = freq[key]; freq[key]++; auto p = mp[key].second; freqKeys[count].erase(p); freqKeys[freq[key]].push_back(key); if(freqKeys[lfu].size() == 0) { lfu++; } mp[key].second = --(freqKeys[freq[key]].end()); } int get(int key) { if (mp.find(key) == mp.end()) { return -1; } touch(key); return mp[key].first; } void put(int key, int value) { if(mp.find(key) != mp.end()) { mp[key].first = value; touch(key); return; } if(mp.size() == capacity) { int keyToRemove = *freqKeys[lfu].begin(); freq.erase(keyToRemove); auto p = mp[keyToRemove].second; freqKeys[lfu].erase(p); mp.erase(keyToRemove); } lfu = 1; freq[key] = lfu; freqKeys[lfu].push_back(key); mp[key] = {value, --freqKeys[lfu].end()}; } }; /** * Your LFUCache object will be instantiated and called as such: * LFUCache* obj = new LFUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */
Leave a Comment