How do you design an LRU cache?

Use a hash map and a doubly linked list. The map goes from key to list node, so any key is found in O(1). The list keeps nodes in order of use, most recent at the front. get moves the node to the front. put adds the node at the front and, when the cache is full, removes the node at the back and deletes its key from the map. Both are O(1).

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

To unlink a node you must change the node before it. A singly linked list has no link back, so finding that node means walking from the start, which is O(n). The prev link makes it one step.

Why does each node store its key?

On eviction you take the node at the back of the list. You must also delete it from the map, and the map is looked up by key. If the node did not carry its key, you would have to search the whole map for it.

Can I use Java's LinkedHashMap instead?

Yes. new LinkedHashMap<>(16, 0.75f, true) keeps entries in access order, from least recent to most recent, and the Java docs say this makes it well suited to LRU caches. Override removeEldestEntry to return size() > capacity, and the eldest entry is removed after each insert. Name it in the interview, then write the map and list yourself unless told not to. The program on this page uses LinkedHashMap as the reference its own cache must match.

How do you make an LRU cache thread safe?

Put get and put behind one lock. A get moves the node to the front, so it changes the list, and two unguarded gets can break the links. If one lock is too slow, split the keys across several shards, each with its own lock. Each shard then evicts by its own order, so the whole cache is only close to LRU. Caffeine takes a third path: it records reads in buffers and applies them to the eviction order in batches.

How do you add a TTL (expiry time) to an LRU cache?

Store a deadline in each node when it is written. On get, if the clock has passed the deadline, remove the node and return a miss. This is lazy: expired entries stay until read or evicted, so add a cleanup pass if many entries expire unread. Caffeine offers expireAfterWrite and expireAfterAccess, and does its expiry work during writes and sometimes during reads.

Does Redis use exact LRU?

No. The Redis docs say its LRU is an approximation: it samples a few keys at random and evicts the one idle longest. maxmemory-samples sets the sample size, 5 by default. An exact LRU would cost more memory per key.

When should I use LFU instead of LRU?

LRU keeps what was used recently. LFU, least frequently used, keeps what was used most often. If a few keys are popular for a long time, LFU protects them from a one-off scan of many keys. If what is popular changes quickly, LRU adapts faster. The LFU cache page builds the O(1) version and shows a case where each one wins.

What is the time and space complexity?

get and put are O(1) on average: one hash map lookup plus a few pointer changes. Space is O(capacity): one map entry and one node per key, plus the two dummy nodes.

LLD · Machine Coding Round

LRU Cache Design: Hash Map + Doubly Linked List, O(1) Get and Put

To design an LRU cache, use a hash map and a doubly linked list together. The map finds any key's node at once, and the list keeps the nodes in order of use, most recent at the front. get moves a node to the front, and put adds one at the front and drops the node at the back when the cache is full. Both take O(1) time, which means the time does not grow with the number of items stored.

Where it shows up

A classic cache question in coding and low level design (LLD) rounds. LLD means designing the classes and methods of one program. LeetCode 146, LRU Cache, is the coding form: it asks for get and put in O(1) average time. In a design round, the interviewer adds threads, expiry times and a second eviction rule.

Two courses by the author of this page:

System Design

770 lessons · 18 free to read

₹1,111 in India · $25 elsewhere, once

Get System Design

You own this course

Generative AI and Agentic AI

214 lessons · 10 free to read

₹1,333 in India · $35 elsewhere, once

Get Generative AI and Agentic AI

You own this course

Every lesson in both courses has an AI tutor beside it. It reads the same lesson you are reading and answers your questions from it. Try the tutor

Spec sheetLRU Cache

01Core classes: LRUCache, Node, SynchronizedLRU, ShardedLRU, Clock
02Design patterns: Sentinel nodes, Decorator, Observer, Passing time in
03Key methods: 4 signatures, with the code skeleton

worked through below, with the maths

Why this is asked

A cache is a small, fast store that keeps copies of data you will likely need again. When it is full, it must throw something out. LRU, least recently used, throws out the item that was used longest ago. The question tests whether you can pick two data structures that together do what neither does alone. A hash map stores key and value pairs and finds a key in one step, but it keeps no order. A linked list is a chain of nodes, where each node holds one item and a link to the next node. It keeps order, but finding a key in it means walking the chain. In a doubly linked list each node also links back to the one before it. The question also tests careful pointer code (the links between nodes), a clean class design, and one trap: in an LRU cache, a read changes the order, so a read is also a write. That matters the moment two threads share the cache. A thread is one line of work that runs alongside others.

Requirements

Functional

get(key) returns the value, or null if the key is missing. A hit makes that key the most recently used.
put(key, value) adds the key or updates its value. Either way, the key becomes the most recently used.
When the cache is full and a new key arrives, remove the least recently used key first.
Updating a key that is already there does not change the size and removes nothing, even when the cache is full.
The capacity is fixed when the cache is made, and must be at least 1.
Follow-ups: an expiry time per entry (TTL, time to live), a callback when a key is evicted, and safe use from many threads.

Constraints & non-functional

get and put each take O(1) time on average.
Memory grows in step with the capacity: one map entry and one list node per key.
Build the doubly linked list yourself. LinkedHashMap is the library shortcut, worth naming, but most interviewers want to see the pointers.
An evicted key must leave both the map and the list. Leaving it in one of them is a memory leak or a wrong answer later.
With many threads, get must take the lock that put takes, because it changes the list.

Core classes & entities

Class diagram: LRU Cache

LRUCache

The class callers use. It holds the map and the two ends of the list, and keeps them in step on every get and put. It is written as LRUCache<K, V>, so it works for any key type and any value type.

attrs: capacity: int, map: HashMap<K, Node<K, V>>, head, tail: Node (dummy ends), ttlMillis, clock, onEvict (optional)

methods: get(key): V, put(key, value), remove(key): boolean, containsKey(key): boolean, size(): int

Node

One entry in the list. It holds the key, the value, an expiry time, and links to the node before and after it. It keeps the key so that, when it is evicted from the list, the cache can also delete it from the map.

attrs: key, value, expiresAt, prev, next

SynchronizedLRU

Wraps LRUCache with one lock, so many threads can share it. Both get and put take the lock.

attrs: c: LRUCache<K, V>, lock: ReentrantLock

methods: get(key): V, put(key, value)

ShardedLRU

