Design an LRU Cache (OOD): LLD Interview in Java

Build a generic, O(1) Least Recently Used cache in Java with a HashMap and a doubly linked list, then make it thread-safe and extensible.

Requirements

An LRU (Least Recently Used) cache holds a fixed number of entries. When it is full and a new key arrives, it evicts the entry that was used longest ago. "Used" means read or written.

Functional

get(key): return the value (or null if absent) and mark the key as most recently used.
put(key, value): insert or update; if inserting into a full cache, evict the least recently used entry first.
remove(key), size(), and a fixed capacity set at construction.
Optional: an eviction listener so callers can react (e.g. write back, log metrics).

Non-functional

get and put in O(1) time.
O(capacity) memory.
Generic over key and value types.
A thread-safe variant for concurrent use.

Tip

Confirm whether get on a missing key returns null, Optional, or throws, and whether put on an existing key counts as a "use". The standard answer: null and yes.

Why HashMap + Doubly Linked List

Need	Structure	Cost
Find an entry by key	`HashMap<K, Node>`	O(1)
Move an entry to "most recent"	Doubly linked list (unlink + insert at head)	O(1) given the node
Find the least recent entry	Tail of the list	O(1)
Remove the least recent entry	Unlink tail node + remove its key from the map	O(1)

A singly linked list fails: unlinking a node needs its predecessor, which costs O(n) to find.
An array or ArrayList fails: moving an element to the front shifts everything, O(n).
Each node stores its key so that, when the tail is evicted, we can also delete it from the map.

Insight

Sentinel head and tail nodes remove every null check: the list is never empty from the code's point of view, so addFirst and unlink are four pointer assignments each, with no special cases for the first or last element.

Class Design

classDiagram
  class LRUCache {
    -int capacity
    -Map index
    -Node head
    -Node tail
    -BiConsumer evictionListener
    +get(K) V
    +put(K, V) void
    +remove(K) V
    +containsKey(K) boolean
    +size() int
    -moveToFront(Node) void
    -addFirst(Node) void
    -unlink(Node) void
  }
  class Node {
    +K key
    +V value
    +Node prev
    +Node next
  }
  class SynchronizedLRUCache {
    -LRUCache delegate
    +get(K) V
    +put(K, V) void
    +remove(K) V
    +size() int
  }
  LRUCache "1" *-- "many" Node : owns
  SynchronizedLRUCache --> LRUCache : delegates to

Design choices:

Node is a private static nested class: an implementation detail no caller should see.
LRUCache is not thread-safe by itself (like HashMap). Thread safety is layered on with a decorator, so single-threaded users do not pay for locking.
The eviction listener is a BiConsumer<K, V>, defaulting to a no-op, so callers can plug in behaviour without subclassing.

Java Implementation

The whole program compiles as one Main.java (Java 17+). The list is ordered from most recently used (after head) to least recently used (before tail).

java

import java.util.HashMap;
import java.util.Map;
import java.util.function.BiConsumer;

class LRUCache<K, V> {

    private static final class Node<K, V> {
        final K key;
        V value;
        Node<K, V> prev, next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<K, Node<K, V>> index;
    private final Node<K, V> head = new Node<>(null, null);   // sentinel: most recently used side
    private final Node<K, V> tail = new Node<>(null, null);   // sentinel: least recently used side
    private final BiConsumer<K, V> evictionListener;

    LRUCache(int capacity) {
        this(capacity, (k, v) -> { });
    }

    LRUCache(int capacity, BiConsumer<K, V> evictionListener) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity;
        this.index = new HashMap<>(capacity * 4 / 3 + 1);
        this.evictionListener = evictionListener;
        head.next = tail;
        tail.prev = head;
    }

    /** Returns the value or null, and marks the entry as most recently used. */
    V get(K key) {
        Node<K, V> node = index.get(key);
        if (node == null) return null;
        moveToFront(node);
        return node.value;
    }

