LRU Cache: O(1) Get/Put via Hashmap + Linked List

9.1Problem Statement

Design an in-memory key-value cache with a fixed capacity and an eviction policy, suitable for embedding directly inside a service — think a per-process cache in front of a database call, not a distributed cache like Redis.

Functional requirements:

• get(key) returns the value if present, else signals a miss.
• put(key, value) inserts or updates; if the cache is at capacity, it must evict an entry per the active policy before inserting.
• The base policy is LRU — evict the least-recently-used entry.
• Both get and put must be O(1) average time. This is the load-bearing constraint; nothing in the design is allowed to scan.

Non-functional requirements / constraints:

• The eviction policy must be pluggable — LRU is the base case, but LFU and FIFO must drop in via a common EvictionPolicy interface without touching the cache's core logic. At SDE-3 level, this generalization is the point of the exercise, not just coding LRU correctly.
• The cache must be thread-safe for concurrent get/put calls.
• The cache must be generic over key and value types.

Expected public interface:

template <typename K, typename V>
class EvictionPolicy {                // Strategy
public:
    virtual void keyAccessed(const K& key) = 0;
    virtual K    evictKey() = 0;       // returns the key to remove
    virtual void keyAdded(const K& key) = 0;
    virtual ~EvictionPolicy() = default;
};

template <typename K, typename V>
class Cache {
public:
    Cache(size_t capacity, std::unique_ptr<EvictionPolicy<K,V>> policy);
    std::optional<V> get(const K& key);
    void put(const K& key, const V& value);
};

What the interviewer is really testing:

• The hashmap + doubly-linked-list mechanism for O(1) LRU — and whether you can justify why both structures are necessary, not just one.
• Whether you cleanly decouple the policy from the storage, so LFU/FIFO can swap in without editing Cache.
• The thread-safety answer: reach for a single mutex first, then talk intelligently about contention and sharded/striped locks as the natural next step.

Follow-up questions to expect:

1. Swap to LFU (frequency buckets) without changing the cache storage.
2. TTL / expiry per entry alongside capacity-based eviction.
3. Reduce lock contention: a sharded cache, partitioned by key hash.
4. Make it write-through / write-back to a backing store.

9.2How to Approach

Mine the hard constraints first, because they decide the design before you write a single class. "Both get and put must be O(1)" rules out anything that scans to find a victim. "Pluggable eviction policy" says the recency bookkeeping cannot live inside the same class as the key-value storage — that split is a seam, and the statement is telling you it's the seam it wants to see. "Thread-safe" means a mutex is a first-class requirement, not an afterthought bolted on at the end. "Generic over K and V" means templates from the first line.

Circle the nouns in the problem — cache, key, value, capacity, policy, eviction, recency, lock — and they hand you the class list almost for free: an EvictionPolicy<K,V> interface that owns the ordering rule; a concrete LRUEvictionPolicy<K,V> that implements it with a list plus a map; and a Cache<K,V> that is the public-facing orchestrator holding the values, the capacity, the policy, and the mutex. That's a textbook Strategy pattern: one interface, several interchangeable concrete strategies, and one context that holds a strategy pointer and never inspects which concrete strategy it was handed.

A first instinct for storage is std::unordered_map<K, V>, and that instinct is correct — it gives O(1) average lookup, insert, and erase by key. The interesting state doesn't live there, though. It lives inside the policy. The cache holds what the values are; the policy holds the order they should leave in. Don't over-model the leaf; spend your modeling effort where the algorithm actually is.

So why can't a plain hashmap alone give O(1) recency updates? Because a hashmap has no notion of order. The naive fix — stamp every entry with a "last used" timestamp, and on eviction scan every entry for the smallest one — is O(n) per eviction. That fails the O(1) requirement outright, and it's the single most common wrong turn candidates take into this problem.

The fix is two structures cooperating, each covering the other's blind spot:

       MRU (front)                          LRU (back / evict here)
        ┌────┬   ┌────┬   ┌────┬   ┌────┬
list:   │  D  │ ⇄ │  A  │ ⇄ │  C  │ ⇄ │  B  │
        └────┴   └────┴   └────┴   └────┴
           ▲         ▲         ▲         ▲
map:   key → iterator (node address) for each key, O(1) lookup

