LRU Cache

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

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input [“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] Output [null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // cache is {1=1} lRUCache.put(2, 2); // cache is {1=1, 2=2} lRUCache.get(1); // return 1 lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3} lRUCache.get(2); // returns -1 (not found) lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3} lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4

Constraints:

• 1 <= capacity <= 3000
• 0 <= key <= 104
• 0 <= value <= 105
• At most 2 * 105 calls will be made to get and put.

Approach: HashMap + Doubly Linked List

Algorithm

1. Maintain a HashMap mapping keys to list nodes for O(1) lookups
2. Maintain a doubly linked list where the head side holds the most recently used entry and the tail side holds the least recently used entry
3. get(key): if absent return -1; otherwise move the node to the head and return its value
4. put(key, value): if the key exists, update the value and move the node to the head; otherwise insert a new node at the head. If the size exceeds the capacity, remove the node at the tail and its map entry
5. Use dummy head and tail sentinels to simplify boundary handling

Time & Space Complexity

• Time Complexity: O(1) for both get and put
• Space Complexity: O(capacity) - the hash map and the doubly linked list store at most capacity nodes

Java Implementation

import java.util.HashMap;
import java.util.Map;

public class LRUCache {

    private static class Node {
        int key;
        int value;
        Node prev;
        Node 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);
    private final Node tail = new Node(0, 0);

    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;
        }
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
            return;
        }
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        addToHead(newNode);

        if (map.size() > capacity) {
            Node last = tail.prev;
            removeNode(last);
            map.remove(last.key);
        }
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

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

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

    // Test method
    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1);          // cache is {1=1}
        lRUCache.put(2, 2);          // cache is {1=1, 2=2}
        System.out.println(lRUCache.get(1));    // return 1
        lRUCache.put(3, 3);          // evicts key 2
        System.out.println(lRUCache.get(2));    // return -1 (not found)
        lRUCache.put(4, 4);          // evicts key 1
        System.out.println(lRUCache.get(1));    // return -1 (not found)
        System.out.println(lRUCache.get(3));    // return 3
        System.out.println(lRUCache.get(4));    // return 4
        // Expected: 1, -1, -1, 3, 4
    }
}

Example Walkthrough

With capacity 2:

1. put(1,1): add node 1 to the head. Order (MRU to LRU): 1
2. put(2,2): add node 2 to the head. Order: 2, 1
3. get(1): move 1 to the head. Order: 1, 2. Return 1
4. put(3,3): add 3 to the head; size exceeds 2, evict tail node 2. Order: 3, 1
5. get(2): not in the map, return -1
6. put(4,4): add 4 to the head; evict tail node 1. Order: 4, 3
7. get(1): -1; get(3): 3; get(4): 4

Key Points

1. Doubly Linked List: Enables O(1) node removal and insertion at either end
2. Hash Map: Maps key to node for O(1) access, and the node itself carries the key for eviction
3. Sentinels: Dummy head and tail avoid null checks on boundary operations
4. Recency Order: MRU at the head, LRU at the tail; every access moves the node to the head
5. Eviction: When over capacity, remove the tail node and delete its map entry