Splits keys across several SynchronizedLRU caches, called shards. A key's hash, a number computed from the key, picks its shard. Threads working on different shards do not wait for each other. The cost: each shard evicts by its own order, so the whole is only roughly LRU.

attrs: shards: List<SynchronizedLRU<K, V>>

methods: get(key): V, put(key, value)

Clock

Gives the current time for TTL checks. Tests use a FakeClock that they move forward by exact amounts.

methods: nowMillis(): long

Relationships

LRUCache → composition → Node. The cache makes and owns every node. The map and the list both point at these node objects.
SynchronizedLRU → composition → LRUCache. Wraps one cache and guards it with one lock.
ShardedLRU → composition → SynchronizedLRU. Owns several locked caches and sends each key to one of them.
LRUCache → association → Clock. Reads the time only through the clock it was given.

Design patterns used

Sentinel nodes in The dummy head and tail of the list

They never hold data, so every real node always has a node before and after it. Adding and removing need no checks for an empty list, which removes the most common bug in a timed round.

Decorator in SynchronizedLRU around LRUCache

A decorator wraps an object to add one behaviour, here a lock, without changing the object. The single-threaded cache stays simple and fast for single-threaded use.

Observer in The onEvict callback

Code outside the cache can react to an eviction, for example to count evictions or write the value somewhere, without the cache knowing who listens.

Passing time in in Clock with FakeClock

TTL is about time. With the clock passed in, the test checks 999 ms and 1,000 ms exactly, with no sleeping.

Key API / methods

V get(K key)

Find the node in the map. On a miss, return null and change nothing. If the entry has expired, remove it and return null. On a hit, unlink the node and add it at the front. O(1).

void put(K key, V value)

If the key exists: set the value, move the node to the front, done. If it is new and the cache is full: unlink the node before the tail and delete its key from the map. Then add the new node at the front and put it in the map. O(1).

boolean containsKey(K key)

Checks the map only. It does not count as a use, so the order does not change. Do not build it on get().

LinkedHashMap(16, 0.75f, true) + removeEldestEntry

The library shortcut. The third argument, true, keeps entries in access order. Overriding removeEldestEntry to return size() > capacity removes the eldest entry after each insert.

Code skeleton

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.BiConsumer;

interface Clock { long nowMillis(); }
final class FakeClock implements Clock {
    private long t;
    public long nowMillis() { return t; }
    void advance(long ms) { t += ms; }
}

// ---------- The LRU cache: a hash map for finding, a doubly linked list for order ----------
// head side = most recently used, tail side = least recently used. head and tail are dummy
// nodes that never hold data, so adding and removing never has to check for null.
final class LRUCache<K, V> {
    private static final class Node<K, V> {
        final K key; V value; long expiresAt; Node<K, V> prev, next;   // the key is kept so eviction can delete it from the map
        Node(K key, V value) { this.key = key; this.value = value; }
    }
    private final int capacity; private final long ttlMillis; private final Clock clock;
    private final BiConsumer<K, V> onEvict;
    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null), tail = new Node<>(null, null);
    long evictions, expirations;

    LRUCache(int capacity) { this(capacity, 0, () -> 0L, (k, v) -> {}); }
    LRUCache(int capacity, long ttlMillis, Clock clock, BiConsumer<K, V> onEvict) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be at least 1");
        this.capacity = capacity; this.ttlMillis = ttlMillis; this.clock = clock; this.onEvict = onEvict;
        head.next = tail; tail.prev = head;
    }

    V get(K key) {
        Node<K, V> n = map.get(key);
        if (n == null) return null;                               // miss: nothing changes
        if (expired(n)) { unlink(n); map.remove(key); expirations++; return null; }
        unlink(n); addFront(n);                                   // a read is a use: move to the front
        return n.value;
    }

    void put(K key, V value) {
        Node<K, V> n = map.get(key);
        if (n != null) {                                          // update: size stays, nothing is evicted
            n.value = value; n.expiresAt = deadline();
            unlink(n); addFront(n);
            return;
        }
        if (map.size() == capacity) {                             // full: drop the least recently used first
            Node<K, V> victim = tail.prev;
            unlink(victim); map.remove(victim.key); evictions++;
            onEvict.accept(victim.key, victim.value);
        }
        n = new Node<>(key, value); n.expiresAt = deadline();
        addFront(n); map.put(key, n);
    }

    boolean remove(K key) { Node<K, V> n = map.remove(key); if (n == null) return false; unlink(n); return true; }
    boolean containsKey(K key) { return map.containsKey(key); }   // does not count as a use
    int size() { return map.size(); }

    private long deadline() { return ttlMillis == 0 ? Long.MAX_VALUE : clock.nowMillis() + ttlMillis; }
    private boolean expired(Node<K, V> n) { return clock.nowMillis() >= n.expiresAt; }
    private void addFront(Node<K, V> n) { n.prev = head; n.next = head.next; head.next.prev = n; head.next = n; }
    private void unlink(Node<K, V> n) { n.prev.next = n.next; n.next.prev = n.prev; n.prev = n.next = null; }

    // most recent first, for printing and for the checks
    List<K> keysMostRecentFirst() { List<K> out = new ArrayList<>(); for (Node<K, V> n = head.next; n != tail; n = n.next) out.add(n.key); return out; }

    // walk the list both ways and compare with the map; any broken link shows up here
    boolean consistent() {
        int forward = 0;
        for (Node<K, V> n = head.next; n != tail; n = n.next) { if (n.next.prev != n || map.get(n.key) != n) return false; if (++forward > map.size()) return false; }
        int back = 0;
        for (Node<K, V> n = tail.prev; n != head; n = n.prev) if (++back > map.size()) return false;
        return forward == map.size() && back == map.size() && map.size() <= capacity;
    }
}

// ---------- Thread safe: one lock around every call, because get() changes the list too ----------
final class SynchronizedLRU<K, V> {
    private final LRUCache<K, V> c; private final ReentrantLock lock = new ReentrantLock();
    SynchronizedLRU(int capacity) { c = new LRUCache<>(capacity); }
    V get(K k) { lock.lock(); try { return c.get(k); } finally { lock.unlock(); } }
    void put(K k, V v) { lock.lock(); try { c.put(k, v); } finally { lock.unlock(); } }
    boolean consistent() { lock.lock(); try { return c.consistent(); } finally { lock.unlock(); } }
    int size() { lock.lock(); try { return c.size(); } finally { lock.unlock(); } }
}

