aboutsummaryrefslogtreecommitdiff
path: root/other/lfu_cache.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/lfu_cache.cpp')
-rw-r--r--other/lfu_cache.cpp69
1 files changed, 0 insertions, 69 deletions
diff --git a/other/lfu_cache.cpp b/other/lfu_cache.cpp
deleted file mode 100644
index c0c857a..0000000
--- a/other/lfu_cache.cpp
+++ /dev/null
@@ -1,69 +0,0 @@
-// 460. LFU Cache
-#include <bits/stdc++.h>
-#include <unordered_map>
-using namespace std;
-
-// https://en.wikipedia.org/wiki/Least_frequently_used
-// http://dhruvbird.com/lfu.pdf
-
-struct Node {
- int value;
- list<int>::iterator itr;
-};
-
-class LFUCache {
-private:
- unordered_map<int, Node> umVal;
- unordered_map<int, int> umCount;
- unordered_map<int, list<int>> umlCountKey;
- int lowFreq, maxCap;
-
-public:
- LFUCache(int capacity) {
- maxCap = capacity;
- lowFreq = 0;
- }
- int get(int key) {
- if (umVal.find(key) == umVal.end() || maxCap <= 0)
- return -1;
- put(key, umVal[key].value);
- return umVal[key].value;
- }
- void put(int key, int value) {
- if (maxCap <= 0)
- return;
- if (umVal.find(key) == umVal.end()) {
- if (umVal.size() == maxCap) {
- int del = umlCountKey[lowFreq].back();
- umlCountKey[lowFreq].pop_back();
- if (umlCountKey[lowFreq].empty())
- umlCountKey.erase(lowFreq);
- umVal.erase(del);
- umCount.erase(del);
- }
- umVal[key].value = value;
- umCount[key] = 0;
- lowFreq = 0;
- umlCountKey[umCount[key]].push_front(key);
- umVal[key].itr = umlCountKey[0].begin();
- } else {
- umlCountKey[umCount[key]].erase(umVal[key].itr);
- if (umlCountKey[umCount[key]].empty()) {
- if (lowFreq == umCount[key])
- lowFreq++;
- umlCountKey.erase(umCount[key]);
- }
- umVal[key].value = value;
- umCount[key]++;
- umlCountKey[umCount[key]].push_front(key);
- umVal[key].itr = umlCountKey[umCount[key]].begin();
- }
- }
-};
-
-int main() {
- int capacity, key, value;
- LFUCache *obj = new LFUCache(capacity);
- int param_1 = obj->get(key);
- obj->put(key, value);
-}