Step 5 of 5

Challenge: an LRU cache

A least-recently-used cache keeps the capacity most recently used items and evicts the stalest one when full. It sits in front of databases, file systems and web servers everywhere, and it's one of the most common interview questions because it combines two structures:

• a std::list of (key, value) pairs ordered by recency (front = most recent),
• a std::unordered_map from key to the list iterator, for O(1) lookup.

list.splice(list.begin(), list, it) moves an element to the front in O(1) without invalidating any iterators, so the map stays correct.

Your turn: write LruCache with std::optional<int> get(int key) (a hit makes the key most recent) and void put(int key, int value) (insert or update, making it most recent; evict the least recent if over capacity). Both O(1).

Previous: Hashing your own keys