// ---------- Sharded: N small caches, each with its own lock. Faster under many threads, but LRU only per shard ----------
final class ShardedLRU<K, V> {
    private final List<SynchronizedLRU<K, V>> shards = new ArrayList<>();
    ShardedLRU(int shardCount, int capacityPerShard) { for (int i = 0; i < shardCount; i++) shards.add(new SynchronizedLRU<>(capacityPerShard)); }
    private SynchronizedLRU<K, V> shard(K k) { return shards.get(Math.floorMod(k.hashCode(), shards.size())); }
    V get(K k) { return shard(k).get(k); }
    void put(K k, V v) { shard(k).put(k, v); }
}

// ---------- The library shortcut, used here as the reference to check against ----------
final class LinkedHashMapLRU<K, V> extends LinkedHashMap<K, V> {
    private static final long serialVersionUID = 1L;
    private final int capacity;
    LinkedHashMapLRU(int capacity) { super(16, 0.75f, true); this.capacity = capacity; }   // true = access order
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; }
}

public class LRUCacheDemo {
    public static void main(String[] args) throws Exception {
        System.out.println("1. A sequence of operations, capacity 3 (list printed most recent first)");
        LRUCache<String, Integer> c = new LRUCache<>(3);
        step(c, "put A=1", () -> c.put("A", 1));
        step(c, "put B=2", () -> c.put("B", 2));
        step(c, "put C=3", () -> c.put("C", 3));
        step(c, "get A -> " + c.get("A"), () -> {});
        step(c, "put D=4 (full: evicts B)", () -> c.put("D", 4));
        step(c, "get B -> " + c.get("B"), () -> {});
        step(c, "put C=30 (update)", () -> c.put("C", 30));
        step(c, "put E=5 (full: evicts A)", () -> c.put("E", 5));
        check(c.keysMostRecentFirst().equals(List.of("E", "C", "D")) && c.get("C") == 30 && c.evictions == 2,
            "final order E, C, D. B and A were evicted. C kept its new value 30");

        System.out.println("2. Same answers as LinkedHashMap(accessOrder=true) + removeEldestEntry");
        Random rnd = new Random(42);
        long gets = 0, mismatches = 0;
        for (int cap : new int[] { 1, 2, 5, 16 }) {
            LRUCache<Integer, Integer> mine = new LRUCache<>(cap);
            LinkedHashMapLRU<Integer, Integer> ref = new LinkedHashMapLRU<>(cap);
            for (int i = 0; i < 50_000; i++) {
                int k = rnd.nextInt(cap * 3);
                if (rnd.nextBoolean()) { gets++; if (!Objects.equals(mine.get(k), ref.get(k))) mismatches++; }
                else { int v = rnd.nextInt(); mine.put(k, v); ref.put(k, v); }
            }
            List<Integer> refOrder = new ArrayList<>(ref.keySet());
            Collections.reverse(refOrder);                          // LinkedHashMap lists least recent first
            if (!refOrder.equals(mine.keysMostRecentFirst()) || !mine.consistent()) mismatches++;
        }
        check(mismatches == 0, "200,000 random operations at capacities 1, 2, 5 and 16: all " + String.format("%,d", gets) + " gets and the final order match");

        System.out.println("3. Edge cases");
        LRUCache<String, Integer> one = new LRUCache<>(1);
        one.put("X", 1); one.put("Y", 2);
        check(one.keysMostRecentFirst().equals(List.of("Y")), "capacity 1: a new key replaces the old one");
        LRUCache<String, Integer> full = new LRUCache<>(2);
        full.put("P", 1); full.put("Q", 2); full.put("P", 10);
        check(full.size() == 2 && full.evictions == 0 && full.keysMostRecentFirst().equals(List.of("P", "Q")), "updating a key in a full cache evicts nothing");
        full.containsKey("Q");
        check(full.keysMostRecentFirst().get(0).equals("P"), "containsKey does not count as a use, so the order does not change");
        boolean bad = false;
        try { new LRUCache<String, Integer>(0); } catch (IllegalArgumentException e) { bad = true; }
        check(bad, "capacity 0 is refused");

        System.out.println("4. TTL: entries expire after a set time (test clock, no sleeping)");
        FakeClock clock = new FakeClock();
        List<String> evicted = new ArrayList<>();
        LRUCache<String, String> ttl = new LRUCache<>(2, 1_000, clock, (k, v) -> evicted.add(k));
        ttl.put("session", "alice");
        clock.advance(999);
        check("alice".equals(ttl.get("session")), "read at 999 ms: still there (TTL is 1,000 ms)");
        clock.advance(1);
        check(ttl.get("session") == null && ttl.size() == 0 && ttl.expirations == 1, "read at 1,000 ms: expired, removed, counted as a miss");
        ttl.put("a", "1"); ttl.put("b", "2"); ttl.put("c", "3");
        check(evicted.equals(List.of("a")), "the eviction listener hears about evicted key a");

        System.out.println("5. Thread safety");
        SynchronizedLRU<Integer, Integer> shared = new SynchronizedLRU<>(64);
        ExecutorService pool = Executors.newFixedThreadPool(8);
        CountDownLatch go = new CountDownLatch(1);
        List<Future<?>> fs = new ArrayList<>();
        for (int t = 0; t < 8; t++) {
            final int seed = t;
            fs.add(pool.submit(() -> { go.await(); Random r = new Random(seed);
                for (int i = 0; i < 100_000; i++) { int k = r.nextInt(200); if (r.nextBoolean()) shared.get(k); else shared.put(k, i); }
                return null; }));
        }
        go.countDown();
        for (Future<?> f : fs) f.get();
        pool.shutdown();
        check(shared.consistent() && shared.size() == 64, "8 threads, 800,000 mixed gets and puts behind one lock: every link intact, size 64");

        System.out.println("6. Sharding trades exact LRU for less waiting");
        ShardedLRU<Integer, String> sharded = new ShardedLRU<>(2, 2);   // 2 shards x 2 = room for 4
        LRUCache<Integer, String> exact = new LRUCache<>(4);
        for (int k : new int[] { 0, 1, 2 }) { sharded.put(k, "v" + k); exact.put(k, "v" + k); }
        sharded.put(4, "v4"); exact.put(4, "v4");               // keys 0, 2, 4 all land in shard 0
        check(exact.get(0) != null && sharded.get(0) == null,
            "keys 0, 2 and 4 hash to one shard: the sharded cache evicts 0 while 3 of its 4 slots are used. One exact LRU of 4 keeps it");
        System.out.println("all checks passed");
    }

