#146 LRU Cache

frequently reported atApple Oracle Samsung ByteDance / TikTok Walmart Adobe

the problem

In plain words

Design a cache with a fixed capacity. get(key) returns the value or -1. put(key, value) inserts or updates; if the cache is over capacity, evict the least recently used key. Both must run in O(1) average time.

in capacity 2: put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4)

out 1, -1, -1, 3, 4

put(3,3) evicts key 2 (key 1 was just used); put(4,4) evicts key 1.

1 ≤ capacity ≤ 3000
0 ≤ key ≤ 10⁴
0 ≤ value ≤ 10⁵
At most 2·10⁵ calls to get and put

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternHashMap + doubly linked list

where this runsJava's LinkedHashMap is this exact structure: a HashMap with a doubly linked list through its entries, and in access order its Javadoc calls it well-suited to building LRU caches.

You need two things in O(1): find a key (HashMap) and move/remove an entry by recency (doubly linked list). The map stores nodes, so you can unlink any node instantly.

solutions

From brute force to optimal

Keep keys in usage order in a LinkedList; on each use, find and move the key.

get/put: remove the key from the order list (search), append it to the end.
When full, evict the first key.

timeO(capacity) per call

order.remove(key) must search the list.

spaceO(capacity)

Map + order list.

javaRename to LRUCache on LeetCodejava.util.* · java.util.function.*

1class LRUCacheSlow {2    private final int capacity;3    private final Map<Integer, Integer> map = new HashMap<>();4    private final LinkedList<Integer> order = new LinkedList<>(); // front = least recently used5 6    LRUCacheSlow(int capacity) { this.capacity = capacity; }7 8    public int get(int key) {9        if (!map.containsKey(key)) return -1;10        order.remove(Integer.valueOf(key)); // O(n): must search for the key11        order.addLast(key);12        return map.get(key);13    }14 15    public void put(int key, int value) {16        if (map.containsKey(key)) order.remove(Integer.valueOf(key));17        else if (map.size() == capacity) map.remove(order.removeFirst()); // evict LRU18        map.put(key, value);19        order.addLast(key);20    }21}

Java's LinkedHashMap already is a HashMap + doubly linked list. Turn on access order and evict in removeEldestEntry.

new LinkedHashMap<>(16, 0.75f, true).
Override removeEldestEntry: size() > capacity.
get → getOrDefault(key, -1); put → put.

timeO(1) average

Hash lookup + constant-time relinking inside LinkedHashMap.

spaceO(capacity)

One entry per key.

javaRename to LRUCache on LeetCodejava.util.* · java.util.function.*

1class LRUCacheBuiltIn {2    private final Map<Integer, Integer> map;3 4    LRUCacheBuiltIn(int capacity) {5        // accessOrder = true: every get/put moves the entry to the end (most recent)6        map = new LinkedHashMap<>(16, 0.75f, true) {7            @Override8            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {9                return size() > capacity; // called after each insert: drop the oldest10            }11        };12    }13 14    public int get(int key) { return map.getOrDefault(key, -1); }15 16    public void put(int key, int value) { map.put(key, value); }17}

Map key → node. Most recent node sits after the head sentinel; the LRU node sits before the tail sentinel.

get: look up the node, unlink it, add it to the front.
put existing: update value, move to front.
put new: if full, unlink tail.prev and remove its key from the map; then add the new node to the front.

timeO(1) average

Map operations are O(1) average; unlink/addFront change four references.

spaceO(capacity)

One node + one map entry per key.

javaclass LRUCachejava.util.* · java.util.function.*

1class LRUCache {2    private static class Node {3        int key, value;4        Node prev, next;5        Node(int key, int value) { this.key = key; this.value = value; }6    }7 8    private final int capacity;9    private final Map<Integer, Node> map = new HashMap<>();          // key → node, O(1) lookup10    private final Node head = new Node(0, 0), tail = new Node(0, 0); // sentinels; head.next = most recent11 12    public LRUCache(int capacity) {13        this.capacity = capacity;14        head.next = tail;15        tail.prev = head;16    }17 18    public int get(int key) {19        Node node = map.get(key);20        if (node == null) return -1;21        unlink(node);22        addFront(node); // touched → most recently used23        return node.value;24    }25 26    public void put(int key, int value) {27        Node node = map.get(key);28        if (node != null) {           // update + refresh29            node.value = value;30            unlink(node);31            addFront(node);32            return;33        }34        if (map.size() == capacity) { // full → evict the node just before tail35            Node lru = tail.prev;36            unlink(lru);37            map.remove(lru.key);      // why each node stores its key38        }39        node = new Node(key, value);40        map.put(key, node);41        addFront(node);42    }43 44    private void unlink(Node x) {45        x.prev.next = x.next;46        x.next.prev = x.prev;47    }48 49    private void addFront(Node x) {50        x.next = head.next;51        x.prev = head;52        head.next.prev = x;53        head.next = x;54    }55}

sim

Dry run

loading simulation…

javaclass LRUCachejava.util.* · java.util.function.*

1class LRUCache {2    private static class Node {3        int key, value;4        Node prev, next;5        Node(int key, int value) { this.key = key; this.value = value; }6    }7 8    private final int capacity;9    private final Map<Integer, Node> map = new HashMap<>();          // key → node, O(1) lookup10    private final Node head = new Node(0, 0), tail = new Node(0, 0); // sentinels; head.next = most recent11 12    public LRUCache(int capacity) {13        this.capacity = capacity;14        head.next = tail;15        tail.prev = head;16    }17 18    public int get(int key) {19        Node node = map.get(key);20        if (node == null) return -1;21        unlink(node);22        addFront(node); // touched → most recently used23        return node.value;24    }25 26    public void put(int key, int value) {27        Node node = map.get(key);28        if (node != null) {           // update + refresh29            node.value = value;30            unlink(node);31            addFront(node);32            return;33        }34        if (map.size() == capacity) { // full → evict the node just before tail35            Node lru = tail.prev;36            unlink(lru);37            map.remove(lru.key);      // why each node stores its key38        }39        node = new Node(key, value);40        map.put(key, node);41        addFront(node);42    }43 44    private void unlink(Node x) {45        x.prev.next = x.next;46        x.next.prev = x.prev;47    }48 49    private void addFront(Node x) {50        x.next = head.next;51        x.prev = head;52        head.next.prev = x;53        head.next = x;54    }55}

in the room

How to say it in the interview

talk track

Say the requirement out loud: "O(1) lookup → HashMap; O(1) reorder and evict → doubly linked list. Combine them."
Explain the sentinels: no null checks in unlink/addFront.
Explain why each node stores its key: on eviction you have the node and must delete it from the map.
Mention LinkedHashMap as the production answer — but implement the manual version if asked.

traps

Forgetting to move a key to the front on get (a read counts as a use).
Forgetting that put on an existing key also refreshes it — and must not evict anything.
Evicting from the map but not the list (or the reverse) — the two must always agree.

what they ask next

Follow-ups

LFU Cache (LC 460)?

Map key → node plus a map frequency → doubly linked list, and a minFreq variable. Still O(1) per operation.

Make it thread-safe?

Simplest: one lock around get/put. At scale: split the cache into shards, each with its own lock (lock striping).

before you submit

Edge cases to test

Capacity 1.
put on an existing key updates and refreshes it — no eviction.
get on a missing key → -1, and nothing moves.
get counts as a use: it can save a key from eviction.

practise next