LRU Cache

Introduction

Caches live at every level of modern computing — L1/L2/L3 on the CPU, page cache in the kernel, buffer pools in databases, HTTP caches in the browser, memoization tables in your code. They all share the same problem: memory is finite, so when the cache fills up, something has to go. Least Recently Used is the most common policy: evict whatever hasn’t been touched for the longest time.

Implementing LRU is not an algorithm problem. It is a data-structure composition problem. Your job is to pick two primitives whose operations are individually $O(1)$ and cross-link them so that every cache operation stays $O(1)$. That composition move — hash map for keyed lookup, doubly-linked list for ordered mutation, iterators to bridge them — shows up everywhere in systems code. Interviewers reach for LRU because recognizing it separates candidates who think in terms of algorithms from candidates who think in terms of data structures.

When no single data structure supports your operations at the target complexity, cross-link two that do.

If you’ve never composed stdlib containers this way, read the constant-time approach slowly. If you have, skip ahead to the splice and iterator-stability subsection — that’s where the interview signal hides.

What the interviewer is actually testing

Four signals, in priority order:

1. API instinct. Do you pin down the semantics of get on a miss, get on a hit (does it update order?), put on an existing key, and put at capacity — before writing a line?
2. Composition. Do you spot that no single standard container supports both $O(1)$ lookup-by-key and $O(1)$ ordered mutation? The leap from “I need one DS” to “I need two, cross-linked” is the core move.
3. Iterator / pointer invariants. When you store a std::list iterator inside a hash map, do you know why it stays valid across splice, push_front, and neighbor erasures? If you don’t, you’ll write a subtle dangling-iterator bug.
4. Idiomatic C++. splice, emplace_front, std::optional returns, move-only values, list::iterator as a value type — fluency here is the senior signal.

Problem statement

Clarifying questions — and why each one matters

LRU has more moving pieces than most one-function problems. Pinning semantics up front saves you from rewriting code mid-interview.

A mental framework — why one data structure is not enough

List every $O(1)$-capable container in the standard library. Hash maps give you $O(1)$ keyed lookup. Arrays give you $O(1)$ random access. Doubly-linked lists give you $O(1)$ insertion, deletion, and move-to-front when you already hold a pointer into them.

Now list the operations we need:

Every row needs two things: a keyed lookup AND an ordered mutation. No single container covers both in $O(1)$:

• A hash map alone has no notion of order.
• A linked list alone has no notion of keyed lookup.
• An ordered map (like std::map) gets you $O(\log n)$ keyed access to sorted-by-timestamp data — better than linear, but still not constant.

The move: use two containers and cross-link them. The hash map resolves the key to a node in the list in $O(1)$. The list maintains the MRU → LRU order and allows $O(1)$ splicing to its front. Neither half works alone; together they do.

Discussion

#include <algorithm>
#include <cstddef>
#include <optional>
#include <utility>
#include <vector>

template <typename K, typename V>
class LRUCacheBrute {
  public:
    explicit LRUCacheBrute(std::size_t capacity) : capacity_(capacity) {}

    std::optional<V> get(const K& key) {
        auto it = find(key);
        if (it == items_.end()) return std::nullopt;
        auto entry = std::move(*it);
        items_.erase(it);
        items_.insert(items_.begin(), std::move(entry));
        return items_.front().second;
    }

    void put(const K& key, V value) {
        if (auto it = find(key); it != items_.end()) {
            items_.erase(it);
        } else if (items_.size() >= capacity_) {
            items_.pop_back();
        }
        items_.insert(items_.begin(), {key, std::move(value)});
    }

  private:
    using Entry = std::pair<K, V>;
    std::vector<Entry> items_;  // MRU front → LRU back
    std::size_t capacity_;

    auto find(const K& key) {
        return std::find_if(items_.begin(), items_.end(),
                            [&](const Entry& e) { return e.first == key; });
    }
};

#include <cstddef>
#include <map>
#include <optional>
#include <unordered_map>
#include <utility>

template <typename K, typename V>
class LRUCacheLog {
  public:
    explicit LRUCacheLog(std::size_t capacity) : capacity_(capacity) {}

    std::optional<V> get(const K& key) {
        auto it = values_.find(key);
        if (it == values_.end()) return std::nullopt;
        touch(it);
        return it->second.first;
    }

    void put(const K& key, V value) {
        if (auto it = values_.find(key); it != values_.end()) {
            it->second.first = std::move(value);
            touch(it);
            return;
        }
        if (values_.size() == capacity_) {
            auto oldest = times_.begin();
            values_.erase(oldest->second);
            times_.erase(oldest);
        }
        const Stamp t = ++clock_;
        values_.emplace(key, std::pair{std::move(value), t});
        times_.emplace(t, key);
    }

