{"id":29,"date":"2018-03-10T00:00:27","date_gmt":"2018-03-10T00:00:27","guid":{"rendered":"https:\/\/sinyalee.com\/essays\/?p=29"},"modified":"2024-09-02T03:25:03","modified_gmt":"2024-09-02T03:25:03","slug":"leetcode-hard-146-lru-cache","status":"publish","type":"post","link":"https:\/\/sinyalee.com\/essays\/?p=29","title":{"rendered":"[LeetCode HARD] 146 LRU Cache"},"content":{"rendered":"

LeetCode has become the de facto go-to website for tech interviews. As a former competitive programmer, the LeetCode \u201chard\u201d, \u201cmedium\u201d, and \u201ceasy\u201d problems are more like \u201ceasy\u201d, \u201cvery easy\u201d, \u201cextremely easy\u201d for me. I think it would be a good idea for me to put my solutions of some of the LeetCode hard problems here. Hope it would be helpful for people who are preparing for tech interviews.<\/p>\n

This is my 5th LeetCode solution article, for\u00a0LeetCode Problem 146, LRU Cache<\/a>. This problem is not interesting but I found it a very useful interview problem because it works well to weed out people who cannot use basic data structures naturally.<\/p>\n

Problem<\/h3>\n

Write a key-value cache which has a maximum size and keeps the most recent used items.<\/p>\n

Solution<\/h3>\n

The most simple solution is to have a hash table with the key-value pairs and their last operation time. And then we also keep a queue of operations.<\/p>\n

Every time a key is access, we put the key into the back of the queue and then update the last operation time in the hash table. When the cache is oversize, we keep looking at the front of the queue to get the oldest operations, then compare it to the hash table to see if that operation is the latest operation for that element. If so, we should remove that element.<\/p>\n

Source Code (C++)<\/h4>\n
#include \n#include \n\nclass LRUCache {\npublic:\n    LRUCache(int capacity) {\n        _capacity = capacity;\n        _front = _back = 0;\n    }\n    \n    int get(int key) {\n        auto ret = _data.find(key);\n        if (ret == _data.end()) {\n            return -1;\n        }\n        \n        _lastOperation[key] = _back++;\n        _operations.push(key);\n        return ret->second;\n    }\n    \n    void put(int key, int value) {\n        _data[key] = value;\n        _operations.push(key);\n        _lastOperation[key] = _back++;\n        \n        while (_data.size() > _capacity && _operations.size() > 0) {\n            auto deleteKey = _operations.front();\n            \/\/ check if the oldest operation in the queue is the latest operation\n            \/\/ for the corresponding key.\n            if (_front == _lastOperation[deleteKey]) {\n                _data.erase(deleteKey);\n                _lastOperation.erase(deleteKey);\n            }\n            _front++;\n            _operations.pop();\n        }\n    }\n    \nprivate:\n    int _capacity;\n    std::unordered_map<int, int> _data;\n    std::unordered_map<int, long long> _lastOperation;\n    std::queue _operations;\n    long long _front, _back;\n};\n\n\/**\n * Your LRUCache object will be instantiated and called as such:\n * LRUCache* obj = new LRUCache(capacity);\n * int param_1 = obj->get(key);\n * obj->put(key,value);\n *\/\n\n<\/code><\/pre>\n
Complexity<\/h4>\n
Let\u00a0n<\/em>\u00a0be the number of operations. Then the total time complexity is\u00a0O(n)<\/em>\u00a0because hash table operation is\u00a0O(1)<\/em>\u00a0and there are at most\u00a0O(n)<\/em>\u00a0elements in the queue. Therefore the average time complexity for each operation is\u00a0O(1)<\/em>.<\/p>\n
The space complexity is\u00a0O(n)<\/em>\u00a0because the length of the queue is\u00a0n<\/em>\u00a0in the worst case. In the worst case, an operation can takes up to\u00a0O(n)<\/em>\u00a0if the queue is very long and we need to go over all the elements before we can reduce the size of the cache. In some special use case, for example if this cache is used by a web server, it is important to keep the latency low for every operation, and there are a lot of read operations and not so much write operations, this approach may not be ideal.<\/p>\n
A Better Solution<\/h3>\n
To have better space complexity and better worst case single operation time complexity, we can have a sorted list of keys, ordered by last operation time.<\/p>\n
To do this, we should use a doubly-linked list instead of a queue. Every time a key is accessed, we take it out of the list and put it to the back of the list. To do this, for each key, we need to store a pointer to that key in the linked list in the hash table.<\/p>\n
This way the time complexity is guaranteed\u00a0O(1)<\/em>\u00a0for every single operation and the space complexity is\u00a0O(capacity)<\/em>\u00a0instead of\u00a0O(n)<\/em>.<\/p>\n
However, this solution is a little bit harder to write because there are pointers. Also it is actually a little bit slower on LeetCode because of the doubly-linked list operations.<\/p>\n
Source Code (C++)<\/h4>\n
\n#include \n#include \n\nstruct LRUCacheNode {\n    int value;\n    std::list::iterator operation;\n};\n\nclass LRUCache {\npublic:\n    LRUCache(int capacity) {\n        _capacity = capacity;\n    }\n    \n    int get(int key) {\n        auto pt = _data.find(key);\n        if (pt == _data.end()) {\n            return -1;\n        }\n        _operations.erase(pt->second.operation);\n        pt->second.operation = _operations.insert(_operations.end(), key);\n        return pt->second.value;\n    }\n    \n    void put(int key, int value) {\n        auto pt = _data.find(key);\n        if (pt != _data.end())\n            _operations.erase(pt->second.operation);\n        _data[key] = {value, _operations.insert(_operations.end(), key)};\n        \n        while (_data.size() > _capacity) {\n            _data.erase(*_operations.begin());\n            _operations.pop_front();\n        }\n    }\n    \nprivate:    \n    int _capacity;\n    std::unordered_map<int, LRUCacheNode> _data;\n    std::list _operations;\n};\n\n\/**\n * Your LRUCache object will be instantiated and called as such:\n * LRUCache* obj = new LRUCache(capacity);\n * int param_1 = obj->get(key);\n * obj->put(key,value);\n *\/<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
LeetCode has become the de facto go-to website for tech interviews. As a former competitive programmer, the LeetCode \u201chard\u201d, \u201cmedium\u201d, and \u201ceasy\u201d problems are more like \u201ceasy\u201d, \u201cvery easy\u201d, \u201cextremely easy\u201d for me. I think it would be a good idea for me to put my solutions of some of the LeetCode hard problems here. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-29","post","type-post","status-publish","format-standard","hentry","category-coding"],"_links":{"self":[{"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/posts\/29","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=29"}],"version-history":[{"count":6,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/posts\/29\/revisions"}],"predecessor-version":[{"id":132,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=\/wp\/v2\/posts\/29\/revisions\/132"}],"wp:attachment":[{"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=29"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=29"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sinyalee.com\/essays\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=29"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}