    /** Inserts or updates; evicts the least recently used entry when full. */
    void put(K key, V value) {
        Node<K, V> node = index.get(key);
        if (node != null) {
            node.value = value;
            moveToFront(node);
            return;
        }
        if (index.size() == capacity) {
            Node<K, V> lru = tail.prev;
            unlink(lru);
            index.remove(lru.key);
            evictionListener.accept(lru.key, lru.value);
        }
        Node<K, V> fresh = new Node<>(key, value);
        index.put(key, fresh);
        addFirst(fresh);
    }

    V remove(K key) {
        Node<K, V> node = index.remove(key);
        if (node == null) return null;
        unlink(node);
        return node.value;
    }

    boolean containsKey(K key) { return index.containsKey(key); }   // does not change recency
    int size() { return index.size(); }
    int capacity() { return capacity; }

    private void moveToFront(Node<K, V> node) {
        unlink(node);
        addFirst(node);
    }

    private void addFirst(Node<K, V> node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void unlink(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = node.next = null;
    }

    @Override
    public String toString() {   // most recently used first
        StringBuilder sb = new StringBuilder("[");
        for (Node<K, V> n = head.next; n != tail; n = n.next) {
            sb.append(n.key).append('=').append(n.value);
            if (n.next != tail) sb.append(", ");
        }
        return sb.append(']').toString();
    }
}

/** Decorator: one lock guards both the map and the list, so every operation is atomic. */
class SynchronizedLRUCache<K, V> {
    private final LRUCache<K, V> delegate;

    SynchronizedLRUCache(int capacity) { this.delegate = new LRUCache<>(capacity); }