  private:
    using Stamp = std::size_t;
    using ValueIter = typename std::unordered_map<K, std::pair<V, Stamp>>::iterator;

    std::unordered_map<K, std::pair<V, Stamp>> values_;
    std::map<Stamp, K> times_;
    std::size_t capacity_;
    Stamp clock_ = 0;

    void touch(ValueIter it) {
        times_.erase(it->second.second);
        const Stamp t = ++clock_;
        it->second.second = t;
        times_.emplace(t, it->first);
    }
};

#include <cstddef>
#include <list>
#include <optional>
#include <unordered_map>
#include <utility>

template <typename K, typename V>
class LRUCache {
  public:
    explicit LRUCache(std::size_t capacity) : capacity_(capacity) {}

    std::optional<V> get(const K& key) {
        auto it = index_.find(key);
        if (it == index_.end()) return std::nullopt;
        items_.splice(items_.begin(), items_, it->second);
        return it->second->second;
    }

    void put(const K& key, V value) {
        if (auto it = index_.find(key); it != index_.end()) {
            it->second->second = std::move(value);
            items_.splice(items_.begin(), items_, it->second);
            return;
        }
        if (items_.size() == capacity_) {
            index_.erase(items_.back().first);
            items_.pop_back();
        }
        items_.emplace_front(key, std::move(value));
        index_.emplace(key, items_.begin());
    }

  private:
    using Entry = std::pair<K, V>;
    using ListIt = typename std::list<Entry>::iterator;

    std::list<Entry> items_;                  // MRU at front, LRU at back
    std::unordered_map<K, ListIt> index_;     // key → node in the list
    std::size_t capacity_;
};

index_.erase(items_.back().first);  // read key, then erase from map
items_.pop_back();                  // erase node (this iterator only)
// ... now insert the new entry

Approach comparison

The constant-time solution is what you ship. State it out loud when you close.

Follow-ups to anticipate

Pattern recognition — compose two primitives via an iterator

The move LRU teaches generalizes to any problem where a single container can’t give you every operation in the target complexity:

• O(1) insert + O(1) remove-min on arbitrary elements. Intrusive heap node + a hash map from key to heap-node pointer. Same move: two DSes, one iterator bridge.
• Ordered set with O(1) random sample. std::unordered_set for membership, a std::vector for sampling, cross-linked via index. See LeetCode “Insert Delete GetRandom O(1).”
• LFU cache. Two layers of lists (keyed on frequency) bridged by a hash map.
• Median from a stream. Two heaps (max-heap lower half, min-heap upper half). No hash map needed, but the composition reflex is the same: no single heap gives you the median.
• Disjoint-set / union-find. Parent pointer array + rank-by-root — two arrays composed, one operation uses both.

The reflex you want: when the operations list has two or more entries whose $O(1)$ implementations live in different data structures, compose them. Pick the cheapest bridge — usually an iterator, an index, or a pointer — and store it on the side.

What to say out loud — the delivery script

Ten beats. Rehearse until fluid.

1. “Let me restate: a cache of capacity $n$ with get(key) and put(key, value), both $O(1)$, with LRU eviction.”
2. Ask the three clarifying questions: “Does get update order? What’s the return on a miss? Thread-safe?”
3. “The brute force is a vector in MRU-to-LRU order — $O(n)$ per op. Let me name that and move on.”
4. “I need $O(1)$ keyed lookup AND $O(1)$ ordered mutation. No single container does both.”
5. “The composition: a doubly-linked list holds the entries in MRU-to-LRU order. A hash map maps each key to its node — specifically, to a std::list iterator into the list.”
6. “On get hit, I splice the node to the front in $O(1)$ and return its value. On get miss, I return nullopt.”
7. “On put with an existing key, I update the value and splice to front. On put with a new key and no room, I evict the tail — read the key first, erase from the map, then pop_back the list — and then insert.”
8. Write the get — six lines. Trace through a hit and a miss.
9. Write the put — ten lines. Trace the eviction ordering: “critical: the read of items_.back().first must happen before pop_back.”
10. “std::list iterators are stable across splice and unrelated erasures. That’s what makes the stored iterator in the hash map safe. I’d ship this.”

Summary

LRU Cache looks like a systems-design question and turns out to be a data-structure composition drill. The move — combine a hash map and a doubly-linked list, bridge them with an iterator, promote on every touch with splice, evict from the tail — produces an $O(1)$ cache with about thirty lines of idiomatic C++. The pattern generalizes: whenever no single container gives you every operation at the target complexity, compose two and cross-link.

The interview signal is not the code length. It is recognizing the composition, stating the iterator-stability invariant aloud, and writing the eviction steps in the one correct order. Candidates who nail all three walk out distinguished.