So, I was asked to implement an LRU cache a few years ago in an interview with Oracle, which I couldn’t quite solve on my own in O(1). Recently I found this problem on LeetCode and I can say this time it was not a big deal, here is my solution.

#include <iostream>

#include <list>
#include <optional>
using std::list;

#include <unordered_map>
#include <cassert>

using std::unordered_map;

struct Entry {
    int key, value;
};

class LRUCache {
private:
    size_t capacity;
    list<Entry> L;
    unordered_map<int, list<Entry>::iterator> M;

public:
    explicit LRUCache(size_t capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        if (M.count(key) == 0) {
            return -1;
        }

        // Move entry to the front
        auto it = M[key];
        L.erase(it);

        L.push_front({*it});
        M[key] = L.begin();

        return it->value;
    }

    void put(int key, int value) {
        if (M.count(key) == 1) {
            // Move existing entry to the front
            L.erase(M[key]);
            L.push_front({key, value});
            M[key] = L.begin();
            return;
        }

        // Evict least-recently used entry
        if (L.size() >= capacity) {
            auto it = std::prev(L.end());
            M.erase(it->key);
            L.erase(it);
        }

        // Insert new entry at the front
        L.push_front({key, value});
        M[key] = L.begin();
    }
};

int main() {
    LRUCache cache(5);
    for (int v : {1, 2, 3, 4, 5}) {
        cache.put(v, 2 * v);
    }

    // At this point, the cache is full, so the first element inserted(1) should be evicted
    cache.put(6, 2 * 6);
    assert(cache.get(1) == -1);

    // This should bring 2 to the front and send 3 to the last position
    assert(cache.get(2) == 4);

    // This should put 7 in the first position and evict 3
    cache.put(7, 2 * 7);
    assert(cache.get(3) == -1);

    return EXIT_SUCCESS;
}

I know, my tests are not exhaustive, but hey, it’s better than nothing and it was accepted. I hope you find it kind of interesting and more importantly, that it could help you understand how this data structure works.