🗄️

Design LRU Cache

HashMap + doubly linked list for O(1) get/put — LeetCode 146 made interview-ready with capacity eviction and clear verbalization.

📊 Medium⏱ 25–35 min🏢 Amazon · Google · Microsoft · Meta · virtually all product SDE loops

🎯 Interview goal

Implement get(key) and put(key, value) with O(1) time. On capacity overflow, evict least-recently-used entry. Classic LinkedHashMap shortcut in Java — but interviewers often want the manual DLL version.

📋

The interview question

“Design an LRU cache with fixed capacity.” get returns -1 or null if missing; put inserts/updates and may evict LRU item.

Tests data structure fluency more than patterns — still mention why Map + list together.

💡

State O(1) goal upfront, then pick HashMap + DLL. Only use LinkedHashMap if interviewer allows Java stdlib.

❓

Clarifying questions (ask before coding)

1Capacity fixed at construction?

Why askConstructor LRUCache(capacity) — no dynamic resize in v1.

2Thread-safe?

Why askWrap in synchronized methods or ReentrantLock if yes.

3get() updates recency?

Why askYes — get counts as use; move node to MRU side.

4Generic types K, V?

Why askUse generics in Java; show you know typing.

✅

Requirements & assumptions (state aloud)

get(key): return value or sentinel if absent; mark as recently used.
put(key, value): insert or update; evict LRU if size > capacity.
O(1) average for both operations.
v1: single-threaded in-memory.

🧩

High-level design

HashMap maps key → Node in DLL. Head = MRU, tail = LRU.

On get/put: remove node from list, re-insert at head. Evict tail.prev when over capacity.

LRUCache — public API
Node — key, value, prev, next
Dummy head/tail sentinels simplify edge cases

LRU cache structure — HashMap points into doubly linked list

📐

UML class diagram (optional)

Small diagram — 2 classes enough for most interviewers.

LRU cache UML — LRUCache owns map + list nodes

🎨

Design patterns used (and why)

💡

If allowed: LinkedHashMap with accessOrder=true and removeEldestEntry — then explain manual version for rigor.

Pattern	Where	Why (interview soundbite)
📦Composite structure	Map + DLL	Combines O(1) lookup with O(1) reorder — not a GoF pattern but name the trick.

💻

Full solution — manual O(1) LRU

1. Node & cache skeletonjava

public class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0);
    private final Node tail = new Node(0, 0);

    // Sets max entries and wires dummy head/tail sentinels
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    private static class Node {
        int key, value;
        Node prev, next;

        // DLL node storing one cache entry
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    // Unlinks node from doubly linked list
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // Inserts node right after head (most recently used)
    private void insertAtHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

2. get & putjava

// Returns value and promotes key to MRU; -1 if missing
    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        remove(node);
        insertAtHead(node);
        return node.value;
    }

    // Inserts or updates entry; evicts LRU entry if over capacity
    public void put(int key, int value) {
        Node existing = map.get(key);
        if (existing != null) {
            existing.value = value;
            remove(existing);
            insertAtHead(existing);
            return;
        }
        Node node = new Node(key, value);
        map.put(key, node);
        insertAtHead(node);
        if (map.size() > capacity) {
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.key);
        }
    }
}

⚙️

Alternative — LinkedHashMap (if allowed)

3. LinkedHashMap one-liner stylejava

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

    // accessOrder=true: get/put reorder entries for LRU
    public LRUCacheLinkedHashMap(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    // Called after insert; removes oldest when size exceeds capacity
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }

    // Returns value or -1 if absent (still updates recency via accessOrder)
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    // Adds or updates key; may trigger removeEldestEntry
    public void put(int key, int value) {
        super.put(key, value);
    }
}

4. Demojava

public class LRUCacheDemo {
    // Shows get promoting entry and put evicting LRU key
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // 1
        cache.put(3, 3);                // evicts key 2
        System.out.println(cache.get(2)); // -1
    }
}

🎤

While you code — questions interviewers ask

🚀

Extensions & follow-ups

Thread-safe LRU with striped locks.
TTL per entry on top of LRU.
Distributed cache — HLD, consistent hashing.

⚠️

Common mistakes (fail signals)

O(n) eviction by scanning map.
Forgetting to move node on get.
Losing map entry on eviction (memory leak).

🧾

60-second cheat sheet

StructureHashMap + DLL, head=MRU, tail=LRU

get/putRemove node → push to head → evict tail.prev

ComplexityO(1) time, O(capacity) space

Java shortcutLinkedHashMap accessOrder + removeEldestEntry

🔗