• Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

• get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

• put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

• The cache is initialized with a positive capacity.

Follow up:

• Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

• cache.put(1, 1);
• cache.put(2, 2);
• cache.get(1); // returns 1
• cache.put(3, 3); // evicts key 2
• cache.get(2); // returns -1 (not found)
• cache.put(4, 4); // evicts key 1
• cache.get(1); // returns -1 (not found)
• cache.get(3); // returns 3
• cache.get(4); // returns 4

• Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

• get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

• put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

• The cache is initialized with a positive capacity.

Follow up:

• Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);  
cache.put(2, 2);  
cache.get(1);       // returns 1  
cache.put(3, 3);    // evicts key 2  
cache.get(2);       // returns -1 (not found)  
cache.put(4, 4);    // evicts key 1  
cache.get(1);       // returns -1 (not found)  
cache.get(3);       // returns 3  
cache.get(4);       // returns 4

Accepted C++ without std:: notation

#include <list>
#include <unordered_map>


class LRUCache {
public:
    const int size;
    list<size_t> lru;
    unordered_map<int, list<size_t>::iterator> cache;
    unordered_map<int, int> key_val_map;

    LRUCache(const int capacity) : size(capacity) {}

    // Getter constant memory
    int get(int key) {
        if (key_val_map.count(key) == 0) {
            return -1;
        }

        update(key);
        return key_val_map[key];
    }

    // Setter constant memory
    const void put(int key, int value) {
        if (key_val_map.size() == size && key_val_map.count(key) == 0) {
            clear();
        }

        update(key);

        key_val_map[key] = value;
    }

    // Add a new key
    const void update(int key) {
        if (key_val_map.count(key)) {
            lru.erase(cache[key]);
        }

        lru.push_front(key);
        cache[key] = lru.begin();
    }


    // Erase cache
    const void clear() {
        key_val_map.erase(lru.back());
        cache.erase(lru.back());
        lru.pop_back();
    }
};

Accepted C++ with std:: notation

Accepted C++