    static void step(LRUCache<String, Integer> c, String what, Runnable r) {
        r.run();
        System.out.printf("  %-26s list: %s%n", what, String.join(" > ", c.keysMostRecentFirst()));
    }

    static void check(boolean ok, String what) { System.out.println((ok ? "  ok  " : "  FAIL ") + what); if (!ok) System.exit(1); }
}

/* Output of this exact program (javac + java 21, 2026-10-07):
 * 1. A sequence of operations, capacity 3 (list printed most recent first)
 *   put A=1                    list: A
 *   put B=2                    list: B > A
 *   put C=3                    list: C > B > A
 *   get A -> 1                 list: A > C > B
 *   put D=4 (full: evicts B)   list: D > A > C
 *   get B -> null              list: D > A > C
 *   put C=30 (update)          list: C > D > A
 *   put E=5 (full: evicts A)   list: E > C > D
 *   ok  final order E, C, D. B and A were evicted. C kept its new value 30
 * 2. Same answers as LinkedHashMap(accessOrder=true) + removeEldestEntry
 *   ok  200,000 random operations at capacities 1, 2, 5 and 16: all 100,096 gets and the final order match
 * 3. Edge cases
 *   ok  capacity 1: a new key replaces the old one
 *   ok  updating a key in a full cache evicts nothing
 *   ok  containsKey does not count as a use, so the order does not change
 *   ok  capacity 0 is refused
 * 4. TTL: entries expire after a set time (test clock, no sleeping)
 *   ok  read at 999 ms: still there (TTL is 1,000 ms)
 *   ok  read at 1,000 ms: expired, removed, counted as a miss
 *   ok  the eviction listener hears about evicted key a
 * 5. Thread safety
 *   ok  8 threads, 800,000 mixed gets and puts behind one lock: every link intact, size 64
 * 6. Sharding trades exact LRU for less waiting
 *   ok  keys 0, 2 and 4 hash to one shard: the sharded cache evicts 0 while 3 of its 4 slots are used. One exact LRU of 4 keeps it
 * all checks passed
 */

How it works

Eight rows, one per operation, each showing the list from most to least recently used. put A, put B, put C give C, B, A. get A gives A, C, B. put D gives D, A, C and evicts B. get B is a miss and changes nothing. put C equals 30 gives C, D, A. put E gives E, C, D and evicts A. Below, a hash map with entries C, D and E points into a list of head, E value 5, C value 30, D value 4, tail. — The list after each operation, capacity 3Read it top to bottom. Each use moves a key to the left end, and a full cache drops the key at the right end. B went in after A but is evicted first, because the read of A moved A ahead. Updating C counts as a use too, which is why A goes next. The bottom part is the end state: the map finds each node at once, and the links in both directions let any node be unlinked in one step.

Start from what the cache must do fast. It must find a key, and it must find the least recently used key. A hash map does the first in O(1), but it has no idea of order. A doubly linked list keeps order, and it can unlink any node in O(1), if you already hold that node. It cannot find a key without walking. So use both. The map goes from key to node. The list holds those nodes in order of use, most recent next to the head.

Why doubly linked? To unlink a node, you must change the node before it. With only next links, finding the node before means walking from the start. With prev links, it is one step.

The list has two dummy nodes, head and tail, that hold no data. Every real node then has a neighbour on both sides, so add and unlink are four pointer changes each, with no special cases.

get(key): look up the node in the map. On a miss, return null and touch nothing. On a hit, unlink the node and add it after the head. Return the value.

put(key, value) has three cases. If the key exists, set the value and move the node to the front. The size does not change and nothing is evicted. If the key is new and the cache is full, take the node before the tail, unlink it, and delete its key from the map. This is why each node stores its key. Then make a new node, add it at the front, and put it in the map.

The figure above follows one run of the program with capacity 3. After put A, B, C the order is C, B, A. get A moves A to the front. put D evicts B, now at the back, even though B went in after A. The read of A saved it. Updating C moves C to the front, and put E then evicts A. The final order is E, C, D.

The program then checks the cache against Java's LinkedHashMap set to access order, over 200,000 random operations at 4 sizes. Every get and the final order match.

Threads come next. A get moves a node, so a get is a write. The Java docs say so about LinkedHashMap too: in access order, a plain get is a structural change. The simplest safe answer is one lock around get and put. The program runs 8 threads and 800,000 calls through it, then walks the list both ways to check every link. One lock means every thread waits for every other. Sharding splits the keys over several small caches, each with its own lock. Its cost is that each shard only knows its own order. The program shows a key evicted from a crowded shard while other shards have free space. A single exact LRU keeps it.

Production caches go further. Caffeine records reads in striped ring buffers. Its docs call them lossy, because read events only tune the hit rate. One thread replays them onto the eviction order under a lock. Writes cannot be lost, so they go through a bounded queue.

TTL, time to live, is an expiry time on each entry. Here, each node gets a deadline when it is written. get checks it against the clock. An expired entry is removed and counted as a miss.

Edge cases & gotchas

Capacity 1: each new key replaces the old one. The program checks it.
put on a key that exists, when the cache is full: it is an update, so nothing is evicted. A common bug evicts first and loses a key for nothing.
Evict before you insert. If you insert first, the cache briefly holds one too many, and with capacity 1 you can evict the key you just added.
The node must store its key. Without it, after removing the tail node you cannot find its map entry without searching the whole map.
Null values: if null is a stored value, get returning null is ambiguous. Refuse null values, or use containsKey.
Threads: get moves nodes, so two unguarded gets can break the links. Use one lock for get and put, or shard.
TTL in this design is lazy: an expired entry is removed when someone reads it, or when it reaches the back and is evicted. Until then it still takes a slot. A cache with many short-lived entries needs a cleanup pass too.
Iterating while other threads change the cache is unsafe here. Copy the keys under the lock first.

FAQ

Go deeper

Cache Eviction Policies Time To Live (TTL)Caffeine Cache Redis Cache Distributed Cache Consistent Hashing

the question most readers have next

