LeetCode 146 LRU Cache: HashMap + Doubly Linked List, Explained Properly

LRU Cache is one of the most commonly reported coding questions in Indian product-company interviews, from Amazon and Microsoft to Flipkart, Swiggy and PhonePe, and a staple at FAANG. It sits at the boundary between DSA and design: there is no clever algorithm, just two data structures composed so that each covers the other's weakness. Interviewers use it to check whether you can reason about complexity per operation, manipulate pointers without bugs, and extend a design when requirements change. This walkthrough covers all three, with every implementation tested against LeetCode's examples and a randomised reference model.

The LRU Cache Problem

Design a cache with a fixed capacity that supports:

• get(key): return the value if present, else -1. A successful get counts as a use.
• put(key, value): insert or update. If inserting makes the size exceed capacity, evict the least recently used key first. An update also counts as a use.

Both operations must run in O(1) average time. That constraint is the whole problem.

Example with capacity 2: put(1,1), put(2,2), get(1) → 1, put(3,3) evicts key 2 (key 1 was used more recently), get(2) → -1, put(4,4) evicts key 1, get(1) → -1, get(3) → 3, get(4) → 4.

Why a HashMap Plus a Doubly Linked List

List what each operation needs, then pick structures that make every need O(1):

The list keeps order; the map gives direct access into the list. Why doubly linked? To unlink a node in O(1) you need its predecessor. With a singly linked list, finding the predecessor is O(n). With prev pointers, any node you reach through the map can be removed immediately. Why not a timestamp heap? It works but gives O(log n), and the interviewer specifically asked for O(1).

The Design: Sentinel Nodes and Three Helpers

Sentinels are dummy head and tail nodes that are always present. Every real node then always has a non-null prev and next, so insert and remove need no special cases for "empty list", "first node" or "last node". This removes the most common source of bugs in this problem.

Everything reduces to three helpers:

1. unlink(node): node.prev.next = node.next; node.next.prev = node.prev.
2. addToFront(node): splice it between head and head.next.
3. moveToFront(node): unlink, then add to front.

LRU Cache in Java (HashMap + Doubly Linked List)

class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0);   // sentinel: most recent side
    private final Node tail = new Node(0, 0);   // sentinel: least recent side

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToFront(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {                 // update existing: also a "use"
            node.value = value;
            moveToFront(node);
            return;
        }
        if (map.size() == capacity) {       // evict before inserting
            Node lru = tail.prev;
            unlink(lru);
            map.remove(lru.key);            // why nodes store the key
        }
        Node fresh = new Node(key, value);
        map.put(key, fresh);
        addToFront(fresh);
    }

    private void unlink(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void moveToFront(Node node) {
        unlink(node);
        addToFront(node);
    }
}

Order matters in addToFront: set the new node's own pointers first, then update head.next.prev before overwriting head.next. Reversing the last two lines makes head.next.prev point the new node at itself, a bug that only shows up on the second insert.

Complexity: get and put are O(1) average (one hash operation plus constant pointer work); space O(capacity).

LRU Cache in Python and C++

class Node:
    __slots__ = ("key", "value", "prev", "next")
    def __init__(self, key=0, value=0):
        self.key, self.value = key, value
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}
        self.head, self.tail = Node(), Node()     # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        node = self.map.get(key)
        if node is None:
            return -1
        self._unlink(node)
        self._add_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.map.get(key)
        if node:
            node.value = value
            self._unlink(node)
            self._add_front(node)
            return
        if len(self.map) == self.capacity:
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)

In C++, std::list is already a doubly linked list, and splice moves a node to another position in O(1) without invalidating iterators. Store list iterators in the map:

class LRUCache {
    int capacity;
    list<pair<int, int>> items;                                   // front = most recent
    unordered_map<int, list<pair<int, int>>::iterator> pos;       // key -> node in list
public:
    explicit LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        auto it = pos.find(key);
        if (it == pos.end()) return -1;
        items.splice(items.begin(), items, it->second);           // O(1) move to front
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = pos.find(key);
        if (it != pos.end()) {
            it->second->second = value;
            items.splice(items.begin(), items, it->second);
            return;
        }
        if ((int)items.size() == capacity) {
            pos.erase(items.back().first);
            items.pop_back();
        }
        items.emplace_front(key, value);
        pos[key] = items.begin();
    }
};

Is using std::list "cheating"? Usually not: it is a general-purpose container, not an LRU shortcut, and the design (map of iterators into a recency list) is still yours. Some interviewers will ask you to write the node struct anyway; the Java version above translates directly. The C++ STL cheat sheet explains why splice keeps the stored iterators valid.

Dry Run of the LeetCode Example

Edge cases to test aloud: capacity 1 (every new key evicts the previous one), put on an existing key when full (must not evict, since size does not grow), and repeated get on the same key (moving the front node to the front must be a harmless no-op, which the unlink-then-add sequence handles).

The LinkedHashMap and OrderedDict Shortcuts

Java's LinkedHashMap is a hash map threaded with a doubly linked list. Constructed with accessOrder = true, every get and put moves the entry to the end, and removeEldestEntry is a hook called after each insert:

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);        // true = access order, not insertion order
        this.capacity = capacity;
    }

    public int get(int key) { return super.getOrDefault(key, -1); }

    public void put(int key, int value) { super.put(key, value); }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.data:
            return -1
        self.data.move_to_end(key)          # mark as most recent
        return self.data[key]

    def put(self, key: int, value: int) -> None:
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)   # evict least recent

