MediumStacks & Queues

LRU Cache

hash-mapdoubly-linked-listdesign

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class with capacity k:

get(key) — return the value if the key exists, otherwise return -1
put(key, value) — update or insert. If the number of keys exceeds capacity, evict the least recently used key.

Examples

Example 1

Input: capacity=2; put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4)

Output: 1, -1, -1, 3, 4

Explanation: After put(3,3) key 2 is evicted (LRU). After put(4,4) key 1 is evicted.

Constraints

•1 <= capacity <= 3000
•0 <= key <= 10^4
•At most 2*10^5 calls to get and put.

Hints

Hint 1

A HashMap alone gives O(1) key lookup but no way to track recency; a doubly linked list alone gives O(1) reordering but no O(1) key lookup — combining both is what gets you O(1) on every operation.

Hint 2

The HashMap maps key -> LIST NODE (not key -> value directly) — that node reference is what lets you splice it out of its current position in O(1) without searching the list.

Hint 3

Java's built-in LinkedHashMap (with accessOrder=true) already implements this exact combination internally — worth knowing as the 'if I were allowed a library' answer, contrasted with the from-scratch version an interview usually wants.

Solutions

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

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

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        moveToFront(node);   // mark as recently used
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = value;
            moveToFront(node);
        } else {
            if (map.size() == capacity) {
                Node lru = tail.prev;  // least recently used
                remove(lru);
                map.remove(lru.key);
            }
            Node node = new Node(key, value);
            map.put(key, node);
            addToFront(node);
        }
    }

    private void remove(Node n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }
    private void addToFront(Node n) {
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
    }
    private void moveToFront(Node n) { remove(n); addToFront(n); }

    private static class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }
}

Time: O(1) get and put · Space: O(capacity)