A doubly-linked list of keys orders them by recency: front is most-recently-used, back is least-recently-used. A hashmap from key to list iterator gives O(1) access to any node so it can be spliced out without walking the list. The list alone can't find a node by key without an O(n) scan; the map alone has no concept of order. Together: find-by-key is O(1) via the map, unlink-and-push-front is O(1) via the list, and eviction is O(1) — pop the back, erase from the map. The move that makes this legal is std::list::splice: it relinks a node in place without invalidating any iterator, which is exactly why the map is allowed to hold onto those iterators across reorders.

With the mechanism settled, the policy interface is deliberately narrow: it speaks only in keys, never in values. keyAdded tells it a brand-new key entered; keyAccessed tells it an existing key was touched; evictKey asks it to name a victim and forget it. It never sees a V. That "data-free-of-V" discipline is exactly what makes the same interface serve LRU, LFU, or FIFO — each just answers those three questions differently. Cache, the context, never computes recency itself; it only ever asks the policy "who's the victim?" and evicts before it inserts, so the store's size invariant never goes transiently over capacity.

The remaining follow-ups all resolve the same way: a new injected interface or a thin composition, never an edit to Cache's core. TTL becomes an expiry timestamp stored alongside the value, checked lazily on get. A sharded cache is N copies of the exact same Cache<K,V> wrapped by a router, reusing the single-cache code verbatim. Write-through/write-back is another injected strategy, orthogonal to eviction, sitting beside it rather than tangled with it. That pattern — new follow-up, new subclass or wrapper, zero edits to the core — is the open/closed principle, and pointing it out explicitly is what separates an LLD answer that merely works from one that reads as senior.

9.3Whole Solution

One synthesized, internally-consistent program: the EvictionPolicy Strategy interface, the LRU concrete strategy (hashmap + doubly-linked-list), the LFU concrete strategy (frequency buckets, included to prove the abstraction actually holds), the Cache context wired with a mutex, and a driver that exercises a hit, a miss, an eviction, and a live swap of the strategy.

#include <iostream>
#include <list>
#include <memory>
#include <mutex>
#include <optional>
#include <string>
#include <unordered_map>

// ============================================================
// Strategy interface: the eviction policy speaks only in keys.
// It owns *ordering*; Cache owns *data*. That split is what lets
// LRU / LFU / FIFO drop in without Cache ever changing.
// ============================================================
template <typename K, typename V>
class EvictionPolicy {
public:
    virtual void keyAccessed(const K& key) = 0;   // get or update touched this key
    virtual void keyAdded(const K& key)    = 0;   // a brand-new key was inserted
    virtual K    evictKey()                = 0;   // returns the key to remove
    virtual ~EvictionPolicy() = default;
};

// ============================================================
// Concrete strategy #1: LRU via hashmap + doubly-linked-list.
// front of order_ = most-recently-used, back = least-recently-used.
// pos_ maps key -> iterator into order_, so any node is O(1) reachable.
// ============================================================
template <typename K, typename V>
class LRUEvictionPolicy : public EvictionPolicy<K, V> {
public:
    void keyAccessed(const K& key) override {
        auto it = pos_.find(key);
        if (it == pos_.end()) return;              // not tracked yet; keyAdded handles new keys
        // splice relinks the node in place without invalidating any iterator,
        // including the one pos_ is holding for this key.
        order_.splice(order_.begin(), order_, it->second);
    }

    void keyAdded(const K& key) override {
        order_.push_front(key);
        pos_[key] = order_.begin();
    }

    K evictKey() override {
        K victim = order_.back();                  // back = least-recently-used
        order_.pop_back();
        pos_.erase(victim);
        return victim;
    }

private:
    std::list<K> order_;                                          // front = MRU, back = LRU
    std::unordered_map<K, typename std::list<K>::iterator> pos_;  // key -> its node
};

// ============================================================
// Concrete strategy #2: LFU via frequency buckets. Proves the
// Strategy seam holds -- Cache below needs zero edits to use this
// instead of LRU; only the constructor argument changes.
// ============================================================
template <typename K, typename V>
class LFUEvictionPolicy : public EvictionPolicy<K, V> {
public:
    void keyAdded(const K& key) override {
        freqOf_[key] = 1;
        buckets_[1].push_front(key);
        pos_[key] = buckets_[1].begin();
        minFreq_ = 1;                               // a new key is always freq 1
    }

    void keyAccessed(const K& key) override {
        int f = freqOf_[key];
        buckets_[f].erase(pos_[key]);                // pull out of old bucket
        if (buckets_[f].empty() && f == minFreq_) ++minFreq_;
        int nf = f + 1;
        freqOf_[key] = nf;
        buckets_[nf].push_front(key);                // promote to next bucket
        pos_[key] = buckets_[nf].begin();
    }

