LRU Cache

MEDIUM✓ CHIP-TIMEDLC #146 — FULL STATEMENT ↗

The drill: A fixed-capacity cache that evicts the item nobody has touched in the longest time whenever a new key would push it over capacity — both get and put count as a touch.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

This cache holds a fixed number of key-value pairs and needs two operations: get a value by key, and put a value under a key, creating or overwriting it.

Capacity is the whole point — once a put would push the cache past its limit, the entry that has gone the longest untouched gets evicted to make room. Both get and put reset a key's freshness the moment they touch it.

A get on a key that isn't present reports a miss rather than an error, and a put on a key that already exists updates its value and immediately counts as the freshest touch.

EX 01

LRUCache(2)

put(10, 100)

put(20, 200)

get(10) → 100

put(30, 300)

get(20) → -1

put(40, 400)

get(10) → -1

get(30) → 300

get(40) → 400

CLASSIC EVICTION CHAIN OVER CAPACITY TWO

EX 02

LRUCache(1)

put(5, 50)

get(5) → 50

put(6, 60)

get(5) → -1

get(6) → 60

CAPACITY ONE, EVERY NEW KEY EVICTS THE LAST

EX 03

LRUCache(3)

put(1, 10)

put(2, 20)

put(3, 30)

put(1, 999)

get(2) → 20

put(4, 40)

get(1) → 999

get(3) → -1

get(4) → 40

PUT ON AN EXISTING KEY UPDATES THE VALUE AND REFRESHES RECENCY

capacity is fixed at construction, at least one slot
keys and values are plain integers
get and put must both run in O(1)
recency is defined by both get and put touches, not put alone

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A hashmap alone answers get in O(1) but has no memory of order — recovering who was used least recently means recomputing it from scratch, which is the honest, slower way to do it.

HINT 2 THE STRUCTURE

Recency is exactly a sequence — the shape a doubly linked list is built to maintain in O(1), with a hashmap on the side to jump straight to any node in it.

HINT 3 ONE STEP FROM THE ANSWER

Keep a doubly linked list ordered by recency with a hashmap from key to node; every get or put moves its node to the front, and eviction just unlinks whatever sits at the back.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE RECENCY CHAINPATTERN · HASHMAP + DOUBLY LINKED LISTcapacity 2 · put/get sequence

new(2)

put10,100

put20,200

get10

put30,300

get20

put40,400

get10

get30

get40

ORDER — most to least recently used

order MRU→LRU → (empty)

STEP 1

Capacity-2 LRU cache created — empty map, empty recency list.

STEP 1 / 10 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/lru-cache.py — RACE PACE

LANG ▸

PACE ▸

class _Node:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}
        self.head = _Node()  # sentinel; head.next is the most recently used
        self.tail = _Node()  # sentinel; tail.prev is the least recently used
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _insert_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._insert_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            node = self.map[key]
            node.val = value
            self._remove(node)
            self._insert_front(node)
            return
        if len(self.map) == self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]
        node = _Node(key, value)
        self.map[key] = node
        self._insert_front(node)

TIME O(1) ALL OPSSPACE O(CAPACITY)PYTHON · RACE PACE · 49 LN

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.order = []  # least recently used at index 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.order.remove(key)
        self.order.append(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.order.remove(key)
        elif len(self.cache) == self.capacity:
            lru = self.order.pop(0)
            del self.cache[lru]
        self.cache[key] = value
        self.order.append(key)

TIME O(N) PER OPSPACE O(N)PYTHON · TRAINING PACE · 21 LN

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);
    private final Node tail = new Node(0, 0);

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

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void insertFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        remove(node);
        insertFront(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = value;
            remove(node);
            insertFront(node);
            return;
        }
        if (map.size() == capacity) {
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.key);
        }
        Node node = new Node(key, value);
        map.put(key, node);
        insertFront(node);
    }
}

TIME O(1) ALL OPSSPACE O(CAPACITY)JAVA · RACE PACE · 60 LN

class LRUCache {
    private final int capacity;
    private final Map<Integer, Integer> cache = new HashMap<>();
    private final List<Integer> order = new ArrayList<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        order.remove(Integer.valueOf(key));
        order.add(key);
        return cache.get(key);
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            order.remove(Integer.valueOf(key));
        } else if (cache.size() == capacity) {
            int lru = order.remove(0);
            cache.remove(lru);
        }
        cache.put(key, value);
        order.add(key);
    }
}

TIME O(N) PER OPSPACE O(N)JAVA · TRAINING PACE · 27 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED