PHASE 4Intermediate ~8 min· topic 16 of 18Level 3

Problem 4.16 — LRU Cache

In one line

The most-asked LLD warm-up: get and put in O(1) with least-recently-used eviction, built from a hash map plus a doubly linked list, then made thread-safe and generic.

0/18 · 0%

Think of it like this

A small bookshelf next to your desk that holds 5 books. Every time you use a book you put it at the front. When you bring a 6th book, the one at the very back (the one you haven't touched for longest) goes back to the library.

Key ideas

01
Requirements: fixed capacity; get(key) returns the value and marks it most recently used; put(key, value) inserts or updates and evicts the least recently used entry when full; both O(1).
02
Design: a HashMap<K, Node> for O(1) lookup, and a DOUBLY LINKED LIST ordered by recency (head = most recent, tail = least recent) for O(1) move-to-front and eviction. Sentinel head/tail nodes remove null checks.
03
Extensions interviewers ask for: thread safety (a single lock is simplest; lock striping or Caffeine's approach for high concurrency), generics, TTL per entry, eviction listeners, and swapping the policy (LFU) via the Strategy pattern (Phase 2).
04
In real code you'd use LinkedHashMap(capacity, 0.75f, true) with removeEldestEntry, or Caffeine (which uses the smarter W-TinyLFU policy). Knowing how to build it is the interview; knowing not to hand-roll it in production is seniority.

Java / Spring map

→
LinkedHashMap with accessOrder=true is an LRU in five lines; Caffeine is the production-grade cache for Java.

Code & diagrams

LruCache.javajava

HashMap + doubly linked list with sentinels. O(1) get and put.

public final class LruCache<K, V> {
  private final class Node { K key; V val; Node prev, next; Node(K k, V v) { key = k; val = v; } }

  private final int capacity;
  private final Map<K, Node> map = new HashMap<>();
  private final Node head = new Node(null, null), tail = new Node(null, null);

  public LruCache(int capacity) {
    if (capacity <= 0) throw new IllegalArgumentException("capacity must be > 0");
    this.capacity = capacity;
    head.next = tail; tail.prev = head;
  }

  public synchronized Optional<V> get(K key) {
    Node n = map.get(key);
    if (n == null) return Optional.empty();
    moveToFront(n);
    return Optional.of(n.val);
  }

  public synchronized void put(K key, V val) {
    Node n = map.get(key);
    if (n != null) { n.val = val; moveToFront(n); return; }
    if (map.size() == capacity) {                 // evict least recently used
      Node lru = tail.prev;
      unlink(lru);
      map.remove(lru.key);
    }
    n = new Node(key, val);
    map.put(key, n);
    addFront(n);
  }

  private void moveToFront(Node n) { unlink(n); addFront(n); }
  private void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
  private void addFront(Node n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }
}

Explain without notes

Why a doubly linked list and not a singly linked one?

Practice

Extend it with a per-entry TTL without making get/put slower than O(1) amortised.

Trade-offs

↔
LRU is simple and good for recency-heavy workloads but is fooled by one-off scans; LFU/W-TinyLFU resist scans at the cost of more bookkeeping.

Run it in production

You've designed it. Now build, operate, and break the same idea hands-on in the DevOps courses:

Stateful · Redis memory, eviction & persistence

maxmemory policies, big and hot keys, RDB/AOF, and slow commands.

Completion checklist

I can code an O(1) LRU from scratch in 15 minutes
I can discuss thread safety and TTL extensions

Back to phase

Command Palette