Implement an LRU Cache

System Design Interview•~25 min read•medium

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement get(key) and put(key, value) operations in O(1) average time complexity. When the cache reaches its capacity, it should invalidate and evict the least recently used key before inserting a new item.

1. Understand Requirements & Scope

Hash map provides O(1) key lookup, but doesn't track ordering. Array tracks order, but eviction/shifting is O(N). Doubly linked list allows O(1) node deletion and insertion when a pointer is held. Combining a Hash Map with a Doubly Linked List achieves O(1) for both get and put.

Functional Requirements:

Initialize LRUCache with positive capacity.
int get(int key) returns the value of the key if it exists, otherwise -1.
void put(int key, int value) updates the value of the key if it exists. Otherwise, add the key-value pair to the cache. If keys exceed capacity, evict least recently used key.
Both get and put operations must run in O(1) average time complexity.

2. Back-of-the-Envelope Capacity Estimation

• Memory footprint: 100,000 cached records × ~1 KB payload = 100 MB RAM budget.

• Time Complexity: get() and put() MUST both execute in strict O(1) average time.

• Space Complexity: O(Capacity) bounded overhead with zero memory leaks across sustained writes.

• Concurrency: Support thread-safe concurrent reads and writes with minimal lock contention.

• Eviction: Evict the Least Recently Used element strictly when cache size exceeds capacity.

3. High-Level Architecture Flow

Optimal O(1) LRU Cache implementation combines a doubly linked list (for O(1) order manipulation with dummy head and tail sentinel nodes) and a hash map (for O(1) key-to-node lookup).

[ Client get(k) / put(k, v) ]
               |
               v
      +------------------+
      |  HashMap (O(1))  |  (Key -> DoublyLinkedNode)
      +------------------+
               |
               v
+------+     +------+     +------+     +------+
| HEAD | <-> | Node | <-> | Node | <-> | TAIL |  (Doubly Linked List)
+------+     +------+     +------+     +------+
 [MRU]                                   [LRU]
 (Most Recently Used)                   (Evict candidate)

Fig 1. Architecture data flow and component topology.

4. Production Implementation & Code

class Node {
    int key, value;
    Node prev, next;
    Node(int k, int v) { this.key = k; this.value = v; }
}

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);

    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);
        remove(node);
        insertAtHead(node); // Move to most recently used
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            remove(map.get(key));
        } else if (map.size() >= capacity) {
            map.remove(tail.prev.key);
            remove(tail.prev); // Evict least recently used
        }
        Node newNode = new Node(key, value);
        insertAtHead(newNode);
        map.put(key, newNode);
    }

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

Hardened Implementation Sequence

Node contains key, value, prev, next pointers.
Dummy head and tail nodes avoid special cases for empty list and single-item updates.
get(key): if key in map, find node, removeNode(node), addNodeToHead(node), return node.val; else return -1.
put(key, val): if key exists, update val, move to head. If new, create node, add to head, insert into map. If size > capacity, remove tail.prev node, delete from map.

5. Key Decisions & Operational Mitigations

Architectural Decisions & Trade-Offs

•Storing key in Node: enables O(1) removal from the hash map when evicting tail.prev node (map.delete(tailNode.key)). Without key in Node, deleting from hash map would require an O(N) search through the map.
•Dummy Head & Tail: eliminates edge checks for head === null or tail === null in add and remove methods, drastically reducing bug surface.

Operational Hazards & Mitigations

•Concurrent access race conditions: Multiple threads mutating doubly-linked list pointers cause cyclic references and pointer corruption.
•Coarse-grained lock (ReentrantLock / Mutex): thread-safe, but serializes all reads and writes, creating CPU bottleneck under high concurrent read traffic.
•Read-write lock: allows concurrent reads, but in LRU every read (get) mutates the list to promote the accessed node, turning every read into a write lock! Solution: Read-Write lock with buffered access queues (like Caffeine Cache) or Clock/Second-Chance approximation.

Interactive Knowledge Check • Question 1 of 3↓

Interactive Practice Quiz•Question 1 of 3

intermediate

Single-Thread Execution Bottleneck

Why does Redis execute single-threaded command processing faster than traditional multi-threaded locked data structures?