146

146. LRU Cache (Medium)

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

 

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

 

Constraints:

• 1 <= capacity <= 3000
• 0 <= key <= 104
• 0 <= value <= 105
• At most 2 * 105 calls will be made to get and put.

Companies: Amazon, Google, TikTok

Related Topics:
Hash Table, Linked List, Design, Doubly-Linked List

Similar Questions:

• LFU Cache (Hard)
• Design In-Memory File System (Hard)
• Design Compressed String Iterator (Easy)
• Design Most Recently Used Queue (Medium)

Note

I usually forgot that I need to store the <key, value> pair in the list which is needed when evicting least recently used item.

We'd better write the logic as comments first, then we can find the detailed data structure we need and see if there is any common utility function that we can extract.

Need to remember the signature of the splice function: toList.splice(toListIterator, fromList, fromListIterator) is moving the data pointed by the fromListIterator from the fromList into the position pointed by the toListIterator within the toList.

Solution 1.

Use a list<pair<int, int>> data to store the key-value pairs, unordered_map<int, list<pair<int, int>>::iterator> m to store the mapping from key to the corresponding iterator pointing into data.

The constructor LRUCache is trivial, just storing the capacity as member.

The get logic is:

• If the key cannot be found in m, return -1.
• Otherwise, move the key-value pair pointed by m[key] to the front of data. And update m[key] to point to the front of data. Return the value data.front().second.

The put logic is:

• Use get(key) to test the existance of the key.
  • If not found,
    • Emit the last key-value pair, if the data storage is full.
    • Then insert the key-value pair to the front of data and update m[key] accordingly.
  • Otherwise, just update data.front().second to be value.

// OJ: https://leetcode.com/problems/lru-cache
// Author: github.com/lzl124631x
// Time:
//    LRUCache: O(1)
//    get: O(1)
//    put: O(1)
// Space: O(N)
class LRUCache {
    int capacity;
    typedef pair<int, int> Node;
    list<Node> data;
    typedef list<Node>::iterator Iterator;
    unordered_map<int, Iterator> m;
    void moveToFront(int key) {
        auto node = m[key];
        data.splice(data.begin(), data, node);
        m[key] = data.begin();
    }
public:
    LRUCache(int capacity) : capacity(capacity) {}
    int get(int key) {
        // get node given key, put the node at the beginning of the list, return the value in the node
        if (m.count(key)) {
            moveToFront(key);
            return m[key]->second;
        }
        return -1;
    }
    void put(int key, int value) {
        // if key exists in the map, get node given key, put the node at the beginning of the list and update the value in the node
        // otherwise, put a new node at the beginning of the list with the <key, value> and update the map. If capacity exceeded, remove the last node from the list and map.
        if (m.count(key)) {
            moveToFront(key);
            m[key]->second = value;
        } else {
            data.emplace_front(key, value);
            m[key] = data.begin();
            if (data.size() > capacity) {
                m.erase(data.back().first);
                data.pop_back();
            }
        }
    }
};

We can also leverage get in put

// OJ: https://leetcode.com/problems/lru-cache
// Author: github.com/lzl124631x
// Time:
//    LRUCache: O(1)
//    get: O(1)
//    put: O(1)
// Space: O(N)
class LRUCache {
    int capacity;
    typedef pair<int, int> Node;
    list<Node> data;
    typedef list<Node>::iterator Iterator;
    unordered_map<int, Iterator> m;
public:
    LRUCache(int capacity) : capacity(capacity) {}
    int get(int key) {
        if (m.count(key)) {
            auto node = m[key];
            data.splice(data.begin(), data, node);
            m[key] = data.begin();
            return node->second;
        }
        return -1;
    }
    void put(int key, int value) {
        if (get(key) == -1) {
            data.emplace_front(key, value);
            m[key] = data.begin();
            if (data.size() > capacity) {
                m.erase(data.back().first);
                data.pop_back();
            }
        } else data.front().second = value;
    }
};