{"id":264,"date":"2017-09-14T00:36:55","date_gmt":"2017-09-14T07:36:55","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=264"},"modified":"2018-07-10T18:30:08","modified_gmt":"2018-07-11T01:30:08","slug":"leetcode-460-lfu-cache","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-460-lfu-cache\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 460. LFU Cache"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"LeetCode 460. LFU Cache \/ O(1)  - \u82b1\u82b1\u9171 \u5237\u9898\u627e\u5de5\u4f5c EP54\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/MCTN3MM8vHA?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<div class=\"question-description\">\n<p>Design and implement a data structure for\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Least_frequently_used\" target=\"_blank\" rel=\"noopener\">Least Frequently Used (LFU)<\/a>\u00a0cache. It should support the following operations:\u00a0<code>get<\/code>\u00a0and\u00a0<code>put<\/code>.<\/p>\n<p><code>get(key)<\/code>\u00a0&#8211; Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.<br \/>\n<code>put(key, value)<\/code>\u00a0&#8211; Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least\u00a0<b>recently<\/b>\u00a0used key would be evicted.<\/p>\n<p><b>Follow up:<\/b><br \/>\nCould you do both operations in\u00a0<b>O(1)<\/b>\u00a0time complexity?<\/p>\n<p><b>Example:<\/b><\/p>\n<pre>LFUCache cache = new LFUCache( 2 \/* capacity *\/ );\r\n\r\ncache.put(1, 1);\r\ncache.put(2, 2);\r\ncache.get(1);       \/\/ returns 1\r\ncache.put(3, 3);    \/\/ evicts key 2\r\ncache.get(2);       \/\/ returns -1 (not found)\r\ncache.get(3);       \/\/ returns 3.\r\ncache.put(4, 4);    \/\/ evicts key 1.\r\ncache.get(1);       \/\/ returns -1 (not found)\r\ncache.get(3);       \/\/ returns 3\r\ncache.get(4);       \/\/ returns 4\r\n<\/pre>\n<\/div>\n<div id=\"interviewed-div\"><strong>Idea:<\/strong><\/div>\n<div><\/div>\n<div>Hashtable + balanced search tree<\/div>\n<div><\/div>\n<div>Hashtable + double linked list<\/div>\n<div><\/div>\n<div><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-271\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-1-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-270\" style=\"font-size: 1rem;\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-2-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-2-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-3.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-269\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-3.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-3-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/460-ep54-3-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/div>\n<div><\/div>\n<div><strong>Solution 1: <\/strong>O(logc) c is the capacity<\/div>\n<div>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 99 ms\r\nstruct CacheNode {\r\n    int key;\r\n    int value;\r\n    int freq;\r\n    long tick;\r\n    \r\n    \/\/ Defines the order, smaller one will be evicted first\r\n    bool operator &lt;(const CacheNode&amp; rhs) const {\r\n        if (freq &lt; rhs.freq) return true;\r\n        if (freq == rhs.freq) return tick &lt; rhs.tick;\r\n        return false;\r\n    }\r\n};\r\nclass LFUCache {\r\npublic:\r\n    LFUCache(int capacity):capacity_(capacity), tick_(0) {}\r\n    \r\n    int get(int key) {\r\n        auto it = m_.find(key);\r\n        if (it == m_.cend()) return -1;\r\n        int value = it-&gt;second.value;\r\n        touch(it-&gt;second);\r\n        return value;\r\n    }\r\n    \r\n    void put(int key, int value) {\r\n        if (capacity_ == 0) return;\r\n        \r\n        auto it = m_.find(key);\r\n        \r\n        if (it != m_.cend()) {\r\n            \/\/ Key exists, update value and touch\r\n            it-&gt;second.value = value;            \r\n            touch(it-&gt;second);            \r\n            return;\r\n        }\r\n        \r\n        if (m_.size() == capacity_) {\r\n            \/\/ Remove the first node in cache\r\n            const CacheNode&amp; node = *cache_.cbegin();\r\n            m_.erase(node.key);\r\n            cache_.erase(node);\r\n        }\r\n        \r\n        CacheNode node{key, value, 1, ++tick_};\r\n        m_[node.key] = node;\r\n        cache_.insert(node);\r\n    }\r\nprivate:\r\n    void touch(CacheNode&amp; node) {\r\n        cache_.erase(node);     \/\/ log(capacity)        \r\n        ++node.freq;\r\n        node.tick = ++tick_;\r\n        cache_.insert(node);    \/\/ log(capacity)\r\n    }\r\n    \r\n    long tick_;\r\n    int capacity_;\r\n    unordered_map&lt;int, CacheNode&gt; m_;\r\n    set&lt;CacheNode&gt; cache_;\r\n    \r\n};<\/pre>\n<\/div>\n<p><strong>Solution 2:\u00a0<\/strong>O(1)<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 89 ms (beats 96.3%)\r\n\r\nstruct CacheNode {\r\n    int key;\r\n    int value;\r\n    int freq;\r\n    \/\/ pointer to the node in the list\r\n    list&lt;int&gt;::const_iterator it;\r\n};\r\n\r\nclass LFUCache {\r\npublic:\r\n    LFUCache(int capacity): capacity_(capacity), min_freq_(0) {}\r\n    \r\n    int get(int key) {\r\n        auto it = n_.find(key);\r\n        if (it == n_.cend()) return -1;\r\n        touch(it-&gt;second);\r\n        return it-&gt;second.value;\r\n    }\r\n    \r\n    void put(int key, int value) {\r\n        if (capacity_ == 0) return;\r\n        \r\n        auto it = n_.find(key);\r\n        if (it != n_.cend()) {\r\n            \/\/ Key already exists, update the value and touch it\r\n            it-&gt;second.value = value;\r\n            touch(it-&gt;second);\r\n            return;\r\n        }\r\n        \r\n        if (n_.size() == capacity_) {\r\n            \/\/ No capacity, need to remove one entry that\r\n            \/\/ 1. has the lowest freq\r\n            \/\/ 2. least recently used if there are multiple ones\r\n            \r\n            \/\/ Step 1: remove the element from min_freq_ list\r\n            const int key_to_evict = l_[min_freq_].back();\r\n            l_[min_freq_].pop_back();\r\n            \r\n            \/\/ Step 2: remove the key from cache\r\n            n_.erase(key_to_evict);\r\n        }\r\n        \r\n        \/\/ We know new item has freq of 1, thus set min_freq to 1\r\n        const int freq = 1;\r\n        min_freq_ = freq;\r\n        \r\n        \/\/ Add the key to the freq list\r\n        l_[freq].push_front(key);\r\n        \r\n        \/\/ Create a new node\r\n        n_[key] = {key, value, freq, l_[freq].cbegin()};\r\n    }\r\nprivate:\r\n    void touch(CacheNode&amp; node) {\r\n        \/\/ Step 1: update the frequency\r\n        const int prev_freq = node.freq;\r\n        const int freq = ++(node.freq);\r\n        \r\n        \/\/ Step 2: remove the entry from old freq list\r\n        l_[prev_freq].erase(node.it);\r\n        \r\n        if (l_[prev_freq].empty() &amp;&amp; prev_freq == min_freq_) {\r\n            \/\/ Delete the list\r\n            l_.erase(prev_freq);\r\n            \r\n            \/\/ Increase the min freq\r\n            ++min_freq_;\r\n        }\r\n        \r\n        \/\/ Step 4: insert the key into the front of the new freq list\r\n        l_[freq].push_front(node.key);\r\n        \r\n        \/\/ Step 5: update the pointer\r\n        node.it = l_[freq].cbegin();\r\n    }\r\n    \r\n    int capacity_;\r\n    int min_freq_;\r\n    \r\n    \/\/ key -&gt; CacheNode\r\n    unordered_map&lt;int, CacheNode&gt; n_;\r\n    \r\n    \/\/ freq -&gt; keys with freq\r\n    unordered_map&lt;int, list&lt;int&gt;&gt; l_;\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem: Design and implement a data structure for\u00a0Least Frequently Used (LFU)\u00a0cache. It should support the following operations:\u00a0get\u00a0and\u00a0put. get(key)\u00a0&#8211; Get the value (will always be positive)&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[89,70],"tags":[86,82,85,83,84,28],"class_list":["post-264","post","type-post","status-publish","format-standard","hentry","category-data-structure","category-hashtable","tag-cache","tag-hashtable","tag-lfu","tag-list","tag-lru","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/264","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=264"}],"version-history":[{"count":11,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/264\/revisions"}],"predecessor-version":[{"id":3059,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/264\/revisions\/3059"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=264"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=264"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=264"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}