The interviewer's next question: what breaks when the LRU Cache low level design runs at full scale?

A whiteboard answer gets you through the first round. The follow-ups are about the parts that fail under real load. The lessons below teach them one at a time, starting with "Cache Eviction Policies".

The lessons that teach the next part

LFU beat LRU by 6 to 15 points, FIFO measured identical to random, and the scan that supposedly destroys LRU cost it 11 points for four hundred requests.
Cache Eviction Policiesfree lesson24 min
How to choose a cache TTL from your own traffic. A sweep of seven TTL values on skewed traffic shows the hit rate ceiling and the cost of staleness.
Time To Live (TTL)free lesson24 min
A batch job taking 30 percent of requests cost LRU 6.3 points of hit rate on the real requests, admission by approximate frequency 4.2, and exact counting 0.8, in 2,048 bytes.
Caffeine CacheSystem Design course26 min
The same small GET measured 0.3 ms at worst on an idle server and 59.1 ms while one other client ran KEYS. Reading one field cost 0.934 ms as a blob and 0.040 ms as a hash.
Redis CacheSystem Design course26 min

Stuck on a step? Every lesson has an AI tutor beside it. Ask it your question and it answers from the lesson you are reading. Try the tutor

Get the free System Design Interview cheat sheet (PDF)

Where this is taught

System Design Masterclass

770 lessons · about 287 hours · 18 free to read

₹1,111 in India by UPI$25 elsewhere by PayPal, once, for life

See the System Design course

You own this course

Also by the same author

Generative AI and Agentic AI Engineering

214 lessons · about 224 hours · 10 free to read

₹1,333 in India by UPI$35 elsewhere by PayPal, once, for life

See the Generative AI and Agentic AI course

You own this course

Master LLD and system design interviews

770 interactive lessons and 106 real systems taken apart. One payment, lifetime access, no subscription.

course 1

System Design Masterclass

From absolute beginner to principal engineer, drawn step by step.

770 interactive lessons
Step-by-step system design diagrams
Live code editors
Quizzes with instant feedback
Progress tracking and streaks
Lifetime access and all future lessons

Read 18 lessons free first

In India

₹1,111

Pay with UPI

Everywhere else

$25

Pay by card or PayPal

once · yours for life

LLD · Machine Coding Round

LRU Cache Design: Hash Map + Doubly Linked List, O(1) Get and Put

Where it shows up

Two courses by the author of this page:

System Design

770 lessons · 18 free to read

₹1,111 in India · $25 elsewhere, once

Get System Design

You own this course

Generative AI and Agentic AI

214 lessons · 10 free to read

₹1,333 in India · $35 elsewhere, once

Get Generative AI and Agentic AI

You own this course

Every lesson in both courses has an AI tutor beside it. It reads the same lesson you are reading and answers your questions from it. Try the tutor

Spec sheetLRU Cache

01Core classes: LRUCache, Node, SynchronizedLRU, ShardedLRU, Clock
02Design patterns: Sentinel nodes, Decorator, Observer, Passing time in
03Key methods: 4 signatures, with the code skeleton

worked through below, with the maths

Why this is asked

Requirements

Functional

get(key) returns the value, or null if the key is missing. A hit makes that key the most recently used.
put(key, value) adds the key or updates its value. Either way, the key becomes the most recently used.
When the cache is full and a new key arrives, remove the least recently used key first.
Updating a key that is already there does not change the size and removes nothing, even when the cache is full.
The capacity is fixed when the cache is made, and must be at least 1.
Follow-ups: an expiry time per entry (TTL, time to live), a callback when a key is evicted, and safe use from many threads.

Constraints & non-functional

get and put each take O(1) time on average.
Memory grows in step with the capacity: one map entry and one list node per key.
Build the doubly linked list yourself. LinkedHashMap is the library shortcut, worth naming, but most interviewers want to see the pointers.
An evicted key must leave both the map and the list. Leaving it in one of them is a memory leak or a wrong answer later.
With many threads, get must take the lock that put takes, because it changes the list.

Core classes & entities

Class diagram: LRU Cache

LRUCache

The class callers use. It holds the map and the two ends of the list, and keeps them in step on every get and put. It is written as LRUCache<K, V>, so it works for any key type and any value type.

attrs: capacity: int, map: HashMap<K, Node<K, V>>, head, tail: Node (dummy ends), ttlMillis, clock, onEvict (optional)

methods: get(key): V, put(key, value), remove(key): boolean, containsKey(key): boolean, size(): int

Node

attrs: key, value, expiresAt, prev, next

SynchronizedLRU

Wraps LRUCache with one lock, so many threads can share it. Both get and put take the lock.

attrs: c: LRUCache<K, V>, lock: ReentrantLock

methods: get(key): V, put(key, value)

ShardedLRU

attrs: shards: List<SynchronizedLRU<K, V>>

methods: get(key): V, put(key, value)

Clock

Gives the current time for TTL checks. Tests use a FakeClock that they move forward by exact amounts.

methods: nowMillis(): long

Relationships

LRUCache → composition → Node. The cache makes and owns every node. The map and the list both point at these node objects.
SynchronizedLRU → composition → LRUCache. Wraps one cache and guards it with one lock.
ShardedLRU → composition → SynchronizedLRU. Owns several locked caches and sends each key to one of them.
LRUCache → association → Clock. Reads the time only through the clock it was given.

Design patterns used

Sentinel nodes in The dummy head and tail of the list

They never hold data, so every real node always has a node before and after it. Adding and removing need no checks for an empty list, which removes the most common bug in a timed round.

Decorator in SynchronizedLRU around LRUCache

A decorator wraps an object to add one behaviour, here a lock, without changing the object. The single-threaded cache stays simple and fast for single-threaded use.

Observer in The onEvict callback

Code outside the cache can react to an eviction, for example to count evictions or write the value somewhere, without the cache knowing who listens.

Passing time in in Clock with FakeClock

TTL is about time. With the clock passed in, the test checks 999 ms and 1,000 ms exactly, with no sleeping.

Key API / methods

V get(K key)

Find the node in the map. On a miss, return null and change nothing. If the entry has expired, remove it and return null. On a hit, unlink the node and add it at the front. O(1).

void put(K key, V value)

boolean containsKey(K key)

Checks the map only. It does not count as a use, so the order does not change. Do not build it on get().

