Problem 40.1 · Designing Data StructuresMedium

LRU Cache

PatternCombine Structures to Design Hash Map Lookup (Complement)In-Place Linked List Reversal

What it teaches: HashMap + doubly linked list with sentinels.

Practise it on judges as “LRU Cache”.

In plain words

Think of a small desk that holds only a few books. Every time you read a book you put it on top of the pile. When the desk is full and a new book arrives, the book at the very bottom, the one you haven't touched for the longest time, goes back to the shelf. A map finds any book instantly, and a chain (linked list) keeps them in "most recent first" order so moving or removing one is quick.

Return the value for get (or −1 if it isn't there). Example: capacity 2: put(1,1), put(2,2), get(1), put(3,3), get(2) → 1, −1.

The problem

Design LRUCache(capacity) with get(key) (value or −1) and put(key, value), both O(1). When over capacity, evict the least recently used key.

Example 1

Input: cap 2: put(1,1), put(2,2), get(1), put(3,3), get(2)
Output: 1, -1

Constraints

1 ≤ capacity ≤ 3000
Up to 2 × 10⁵ calls

Pattern clues in the wording

→ Evict least recently used
→ O(1) get and put

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

LRUCache · starter

import java.util.*;

class LRUCache {
    public LRUCache(int capacity) {}
    public int get(int key) { return -1; }
    public void put(int key, int value) {}
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["LRUCache","put","put","get","put","get","put","get","get","get"] args = [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]	[null,null,null,1,null,-1,null,-1,3,4]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Map + doubly linked list · O(1) per operation 2. LinkedHashMap · O(1) per operation

Map + doubly linked list

Time O(1) per operation Space O(capacity)

Sentinels head and tail. get: move to front. put: update and move, or insert at front and evict tail.prev if over capacity.

▶ Dry run: Map + most-recent-first listcapacity 2: put(1,1), put(2,2), get(1), put(3,3), get(2)

1=1

front

null

map(map)

1: node(1)

Step 1/6put(1,1): make a node, store it in the map, and put it at the front of the list.

Approach 1

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

class LRUCache {
    private static class Node {
        int key, val;
        Node prev, next;
        Node(int key, int val) { this.key = key; this.val = val; }
    }

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

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        unlink(n);
        addFront(n);
        return n.val;
    }

    public void put(int key, int value) {
        Node n = map.get(key);
        if (n != null) { n.val = value; unlink(n); addFront(n); return; }
        n = new Node(key, value);
        map.put(key, n);
        addFront(n);
        if (map.size() > capacity) {
            Node lru = tail.prev;
            unlink(lru);
            map.remove(lru.key);
        }
    }

    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;
    }
}

Verdict: The standard answer.

LinkedHashMap

Time O(1) per operation Space O(capacity)

Access-ordered LinkedHashMap that removes the eldest entry when size exceeds capacity.

Approach 2

import java.util.LinkedHashMap;
import java.util.Map;

class LRUCache {
    private final Map<Integer, Integer> map;

    public LRUCache(int capacity) {
        map = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) { return map.getOrDefault(key, -1); }

    public void put(int key, int value) { map.put(key, value); }
}

Verdict: Production-ready in a few lines; mention it, but be ready to build the manual version.

Before you submit

Edge cases and common mistakes

Test these inputs

Capacity 1
put on an existing key (no eviction, but it becomes most recent)

Mistakes people make

Forgetting to remove the evicted key from the map.

Interview

Follow-up questions

How would you make it thread-safe?

Connect the dots

Where this shows up in real systems

System Design · Topic 10.6 — Eviction Policies: LRU, LFU, TTLLRU eviction is a hash map for lookup plus a doubly linked list for recency, both O(1).System Design · Problem 4.16 — LRU CacheThe same class, built and tested step by step with a dry run.

Command Palette