    K evictKey() override {
        auto& lst = buckets_[minFreq_];             // lowest freq; back = least-recent there
        K victim = lst.back();
        lst.pop_back();
        freqOf_.erase(victim);
        pos_.erase(victim);
        return victim;
    }

private:
    int minFreq_ = 0;
    std::unordered_map<K, int> freqOf_;                           // key -> frequency
    std::unordered_map<int, std::list<K>> buckets_;               // frequency -> keys at it
    std::unordered_map<K, typename std::list<K>::iterator> pos_;  // key -> its node
};

// ============================================================
// Context: owns the key->value store, the capacity bound, and the
// mutex. Delegates "who leaves" to whichever policy was injected.
// ============================================================
template <typename K, typename V>
class Cache {
public:
    Cache(size_t capacity, std::unique_ptr<EvictionPolicy<K, V>> policy)
        : capacity_(capacity), policy_(std::move(policy)) {}

    std::optional<V> get(const K& key) {
        std::lock_guard<std::mutex> lock(mutex_);   // get mutates recency: it's a writer
        auto it = store_.find(key);
        if (it == store_.end()) return std::nullopt;  // miss
        policy_->keyAccessed(key);                     // touch: now most-recently-used
        return it->second;
    }

    void put(const K& key, const V& value) {
        std::lock_guard<std::mutex> lock(mutex_);

        auto it = store_.find(key);
        if (it != store_.end()) {            // update existing key
            it->second = value;
            policy_->keyAccessed(key);
            return;
        }

        if (store_.size() >= capacity_) {    // at capacity -> evict before inserting
            K victim = policy_->evictKey();
            store_.erase(victim);
        }

        store_[key] = value;                 // insert new
        policy_->keyAdded(key);
    }

private:
    size_t capacity_;
    std::unordered_map<K, V> store_;                       // key -> value
    std::unique_ptr<EvictionPolicy<K, V>> policy_;         // the Strategy
    std::mutex mutex_;                                     // guards both above
};

// ============================================================
// Driver: exercise a hit, a miss, and an eviction under LRU, then
// swap in LFU against a fresh Cache to prove the abstraction holds.
// ============================================================
int main() {
    // --- LRU behavior ---
    auto lruPolicy = std::make_unique<LRUEvictionPolicy<int, std::string>>();
    Cache<int, std::string> cache(2, std::move(lruPolicy));   // capacity 2

    cache.put(1, "one");
    cache.put(2, "two");

    cache.get(1);              // touch 1 -> order: [1 (MRU), 2 (LRU)]
    cache.put(3, "three");     // at capacity -> evict LRU key (2), insert 3

    if (!cache.get(2))
        std::cout << "2 evicted (miss)\n";
    if (auto v = cache.get(1))
        std::cout << "1 = " << *v << "\n";   // one
    if (auto v = cache.get(3))
        std::cout << "3 = " << *v << "\n";   // three

    // --- Same Cache template, different strategy: LFU, zero edits to Cache ---
    Cache<int, std::string> lfuCache(2, std::make_unique<LFUEvictionPolicy<int, std::string>>());

    lfuCache.put(10, "ten");
    lfuCache.put(20, "twenty");
    lfuCache.get(10);            // freq(10) = 2, freq(20) = 1
    lfuCache.put(30, "thirty");  // at capacity -> evict least-frequent (20), insert 30

    if (!lfuCache.get(20))
        std::cout << "20 evicted (miss, lowest frequency)\n";
    if (auto v = lfuCache.get(10))
        std::cout << "10 = " << *v << "\n";
    if (auto v = lfuCache.get(30))
        std::cout << "30 = " << *v << "\n";

    return 0;
}

Strategy pattern

One interface (EvictionPolicy), several interchangeable concrete implementations (LRU/LFU/FIFO), and one context (Cache) that holds a pointer to the interface and never branches on which concrete type it was handed.

std::list::splice

Moves a node from one position in a linked list (or another list) to another in O(1), without invalidating any iterator to that node. That guarantee is what lets the hashmap keep caching iterators across reorders.

lock_guard / RAII

A stack object that acquires a mutex on construction and releases it on destruction, including when the function exits via an exception. Removes the class of bug where a lock is acquired but a return path forgets to release it.

Sharding

Splitting one cache into N independent sub-caches, each with its own mutex and policy, keyed by hash(key) % N. Trades one global lock (serializes everything) for N smaller locks (only keys landing in the same shard contend).