LinkedHashMap(16, 0.75f, true) + removeEldestEntry

The library shortcut. The third argument, true, keeps entries in access order. Overriding removeEldestEntry to return size() > capacity removes the eldest entry after each insert.

Code skeleton

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.BiConsumer;

interface Clock { long nowMillis(); }
final class FakeClock implements Clock {
    private long t;
    public long nowMillis() { return t; }
    void advance(long ms) { t += ms; }
}

// ---------- The LRU cache: a hash map for finding, a doubly linked list for order ----------
// head side = most recently used, tail side = least recently used. head and tail are dummy
// nodes that never hold data, so adding and removing never has to check for null.
final class LRUCache<K, V> {
    private static final class Node<K, V> {
        final K key; V value; long expiresAt; Node<K, V> prev, next;   // the key is kept so eviction can delete it from the map
        Node(K key, V value) { this.key = key; this.value = value; }
    }
    private final int capacity; private final long ttlMillis; private final Clock clock;
    private final BiConsumer<K, V> onEvict;
    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null), tail = new Node<>(null, null);
    long evictions, expirations;

    LRUCache(int capacity) { this(capacity, 0, () -> 0L, (k, v) -> {}); }
    LRUCache(int capacity, long ttlMillis, Clock clock, BiConsumer<K, V> onEvict) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be at least 1");
        this.capacity = capacity; this.ttlMillis = ttlMillis; this.clock = clock; this.onEvict = onEvict;
        head.next = tail; tail.prev = head;
    }

    V get(K key) {
        Node<K, V> n = map.get(key);
        if (n == null) return null;                               // miss: nothing changes
        if (expired(n)) { unlink(n); map.remove(key); expirations++; return null; }
        unlink(n); addFront(n);                                   // a read is a use: move to the front
        return n.value;
    }

    void put(K key, V value) {
        Node<K, V> n = map.get(key);
        if (n != null) {                                          // update: size stays, nothing is evicted
            n.value = value; n.expiresAt = deadline();
            unlink(n); addFront(n);
            return;
        }
        if (map.size() == capacity) {                             // full: drop the least recently used first
            Node<K, V> victim = tail.prev;
            unlink(victim); map.remove(victim.key); evictions++;
            onEvict.accept(victim.key, victim.value);
        }
        n = new Node<>(key, value); n.expiresAt = deadline();
        addFront(n); map.put(key, n);
    }

    boolean remove(K key) { Node<K, V> n = map.remove(key); if (n == null) return false; unlink(n); return true; }
    boolean containsKey(K key) { return map.containsKey(key); }   // does not count as a use
    int size() { return map.size(); }

    private long deadline() { return ttlMillis == 0 ? Long.MAX_VALUE : clock.nowMillis() + ttlMillis; }
    private boolean expired(Node<K, V> n) { return clock.nowMillis() >= n.expiresAt; }
    private void addFront(Node<K, V> n) { n.prev = head; n.next = head.next; head.next.prev = n; head.next = n; }
    private void unlink(Node<K, V> n) { n.prev.next = n.next; n.next.prev = n.prev; n.prev = n.next = null; }

    // most recent first, for printing and for the checks
    List<K> keysMostRecentFirst() { List<K> out = new ArrayList<>(); for (Node<K, V> n = head.next; n != tail; n = n.next) out.add(n.key); return out; }

    // walk the list both ways and compare with the map; any broken link shows up here
    boolean consistent() {
        int forward = 0;
        for (Node<K, V> n = head.next; n != tail; n = n.next) { if (n.next.prev != n || map.get(n.key) != n) return false; if (++forward > map.size()) return false; }
        int back = 0;
        for (Node<K, V> n = tail.prev; n != head; n = n.prev) if (++back > map.size()) return false;
        return forward == map.size() && back == map.size() && map.size() <= capacity;
    }
}

// ---------- Thread safe: one lock around every call, because get() changes the list too ----------
final class SynchronizedLRU<K, V> {
    private final LRUCache<K, V> c; private final ReentrantLock lock = new ReentrantLock();
    SynchronizedLRU(int capacity) { c = new LRUCache<>(capacity); }
    V get(K k) { lock.lock(); try { return c.get(k); } finally { lock.unlock(); } }
    void put(K k, V v) { lock.lock(); try { c.put(k, v); } finally { lock.unlock(); } }
    boolean consistent() { lock.lock(); try { return c.consistent(); } finally { lock.unlock(); } }
    int size() { lock.lock(); try { return c.size(); } finally { lock.unlock(); } }
}

// ---------- Sharded: N small caches, each with its own lock. Faster under many threads, but LRU only per shard ----------
final class ShardedLRU<K, V> {
    private final List<SynchronizedLRU<K, V>> shards = new ArrayList<>();
    ShardedLRU(int shardCount, int capacityPerShard) { for (int i = 0; i < shardCount; i++) shards.add(new SynchronizedLRU<>(capacityPerShard)); }
    private SynchronizedLRU<K, V> shard(K k) { return shards.get(Math.floorMod(k.hashCode(), shards.size())); }
    V get(K k) { return shard(k).get(k); }
    void put(K k, V v) { shard(k).put(k, v); }
}

// ---------- The library shortcut, used here as the reference to check against ----------
final class LinkedHashMapLRU<K, V> extends LinkedHashMap<K, V> {
    private static final long serialVersionUID = 1L;
    private final int capacity;
    LinkedHashMapLRU(int capacity) { super(16, 0.75f, true); this.capacity = capacity; }   // true = access order
    @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; }
}