    synchronized V get(K key) { return delegate.get(key); }
    synchronized void put(K key, V value) { delegate.put(key, value); }
    synchronized V remove(K key) { return delegate.remove(key); }
    synchronized int size() { return delegate.size(); }
}

public class Main {
    public static void main(String[] args) throws InterruptedException {
        LRUCache<String, Integer> cache = new LRUCache<>(3,
                (k, v) -> System.out.println("  evicted " + k + "=" + v));

        cache.put("a", 1);
        cache.put("b", 2);
        cache.put("c", 3);
        System.out.println("after a,b,c        : " + cache);

        System.out.println("get(a)             : " + cache.get("a"));
        System.out.println("order now          : " + cache);

        System.out.println("put(d) -> full");
        cache.put("d", 4);
        System.out.println("after d            : " + cache);
        System.out.println("get(b)             : " + cache.get("b"));

        cache.put("c", 30);
        System.out.println("update c=30        : " + cache);

        System.out.println("put(e) -> full");
        cache.put("e", 5);
        System.out.println("after e            : " + cache);

        System.out.println("remove(c)          : " + cache.remove("c"));
        System.out.println("final              : " + cache + " size=" + cache.size());

        SynchronizedLRUCache<Integer, Integer> shared = new SynchronizedLRUCache<>(100);
        Thread[] workers = new Thread[4];
        for (int t = 0; t < workers.length; t++) {
            final int offset = t * 1_000;
            workers[t] = new Thread(() -> {
                for (int i = 0; i < 1_000; i++) {
                    shared.put(offset + i, i);
                    shared.get(offset + i / 2);
                }
            });
            workers[t].start();
        }
        for (Thread w : workers) w.join();
        System.out.println("concurrent size    : " + shared.size() + " (capacity 100)");
    }
}

Demo output

text

after a,b,c        : [c=3, b=2, a=1]
get(a)             : 1
order now          : [a=1, c=3, b=2]
put(d) -> full
  evicted b=2
after d            : [d=4, a=1, c=3]
get(b)             : null
update c=30        : [c=30, d=4, a=1]
put(e) -> full
  evicted a=1
after e            : [e=5, c=30, d=4]
remove(c)          : 30
final              : [e=5, d=4] size=2
concurrent size    : 100 (capacity 100)

Trace the important steps:

After get(a), a jumps to the front, so b becomes least recently used and is evicted by put(d).
Updating c moves it to the front without changing the size.
put(e) evicts a, which had drifted to the tail.
Four threads hammering the synchronized wrapper never push the size past capacity.

Thread Safety

Every get mutates the list (it moves a node to the front). That single fact rules out several "obvious" approaches.

Approach	How	Verdict
`synchronized` methods (decorator above)	One lock around map + list	Correct and simple; all operations serialize, so throughput is limited under heavy contention
`ReentrantReadWriteLock`	Read lock for `get`, write lock for `put`	Incorrect as-is: `get` reorders the list, so it needs the write lock, and then it is no better than `synchronized`. Only `containsKey` or `peek` could use the read lock
`ConcurrentHashMap` + `ConcurrentLinkedDeque`	Map for lookup, deque for recency	Each structure is thread-safe, but the pair is not: map and deque updates are not atomic together, so entries can be duplicated, lost, or evicted while being read. `deque.remove(key)` is also O(n), breaking the O(1) goal
Lock striping / segments	Shard keys into N independent LRU caches, each with its own lock	Good scalability; eviction becomes approximately LRU (per segment rather than global)
`Collections.synchronizedMap(new LinkedHashMap<>(cap, 0.75f, true) { removeEldestEntry })`	JDK access-order map	Quick and correct; same coarse-lock limits as `synchronized`
Production library (Caffeine)	Concurrent hash map + buffered, batched recency updates; W-TinyLFU eviction	Best choice in practice; reads record access in lock-free buffers that are replayed under a lock

Warning

Making the map and the list individually thread-safe does not make the cache thread-safe. The invariant "every map entry has exactly one list node and vice versa" spans both structures, so it must be protected by one lock (or an equivalent atomic scheme).

Interview-friendly answer: start with the coarse lock, explain why a read-write lock does not help because reads write, then propose segmentation or Caffeine-style buffered recency for scale.

Extensions

Time-to-live (TTL)

Store expiresAt in each node.
Lazy expiry: on get, if expired, remove and return null.
Active expiry: a background task, or a min-heap / timing wheel keyed by expiresAt, purges expired entries so dead data does not occupy capacity.
Choose between expire-after-write (fixed lifetime) and expire-after-access (sliding lifetime).

LFU (Least Frequently Used)

Evict the entry with the lowest access count; break ties by recency.
O(1) design: Map<K, Node> plus Map<Integer, LinkedHashSet<K>> (frequency → keys in recency order) plus a minFreq variable.
On access, move the key from bucket f to f + 1; if bucket minFreq empties, increment minFreq. A new key always resets minFreq to 1.
LFU resists one-off scans that would flush an LRU cache, but adapts slowly when popularity shifts; hybrids such as W-TinyLFU address both.

Other common follow-ups

Size-based capacity: evict by total bytes (a weigher function) rather than entry count.
Statistics: hit/miss/eviction counters, ideally LongAdder for low contention.
Write-through / write-back: call a loader on miss and a writer on eviction via the listener.
Distributed cache: shard keys with consistent hashing across nodes, each running a local LRU (essentially how Memcached works).

Interview Tips

Lead with the data-structure argument: map for O(1) lookup, doubly linked list for O(1) reordering and eviction.
Store the key inside the node; forgetting it is the most common bug.
Use sentinel nodes and small helpers (addFirst, unlink, moveToFront) to keep get/put short and readable.
Mention LinkedHashMap with accessOrder = true and removeEldestEntry, then explain you are implementing the internals by hand because that is the exercise.
Validate inputs (capacity > 0) and test edge cases aloud: capacity 1, updating an existing key, removing the only element.
For concurrency, point out that get mutates state, so a read-write lock does not help.
Close with TTL and LFU extensions to show you understand eviction policies beyond LRU.