Python also has functools.lru_cache, but that is a memoisation decorator for function calls, not a key-value cache you can call put on. Strategy in interviews: mention the shortcut in one sentence, then offer to build it from scratch. Most interviewers say "build it"; a few are happy with the shortcut and move to follow-ups, which is a good outcome for you.

The LFU Cache Follow-Up (LeetCode 460)

Least Frequently Used evicts the key with the lowest use count, breaking ties by least recent use. Still O(1) per operation. The design:

• entries: key → (value, freq).
• buckets: freq → keys with that frequency, in LRU order (an insertion-ordered set; each bucket is effectively a small LRU list).
• minFreq: the smallest frequency currently present, so eviction knows which bucket to look in.

On every access, move the key from bucket f to bucket f + 1; if bucket f becomes empty and f was minFreq, increment minFreq. On insert of a new key, evict the oldest key in bucket minFreq if full, then insert with freq 1 and set minFreq = 1.

class LFUCache {
    private final int capacity;
    private int minFreq = 0;
    private final Map<Integer, int[]> entries = new HashMap<>();                 // key -> {value, freq}
    private final Map<Integer, LinkedHashSet<Integer>> buckets = new HashMap<>(); // freq -> keys, LRU first

    public LFUCache(int capacity) { this.capacity = capacity; }

    public int get(int key) {
        int[] e = entries.get(key);
        if (e == null) return -1;
        touch(key, e);
        return e[0];
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        int[] e = entries.get(key);
        if (e != null) {
            e[0] = value;
            touch(key, e);
            return;
        }
        if (entries.size() == capacity) {
            LinkedHashSet<Integer> keys = buckets.get(minFreq);
            int evict = keys.iterator().next();      // least recent among least frequent
            keys.remove(evict);
            if (keys.isEmpty()) buckets.remove(minFreq);
            entries.remove(evict);
        }
        entries.put(key, new int[]{value, 1});
        buckets.computeIfAbsent(1, f -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }

    private void touch(int key, int[] e) {
        int f = e[1];
        LinkedHashSet<Integer> keys = buckets.get(f);
        keys.remove(key);
        if (keys.isEmpty()) {
            buckets.remove(f);
            if (minFreq == f) minFreq = f + 1;
        }
        e[1] = f + 1;
        buckets.computeIfAbsent(f + 1, x -> new LinkedHashSet<>()).add(key);
    }
}

Why can minFreq only ever need "+1" during a touch? Because the touched key moves from f to f + 1, so if bucket f empties and it was the minimum, the new minimum is exactly f + 1, where that key now lives. On LeetCode's example (capacity 2: put 1, put 2, get 1, put 3, get 2, get 3, put 4, get 1, get 3, get 4) this returns 1, -1, 3, -1, 3, 4, and a Python port matched a brute-force model on hundreds of random operation sequences.

Production Follow-Ups: Thread Safety, TTL, Distributed Caches

Senior candidates (2+ YOE) often get pushed from the coding version into design questions. Prepare one-paragraph answers:

Thread safety

Even get mutates the list, so a read-write lock does not help much; reads are writes. The simplest correct answer is one mutex around both methods. For throughput, shard: N independent LRU caches selected by hash(key) % N, each with its own lock, giving approximate global LRU with far less contention. Production libraries such as Java's Caffeine go further by buffering recency updates and applying them in batches.

TTL (time-to-live)

Store an expiry timestamp per node. Lazy expiry: on get, if expired, delete and return a miss. Eager expiry: a min-heap or timer wheel by expiry time, or a background sweeper. Most real caches combine lazy checks with periodic sampling.

Distributed LRU

A single in-memory LRU does not scale across servers. Real systems partition keys across nodes with consistent hashing and run an eviction policy per node. Redis, for example, implements approximated LRU and LFU by sampling a few keys and evicting the best candidate, trading exactness for memory and speed; its maxmemory-policy options include allkeys-lru and allkeys-lfu. See the distributed cache system design and the Redis deep dive for the full picture.

Memory-bounded by bytes, not count

Track total size in bytes and evict from the tail in a loop until under budget. Large values may evict several small ones.

What Interviewers Look For in LRU Cache

• Structure justification before code. Explaining why each structure exists, and why doubly linked, is worth more than fast typing.
• Clean helpers. unlink, addToFront, moveToFront make the main methods read like the specification.
• No null-pointer bugs. Sentinels show experience.
• Correct handling of updates. put on an existing key updates value and recency without evicting.
• Extension readiness. LFU, TTL, thread safety. Also used in LLD rounds, where they expect interfaces (a Cache<K, V> with a pluggable EvictionPolicy) rather than a single class.

In machine-coding and LLD rounds at Indian product companies, LRU often appears as one component of a larger problem, for example an in-memory key-value store; the key-value store LLD shows how to wire it in behind a strategy interface.

Common LRU Cache Mistakes

1. Not storing the key in the node, then being unable to remove the evicted entry from the map in O(1).
2. Evicting on update. If the key exists, size does not change; check existence before capacity.
3. Mixing up the ends. If new nodes go to the front, eviction must take tail.prev. Inserting at one end and evicting from the same end throws away the newest entry, which the capacity-1 test case exposes immediately.
4. Wrong pointer order in addToFront, creating a self-loop.
5. Forgetting that get is a use and not moving the node.
6. Using a singly linked list or an ArrayList plus remove(Object), which is O(n).
7. Java: Integer comparison with == when checking values from the map; see the Integer caching pitfall.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.