public class LRUCacheDemo {
    public static void main(String[] args) throws Exception {
        System.out.println("1. A sequence of operations, capacity 3 (list printed most recent first)");
        LRUCache<String, Integer> c = new LRUCache<>(3);
        step(c, "put A=1", () -> c.put("A", 1));
        step(c, "put B=2", () -> c.put("B", 2));
        step(c, "put C=3", () -> c.put("C", 3));
        step(c, "get A -> " + c.get("A"), () -> {});
        step(c, "put D=4 (full: evicts B)", () -> c.put("D", 4));
        step(c, "get B -> " + c.get("B"), () -> {});
        step(c, "put C=30 (update)", () -> c.put("C", 30));
        step(c, "put E=5 (full: evicts A)", () -> c.put("E", 5));
        check(c.keysMostRecentFirst().equals(List.of("E", "C", "D")) && c.get("C") == 30 && c.evictions == 2,
            "final order E, C, D. B and A were evicted. C kept its new value 30");

        System.out.println("2. Same answers as LinkedHashMap(accessOrder=true) + removeEldestEntry");
        Random rnd = new Random(42);
        long gets = 0, mismatches = 0;
        for (int cap : new int[] { 1, 2, 5, 16 }) {
            LRUCache<Integer, Integer> mine = new LRUCache<>(cap);
            LinkedHashMapLRU<Integer, Integer> ref = new LinkedHashMapLRU<>(cap);
            for (int i = 0; i < 50_000; i++) {
                int k = rnd.nextInt(cap * 3);
                if (rnd.nextBoolean()) { gets++; if (!Objects.equals(mine.get(k), ref.get(k))) mismatches++; }
                else { int v = rnd.nextInt(); mine.put(k, v); ref.put(k, v); }
            }
            List<Integer> refOrder = new ArrayList<>(ref.keySet());
            Collections.reverse(refOrder);                          // LinkedHashMap lists least recent first
            if (!refOrder.equals(mine.keysMostRecentFirst()) || !mine.consistent()) mismatches++;
        }
        check(mismatches == 0, "200,000 random operations at capacities 1, 2, 5 and 16: all " + String.format("%,d", gets) + " gets and the final order match");

        System.out.println("3. Edge cases");
        LRUCache<String, Integer> one = new LRUCache<>(1);
        one.put("X", 1); one.put("Y", 2);
        check(one.keysMostRecentFirst().equals(List.of("Y")), "capacity 1: a new key replaces the old one");
        LRUCache<String, Integer> full = new LRUCache<>(2);
        full.put("P", 1); full.put("Q", 2); full.put("P", 10);
        check(full.size() == 2 && full.evictions == 0 && full.keysMostRecentFirst().equals(List.of("P", "Q")), "updating a key in a full cache evicts nothing");
        full.containsKey("Q");
        check(full.keysMostRecentFirst().get(0).equals("P"), "containsKey does not count as a use, so the order does not change");
        boolean bad = false;
        try { new LRUCache<String, Integer>(0); } catch (IllegalArgumentException e) { bad = true; }
        check(bad, "capacity 0 is refused");

        System.out.println("4. TTL: entries expire after a set time (test clock, no sleeping)");
        FakeClock clock = new FakeClock();
        List<String> evicted = new ArrayList<>();
        LRUCache<String, String> ttl = new LRUCache<>(2, 1_000, clock, (k, v) -> evicted.add(k));
        ttl.put("session", "alice");
        clock.advance(999);
        check("alice".equals(ttl.get("session")), "read at 999 ms: still there (TTL is 1,000 ms)");
        clock.advance(1);
        check(ttl.get("session") == null && ttl.size() == 0 && ttl.expirations == 1, "read at 1,000 ms: expired, removed, counted as a miss");
        ttl.put("a", "1"); ttl.put("b", "2"); ttl.put("c", "3");
        check(evicted.equals(List.of("a")), "the eviction listener hears about evicted key a");

        System.out.println("5. Thread safety");
        SynchronizedLRU<Integer, Integer> shared = new SynchronizedLRU<>(64);
        ExecutorService pool = Executors.newFixedThreadPool(8);
        CountDownLatch go = new CountDownLatch(1);
        List<Future<?>> fs = new ArrayList<>();
        for (int t = 0; t < 8; t++) {
            final int seed = t;
            fs.add(pool.submit(() -> { go.await(); Random r = new Random(seed);
                for (int i = 0; i < 100_000; i++) { int k = r.nextInt(200); if (r.nextBoolean()) shared.get(k); else shared.put(k, i); }
                return null; }));
        }
        go.countDown();
        for (Future<?> f : fs) f.get();
        pool.shutdown();
        check(shared.consistent() && shared.size() == 64, "8 threads, 800,000 mixed gets and puts behind one lock: every link intact, size 64");

        System.out.println("6. Sharding trades exact LRU for less waiting");
        ShardedLRU<Integer, String> sharded = new ShardedLRU<>(2, 2);   // 2 shards x 2 = room for 4
        LRUCache<Integer, String> exact = new LRUCache<>(4);
        for (int k : new int[] { 0, 1, 2 }) { sharded.put(k, "v" + k); exact.put(k, "v" + k); }
        sharded.put(4, "v4"); exact.put(4, "v4");               // keys 0, 2, 4 all land in shard 0
        check(exact.get(0) != null && sharded.get(0) == null,
            "keys 0, 2 and 4 hash to one shard: the sharded cache evicts 0 while 3 of its 4 slots are used. One exact LRU of 4 keeps it");
        System.out.println("all checks passed");
    }

    static void step(LRUCache<String, Integer> c, String what, Runnable r) {
        r.run();
        System.out.printf("  %-26s list: %s%n", what, String.join(" > ", c.keysMostRecentFirst()));
    }

    static void check(boolean ok, String what) { System.out.println((ok ? "  ok  " : "  FAIL ") + what); if (!ok) System.exit(1); }
}

/* Output of this exact program (javac + java 21, 2026-10-07):
 * 1. A sequence of operations, capacity 3 (list printed most recent first)
 *   put A=1                    list: A
 *   put B=2                    list: B > A
 *   put C=3                    list: C > B > A
 *   get A -> 1                 list: A > C > B
 *   put D=4 (full: evicts B)   list: D > A > C
 *   get B -> null              list: D > A > C
 *   put C=30 (update)          list: C > D > A
 *   put E=5 (full: evicts A)   list: E > C > D
 *   ok  final order E, C, D. B and A were evicted. C kept its new value 30
 * 2. Same answers as LinkedHashMap(accessOrder=true) + removeEldestEntry
 *   ok  200,000 random operations at capacities 1, 2, 5 and 16: all 100,096 gets and the final order match
 * 3. Edge cases
 *   ok  capacity 1: a new key replaces the old one
 *   ok  updating a key in a full cache evicts nothing
 *   ok  containsKey does not count as a use, so the order does not change
 *   ok  capacity 0 is refused
 * 4. TTL: entries expire after a set time (test clock, no sleeping)
 *   ok  read at 999 ms: still there (TTL is 1,000 ms)
 *   ok  read at 1,000 ms: expired, removed, counted as a miss
 *   ok  the eviction listener hears about evicted key a
 * 5. Thread safety
 *   ok  8 threads, 800,000 mixed gets and puts behind one lock: every link intact, size 64
 * 6. Sharding trades exact LRU for less waiting
 *   ok  keys 0, 2 and 4 hash to one shard: the sharded cache evicts 0 while 3 of its 4 slots are used. One exact LRU of 4 keeps it
 * all checks passed
 */

