LRU Cache

Problem

Implement the Least Recently Used (LRU) cache class LRUCache. The class should support the following operations

• LRUCache(int capacity) Initialize the LRU cache of size capacity.
• int get(int key) Return the value corresponding to 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 introduction of the new pair causes the cache to exceed its capacity, remove the least recently used key.

A key is considered used if a get or a put operation is called on it.

Ensure that get and put each run in O(1) average time complexity.

Examples

Example 1:

Input:
["LRUCache", [2], "put", [1, 10],  "get", [1], "put", [2, 20], "put", [3, 30], "get", [2], "get", [1]]

Output:
[null, null, 10, null, null, 20, -1]

Explanation:
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 10);  // cache: {1=10}
lRUCache.get(1);      // return 10
lRUCache.put(2, 20);  // cache: {1=10, 2=20}
lRUCache.put(3, 30);  // cache: {2=20, 3=30}, key=1 was evicted
lRUCache.get(2);      // returns 20 
lRUCache.get(1);      // return -1 (not found)

Constraints

• 1 <= capacity <= 100
• 0 <= key <= 1000
• 0 <= value <= 1000

You should aim for a solution with O(1) time for each put() and get() function call and an overall space of O(n), where n is the capacity of the LRU cache.

Solution

class LRUCache {
    struct Node {
        int key;
        int value;
    };
 
    // Front is most recent used, back is least recent used
    std::list<Node> lru;
    std::unordered_map<int, std::list<Node>::iterator> key_to_iter;
    int capacity;
 
public:
    LRUCache(int capacity) : capacity(capacity) { }
    
    int get(int key) {
        // Key doesn't exist
        if (!key_to_iter.contains(key)) { return -1; }
        auto iter = key_to_iter[key];
        // Move to front
        lru.splice(lru.begin(), lru, iter);
        return iter->value;
    }
    
    void put(int key, int value) {
        // If key exists, we update the value
        if (key_to_iter.contains(key)) {
            auto iter = key_to_iter[key];
            iter->value = value;
            lru.splice(lru.begin(), lru, iter);
            return;
        }
        // Key doesn't exist
        // Check if we are at capacity, if so remove
        if (lru.size() == capacity) {
            auto [old_key, old_value] = lru.back();
            key_to_iter.erase(old_key);
            lru.pop_back();
        }
        // Add to front
        lru.emplace_front(key, value);
        key_to_iter[key] = lru.begin();
    }
};