From 7c60dee83b436e8e8a667bf9f191beced8de4fc3 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Mon, 10 Mar 2025 00:36:13 -0600 Subject: chore: move cpp and rust code to directory --- other/lfu_cache.cpp | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 69 insertions(+) create mode 100644 other/lfu_cache.cpp (limited to 'other/lfu_cache.cpp') diff --git a/other/lfu_cache.cpp b/other/lfu_cache.cpp new file mode 100644 index 0000000..c0c857a --- /dev/null +++ b/other/lfu_cache.cpp @@ -0,0 +1,69 @@ +// 460. LFU Cache +#include +#include +using namespace std; + +// https://en.wikipedia.org/wiki/Least_frequently_used +// http://dhruvbird.com/lfu.pdf + +struct Node { + int value; + list::iterator itr; +}; + +class LFUCache { +private: + unordered_map umVal; + unordered_map umCount; + unordered_map> 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); +} -- cgit v1.2.3