How it works

Why doubly linked? To unlink a node, you must change the node before it. With only next links, finding the node before means walking from the start. With prev links, it is one step.

The list has two dummy nodes, head and tail, that hold no data. Every real node then has a neighbour on both sides, so add and unlink are four pointer changes each, with no special cases.

get(key): look up the node in the map. On a miss, return null and touch nothing. On a hit, unlink the node and add it after the head. Return the value.

The program then checks the cache against Java's LinkedHashMap set to access order, over 200,000 random operations at 4 sizes. Every get and the final order match.

TTL, time to live, is an expiry time on each entry. Here, each node gets a deadline when it is written. get checks it against the clock. An expired entry is removed and counted as a miss.

Edge cases & gotchas

Capacity 1: each new key replaces the old one. The program checks it.
put on a key that exists, when the cache is full: it is an update, so nothing is evicted. A common bug evicts first and loses a key for nothing.
Evict before you insert. If you insert first, the cache briefly holds one too many, and with capacity 1 you can evict the key you just added.
The node must store its key. Without it, after removing the tail node you cannot find its map entry without searching the whole map.
Null values: if null is a stored value, get returning null is ambiguous. Refuse null values, or use containsKey.
Threads: get moves nodes, so two unguarded gets can break the links. Use one lock for get and put, or shard.
TTL in this design is lazy: an expired entry is removed when someone reads it, or when it reaches the back and is evicted. Until then it still takes a slot. A cache with many short-lived entries needs a cleanup pass too.
Iterating while other threads change the cache is unsafe here. Copy the keys under the lock first.

FAQ

Go deeper

Cache Eviction Policies Time To Live (TTL)Caffeine Cache Redis Cache Distributed Cache Consistent Hashing

the question most readers have next

The interviewer's next question: what breaks when the LRU Cache low level design runs at full scale?

The lessons that teach the next part

LFU beat LRU by 6 to 15 points, FIFO measured identical to random, and the scan that supposedly destroys LRU cost it 11 points for four hundred requests.
Cache Eviction Policiesfree lesson24 min
How to choose a cache TTL from your own traffic. A sweep of seven TTL values on skewed traffic shows the hit rate ceiling and the cost of staleness.
Time To Live (TTL)free lesson24 min
A batch job taking 30 percent of requests cost LRU 6.3 points of hit rate on the real requests, admission by approximate frequency 4.2, and exact counting 0.8, in 2,048 bytes.
Caffeine CacheSystem Design course26 min
The same small GET measured 0.3 ms at worst on an idle server and 59.1 ms while one other client ran KEYS. Reading one field cost 0.934 ms as a blob and 0.040 ms as a hash.
Redis CacheSystem Design course26 min

Stuck on a step? Every lesson has an AI tutor beside it. Ask it your question and it answers from the lesson you are reading. Try the tutor

Get the free System Design Interview cheat sheet (PDF)

Where this is taught

System Design Masterclass

770 lessons · about 287 hours · 18 free to read

₹1,111 in India by UPI$25 elsewhere by PayPal, once, for life

See the System Design course

You own this course

Also by the same author

Generative AI and Agentic AI Engineering

214 lessons · about 224 hours · 10 free to read

₹1,333 in India by UPI$35 elsewhere by PayPal, once, for life

See the Generative AI and Agentic AI course

You own this course

Master LLD and system design interviews

770 interactive lessons and 106 real systems taken apart. One payment, lifetime access, no subscription.

course 1

System Design Masterclass

From absolute beginner to principal engineer, drawn step by step.

770 interactive lessons
Step-by-step system design diagrams
Live code editors
Quizzes with instant feedback
Progress tracking and streaks
Lifetime access and all future lessons

Read 18 lessons free first

In India

₹1,111

Pay with UPI

Everywhere else

$25

Pay by card or PayPal

once · yours for life

LRU Cache Design: Hash Map + Doubly Linked List, O(1) Get and Put

Why this is asked

Requirements

Functional

Constraints & non-functional

Core classes & entities

LRUCache

Node

SynchronizedLRU

ShardedLRU

Clock

Relationships

Design patterns used

Sentinel nodes in The dummy head and tail of the list

Decorator in SynchronizedLRU around LRUCache

Observer in The onEvict callback

Passing time in in Clock with FakeClock

Key API / methods

Code skeleton

How it works

Edge cases & gotchas

FAQ

How do you design an LRU cache?

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

Why does each node store its key?

Can I use Java's LinkedHashMap instead?

How do you make an LRU cache thread safe?

How do you add a TTL (expiry time) to an LRU cache?

Does Redis use exact LRU?

When should I use LFU instead of LRU?

What is the time and space complexity?

Go deeper

The interviewer's next question: what breaks when the LRU Cache low level design runs at full scale?

The lessons that teach the next part

Master LLD and system design interviews

System Design Masterclass

Get all 200 questions in the System Design and Distributed Systems pack

LRU Cache Design: Hash Map + Doubly Linked List, O(1) Get and Put

Why this is asked

Requirements

Functional

Constraints & non-functional

Core classes & entities

LRUCache

Node

SynchronizedLRU

ShardedLRU

Clock

Relationships

Design patterns used

Sentinel nodes in The dummy head and tail of the list

Decorator in SynchronizedLRU around LRUCache

Observer in The onEvict callback

Passing time in in Clock with FakeClock

Key API / methods

Code skeleton

How it works

Edge cases & gotchas

FAQ

How do you design an LRU cache?

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

Why does each node store its key?

Can I use Java's LinkedHashMap instead?

How do you make an LRU cache thread safe?

How do you add a TTL (expiry time) to an LRU cache?

Does Redis use exact LRU?

When should I use LFU instead of LRU?

What is the time and space complexity?

Go deeper

The interviewer's next question: what breaks when the LRU Cache low level design runs at full scale?

The lessons that teach the next part

Master LLD and system design interviews

System Design Masterclass

Get all 200 questions in the System Design and Distributed Systems pack