Design an LRU Cache

Problem Description#

A Least Recently Used (LRU) cache is a fixed-capacity store that automatically evicts the item that was accessed least recently when space runs out. It is one of the most common LLD interview questions because it sits at the intersection of two classic data structures — a HashMap for O(1) lookup and a doubly linked list for O(1) ordered eviction.

The interesting design challenge is not the data structures themselves but how to separate concerns cleanly: the cache API, the raw key-value storage, and the eviction bookkeeping should each live in their own class so the eviction policy can be swapped without touching storage logic.

Thread safety is also a requirement — multiple threads reading and writing concurrently must not corrupt the access-order list or the backing map.

Clarify Requirements#

Functional

• put(key, value) — insert or update a key-value pair; if the cache is at capacity, evict the least-recently-used entry first
• get(key) — return the value for a key and mark it as most-recently-used; return "null" if the key is absent
• Capacity is fixed and set at construction time

Non-functional

• Both get and put must run in O(1) time
• The cache must be thread-safe for concurrent access
• The eviction strategy should be swappable without touching storage or the public API

Final Requirements#

• Fixed-capacity cache initialised at construction time
• get(key) returns value if present and promotes the key to most-recently-used; returns "null" otherwise
• put(key, value) inserts or updates the entry; evicts the LRU key when at capacity
• O(1) time complexity for both operations
• Eviction logic is fully decoupled from storage logic via a dedicated EvictionEngine

Core Entities#

Patterns Used#

Strategy Pattern#

The EvictionEngine is a self-contained eviction strategy. Cache and Storage program to it through method calls (KeyAccessed, EvictKey), not through any hard-coded LRU logic. To swap in an LFU or FIFO policy you replace only the engine without touching Cache or Storage.

Single Responsibility Principle#

Each class has exactly one reason to change: Storage changes when the backing data structure changes; EvictionEngine changes when the eviction algorithm changes; Cache changes only when the public API changes.

Code#

Cache and Storage#

Cache is the entry point. It owns both collaborators and coordinates between them — calling evictionEngine.KeyAccessed after every successful read or write, and leaving capacity management entirely to Storage.

import java.util.Objects;

public class Cache {
    private final Storage storage;
    private final EvictionEngine evictionEngine;

    public Cache(int capacity) {
        this.storage = new Storage(capacity);
        this.evictionEngine = new EvictionEngine();
    }

    public String getKey(int key) {
        String resultValue = storage.getKey(key);
        if (!Objects.equals(resultValue, "null"))
            evictionEngine.KeyAccessed(key);
        return resultValue;
    }

    public void putKey(int key, String value) {
        storage.addKey(key, value, evictionEngine);
        evictionEngine.KeyAccessed(key);
    }
}

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

public class Storage {
    private final int capacity;
    private final Map<Integer, String> storage;

    public Storage(int capacity) {
        this.capacity = capacity;
        this.storage = new HashMap<>();
        System.out.println("Cache Storage set to " + this.capacity);
    }

    public void addKey(int key, String value, EvictionEngine evictionEngine) {
        if (storage.containsKey(key)) {
            storage.remove(key);
        }
        if (storage.size() == capacity) {
            int evictedKey = evictionEngine.EvictKey();
            System.out.println("Evicting key: " + evictedKey);
            storage.remove(evictedKey);
        }
        storage.put(key, value);
    }

    public String getKey(int key) {
        return storage.getOrDefault(key, "null");
    }
}

Eviction Engine#

EvictionEngine maintains a HashMap<key → node> for O(1) node lookup and a DoublyLinkedList where the head is the most-recently-used key and the tail is the least-recently-used. On every access the node is detached from its current position and re-inserted at the head.

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

public class EvictionEngine {
    Map<Integer, DoublyLinkedListNode> nodes;
    DoublyLinkedList doublyLinkedList;

    public EvictionEngine() {
        this.doublyLinkedList = new DoublyLinkedList();
        nodes = new HashMap<>();
    }

    public void KeyAccessed(int key) {
        if (nodes.containsKey(key)) {
            DoublyLinkedListNode existing = nodes.get(key);
            doublyLinkedList.detachNode(existing);
        }
        DoublyLinkedListNode node = new DoublyLinkedListNode(key);
        nodes.put(key, node);
        doublyLinkedList.addNode(node);
    }

    public int EvictKey() {
        DoublyLinkedListNode node = doublyLinkedList.getOldest().prev;
        int evictedKey = node.getKey();
        doublyLinkedList.detachNode(node);
        nodes.remove(evictedKey);
        return evictedKey;
    }
}

Doubly Linked List#

The list uses two permanent sentinel nodes (latest and oldest) so that insert and remove never have to special-case null neighbours.

public class DoublyLinkedList {
    private final DoublyLinkedListNode latest;
    private final DoublyLinkedListNode oldest;

    public DoublyLinkedList() {
        this.latest = new DoublyLinkedListNode(-1);
        this.oldest = new DoublyLinkedListNode(-1);
        latest.next = oldest;
        oldest.prev = latest;
    }

    public void detachNode(DoublyLinkedListNode node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }

    public void addNode(DoublyLinkedListNode node) {
        node.prev = latest;
        node.next = latest.next;
        latest.next = node;
        node.next.prev = node;
    }

    public DoublyLinkedListNode getLatest() { return latest; }
    public DoublyLinkedListNode getOldest() { return oldest; }
}

import lombok.Getter;

public class DoublyLinkedListNode {
    @Getter
    private final int key;
    public DoublyLinkedListNode prev;
    public DoublyLinkedListNode next;

    public DoublyLinkedListNode(int key) {
        this.key = key;
    }
}

Demo#

public class CacheDemo {
    public static void main(String[] args) {
        Cache cache = new Cache(3);

        cache.putKey(1, "Value 1");
        cache.putKey(2, "Value 2");
        cache.putKey(3, "Value 3");

        System.out.println(cache.getKey(1)); // Value 1  — promotes key 1
        System.out.println(cache.getKey(2)); // Value 2  — promotes key 2
        // Access order (MRU→LRU): 2, 1, 3

        cache.putKey(4, "Value 4"); // capacity full → evicts key 3 (LRU)

        System.out.println(cache.getKey(3)); // null — evicted
        System.out.println(cache.getKey(4)); // Value 4

        cache.putKey(2, "Updated Value 2"); // update existing key

        System.out.println(cache.getKey(1)); // Value 1
        System.out.println(cache.getKey(2)); // Updated Value 2
    }
}

Class Diagram#

Extendible — Follow Ups#

Swap in a different eviction policy#

The EvictionEngine is the only place that knows about LRU. Extract an EvictionPolicy interface with keyAccessed(key) and evict() methods, then provide LRUEvictionPolicy, LFUEvictionPolicy, and FIFOEvictionPolicy implementations. Cache selects a policy at construction time — no other class changes.

Add TTL (time-to-live) expiry#

Store an expiry timestamp alongside each value in Storage. A background thread (or lazy check on get) compares the current time against the expiry and removes stale entries before they are served. The eviction engine can be extended to also track expiry order in a min-heap keyed on expiry time.

Make it thread-safe#

Wrap Storage operations and EvictionEngine state updates in a ReentrantReadWriteLock — multiple concurrent reads can proceed simultaneously, while a write locks exclusively. Alternatively use ConcurrentHashMap for storage and a synchronized linked list, being careful to hold both locks together when a put must evict.

Scale to a distributed cache#

Partition the key space with consistent hashing across N nodes. Each node runs the same single-node cache. A CacheRouter maps a key to the responsible node and forwards get/put calls over the network, making the distributed cache look like a single Cache to callers.