Caching and eviction (LRU, LFU)

coreCommon atAnthropicGoogleAmazonMetaOpenAIRead firstHash mapsLinked listsPractise in the Sandbox →

A cache holds at most capacity entries. When it’s full, an eviction policy picks a victim: LRU drops the least recently used, LFU the least frequently used, FIFO the oldest arrival. The trick for O(1) is always the same: a hash map to find an entry, plus an ordered structure (a doubly linked list, or one list per frequency) that keeps the victim at a known end.

The idea in plain words

Your desk holds five books. The library holds thousands. When you need a sixth book on the desk, one has to go back. Which one?

• LRU (least recently used): the one you haven’t touched for the longest. Bets that the recent past predicts the near future.
• LFU (least frequently used): the one you’ve opened the fewest times. Bets that popular stays popular.
• FIFO (first in, first out): the one that’s been on the desk longest, regardless of use. Cheap and dumb.

No policy wins everywhere. Each one has a request pattern that makes it look brilliant and one that makes it useless. The interview skill is knowing those patterns, and knowing the data structure that makes the policy cost O(1) per operation instead of O(n).

A few terms:

• Hit: the key is already cached. Miss: it isn’t, so you fetch or compute it.
• Hit rate: hits ÷ requests. The number every cache is judged by.
• Working set: the keys a workload is actively using right now. If it fits in the cache, almost everything hits.

See it

Same requests, four caches. Step through and watch where they disagree. Try each scenario: there’s one where LRU wins, one where LFU wins, and one where both score zero. OPT is Belady’s optimal policy: it evicts the key needed furthest in the future. Real caches can’t see the future, so OPT is the ceiling, not a contender.

LRU vs LFU vs FIFO on the same requests

step through

scenariomixedone-off scanpopularity shiftloop > capacityrequests (≤ 16 keys)capacity

A typical mix: a few popular keys plus some one-offs.

A

B

C

A

B

D

A

E

B

A

C

B

LRU

empty

most recent → least

LFU

empty

low freq evicted first; ties → least recent

FIFO

empty

newest → oldest (hits don’t reorder)

OPT

empty

evicts key needed furthest away

LRU hits

–

LFU hits

–

FIFO hits

–

OPT hits

–

Four caches, capacity 3, see the same 12 requests. A hit means the key was already cached; a miss on a full cache forces an eviction.

↺◀▶ Play▶1 / 14

When to reach for it

The problem says…	What it’s asking for
“at most capacity entries, evict the least recently used”	LRU: hash map + doubly linked list, O(1) get and put.
“evict the least frequently used; ties by least recent”	LFU: hash map + per-frequency recency lists + min_freq.
“memoize this function, but memory is bounded”	A cache in front of a pure function. Pick a policy and a key format.
“the same expensive work repeats across requests”	Cache intermediate results. Decide how entries become stale.
“entries expire after ttl”	Combine eviction with TTL and expiry. Expired entries usually free a slot before anything is evicted.
“O(1) per operation”	A sorted structure or a scan won’t do. You need the map + list pairing.

How it works

What's inside an O(1) cache

diagram

structureLRULFU

The map finds a key's node in O(1). The list keeps recency order: a hit unlinks the node and pushes it to the front (four pointer writes); eviction takes the node just before the tail sentinel and deletes its key from the map. Each node stores its key so eviction can find the map entry.

LRU: hash map + doubly linked list

1. A map from key to list node. The node holds the key and the value.
2. A doubly linked list in recency order. Use two sentinel nodes (dummy head and tail) so every insert and unlink is the same four pointer writes, with no special case for an empty list or the ends.
3. On a hit, unlink the node and push it to the front. Both are O(1) because the node knows its neighbours. That’s why the list must be doubly linked: a singly linked list can’t unlink a node without walking to its predecessor.
4. On a miss when full, the victim is the node at the back. Unlink it and delete its key from the map. That’s why each node must store its key.

Here’s the list half, with sentinels. It’s the building block, not a cache: it knows nothing about capacity or values.

Python

order_list.py

from __future__ import annotations


class Node:
    __slots__ = ("key", "prev", "next")

    def __init__(self, key: str) -> None:
        self.key = key
        self.prev: Node = self  # a detached node points at itself
        self.next: Node = self


class OrderList:
    """Doubly linked list with two sentinels, so no splice ever checks for missing ends."""

    def __init__(self) -> None:
        self.head, self.tail = Node("<head>"), Node("<tail>")  # 1. sentinels
        self.head.next, self.tail.prev = self.tail, self.head

    def push_front(self, n: Node) -> None:  # 2. O(1): four pointer writes
        n.prev, n.next = self.head, self.head.next
        self.head.next.prev = n
        self.head.next = n

    def unlink(self, n: Node) -> None:  # 3. O(1): neighbours point past n
        n.prev.next = n.next
        n.next.prev = n.prev
        n.prev = n.next = n

    def back(self) -> Node | None:  # 4. the node at the far end, or None if empty
        return None if self.tail.prev is self.head else self.tail.prev

    def keys(self) -> list[str]:
        out, cur = [], self.head.next
        while cur is not self.tail:
            out.append(cur.key)
            cur = cur.next
        return out


if __name__ == "__main__":
    lst, nodes = OrderList(), {k: Node(k) for k in "abc"}
    for k in "abc":
        lst.push_front(nodes[k])
    assert lst.keys() == ["c", "b", "a"]
    lst.unlink(nodes["a"])  # "touch" a: unlink, then push to the front
    lst.push_front(nodes["a"])
    assert lst.keys() == ["a", "c", "b"] and lst.back() is nodes["b"]
    for n in list(nodes.values()):
        lst.unlink(n)
    assert lst.keys() == [] and lst.back() is None
    print("ok")

TypeScript

order_list.ts

import assert from "node:assert/strict";

class ListNode {
  prev: ListNode | null = null;
  next: ListNode | null = null;
  constructor(readonly key: string) {}
}

/** Doubly linked list with two sentinels, so no splice ever checks for null ends. */
class OrderList {
  private readonly head = new ListNode("<head>"); // 1. sentinels
  private readonly tail = new ListNode("<tail>");
  constructor() { this.head.next = this.tail; this.tail.prev = this.head; }

  pushFront(n: ListNode): void { // 2. O(1): four pointer writes
    n.prev = this.head;
    n.next = this.head.next;
    this.head.next!.prev = n;
    this.head.next = n;
  }

  unlink(n: ListNode): void { // 3. O(1): neighbours point past n
    n.prev!.next = n.next;
    n.next!.prev = n.prev;
    n.prev = n.next = null;
  }

  back(): ListNode | null { // 4. the node at the far end, or null if empty
    return this.tail.prev === this.head ? null : this.tail.prev;
  }

  keys(): string[] {
    const out: string[] = [];
    for (let cur = this.head.next!; cur !== this.tail; cur = cur.next!) out.push(cur.key);
    return out;
  }
}

const lst = new OrderList();
const nodes = new Map([..."abc"].map((k) => [k, new ListNode(k)] as const));
for (const k of "abc") lst.pushFront(nodes.get(k)!);
assert.deepEqual(lst.keys(), ["c", "b", "a"]);
lst.unlink(nodes.get("a")!); // "touch" a: unlink, then push to the front
lst.pushFront(nodes.get("a")!);
assert.deepEqual(lst.keys(), ["a", "c", "b"]);
assert.equal(lst.back(), nodes.get("b"));
for (const n of nodes.values()) lst.unlink(n);
assert.deepEqual(lst.keys(), []);
assert.equal(lst.back(), null);
console.log("ok");

C#

order_list.cs

var lst = new OrderList();
var nodes = "abc".ToDictionary(c => c.ToString(), c => new ListNode(c.ToString()));
foreach (var k in new[] { "a", "b", "c" }) lst.PushFront(nodes[k]);
if (string.Join(",", lst.Keys()) != "c,b,a") throw new Exception("push order");
lst.Unlink(nodes["a"]); // "touch" a: unlink, then push to the front
lst.PushFront(nodes["a"]);
if (string.Join(",", lst.Keys()) != "a,c,b" || lst.Back() != nodes["b"]) throw new Exception("move to front");
foreach (var n in nodes.Values) lst.Unlink(n);
if (lst.Keys().Count != 0 || lst.Back() != null) throw new Exception("should be empty");
Console.WriteLine("ok");

class ListNode(string key)
{
    public string Key { get; } = key;
    public ListNode? Prev, Next;
}

// Doubly linked list with two sentinels, so no splice ever checks for null ends.
// (.NET's LinkedList<T> does the same job; this shows the pointer work.)
class OrderList
{
    readonly ListNode head = new("<head>"), tail = new("<tail>"); // 1. sentinels
    public OrderList() { head.Next = tail; tail.Prev = head; }

    public void PushFront(ListNode n) // 2. O(1): four pointer writes
    {
        n.Prev = head; n.Next = head.Next;
        head.Next!.Prev = n; head.Next = n;
    }

    public void Unlink(ListNode n) // 3. O(1): neighbours point past n
    {
        n.Prev!.Next = n.Next; n.Next!.Prev = n.Prev;
        n.Prev = n.Next = null;
    }

    public ListNode? Back() => tail.Prev == head ? null : tail.Prev; // 4. far end, or null

    public List<string> Keys()
    {
        var output = new List<string>();
        for (var cur = head.Next!; cur != tail; cur = cur.Next!) output.Add(cur.Key);
        return output;
    }
}

Library shortcuts, and why interviewers ban them

Python’s collections.OrderedDict has move_to_end(key) and popitem(last=False), so it is already an LRU list. JavaScript’s Map iterates in insertion order, so delete then set moves a key to the end, and map.keys().next().value is the oldest. .NET has LinkedList<T> whose Remove(node) and AddFirst(node) are O(1), paired with a Dictionary<K, LinkedListNode<T>>. Mention these, then expect “now build the ordering yourself”.

LFU: frequency buckets

1. A map from key to its value, its use count and its node.
2. A second map from count → recency list of keys with that count. Each list is the same sentinel list as above.
3. Keep min_freq, the smallest count with a non-empty list.
4. On a hit, unlink the key from list f, push it onto list f+1. If list f is now empty and f == min_freq, bump min_freq to f+1.
5. On a new key when full, evict the least recent key from list min_freq. Then insert the new key at count 1 and set min_freq = 1.

Step 5’s last move is the one people miss: a new entry always has the lowest possible count, so min_freq resets without a search. That observation is what makes LFU O(1), from Shah, Mitra and Matani’s 2010 paper.

FIFO, for comparison

FIFO needs only a queue and a set: hits don’t reorder anything. It’s the cheapest to run and the easiest to reason about, which makes it a good baseline for measuring hit rates.

Python

fifo_hits.py

from collections import deque


def fifo_hits(requests: list[str], capacity: int) -> int:
    """Count cache hits under first-in-first-out eviction."""
    order: deque[str] = deque()  # 1. arrival order: left = oldest
    cached: set[str] = set()  # 2. O(1) membership test
    hits = 0
    for key in requests:
        if key in cached:
            hits += 1  # 3. FIFO ignores hits: the order does not change
            continue
        if len(cached) == capacity:
            cached.discard(order.popleft())  # 4. evict the oldest arrival
        order.append(key)
        cached.add(key)
    return hits


if __name__ == "__main__":
    reqs = "A B C A B D A E B A C B".split()
    assert fifo_hits(reqs, 3) == 4
    assert fifo_hits("A B C D A B C D".split(), 3) == 0  # loop one bigger than the cache
    assert fifo_hits("A A A".split(), 1) == 2
    assert fifo_hits([], 2) == 0
    print("ok")

TypeScript

fifo_hits.ts

import assert from "node:assert/strict";

/** Count cache hits under first-in-first-out eviction. */
function fifoHits(requests: string[], capacity: number): number {
  const order: string[] = []; // 1. arrival order: front = oldest
  let front = 0; // index of the oldest live entry (avoids O(n) shift())
  const cached = new Set<string>(); // 2. O(1) membership test
  let hits = 0;
  for (const key of requests) {
    if (cached.has(key)) {
      hits++; // 3. FIFO ignores hits: the order does not change
      continue;
    }
    if (cached.size === capacity) cached.delete(order[front++]); // 4. evict the oldest arrival
    order.push(key);
    cached.add(key);
  }
  return hits;
}

assert.equal(fifoHits("A B C A B D A E B A C B".split(" "), 3), 4);
assert.equal(fifoHits("A B C D A B C D".split(" "), 3), 0); // loop one bigger than the cache
assert.equal(fifoHits(["A", "A", "A"], 1), 2);
assert.equal(fifoHits([], 2), 0);
console.log("ok");

C#

fifo_hits.cs

// Count cache hits under first-in-first-out eviction.
static int FifoHits(IEnumerable<string> requests, int capacity)
{
    var order = new Queue<string>();   // 1. arrival order: Peek() = oldest
    var cached = new HashSet<string>(); // 2. O(1) membership test
    int hits = 0;
    foreach (var key in requests)
    {
        if (cached.Contains(key)) { hits++; continue; } // 3. FIFO ignores hits
        if (cached.Count == capacity) cached.Remove(order.Dequeue()); // 4. evict the oldest arrival
        order.Enqueue(key);
        cached.Add(key);
    }
    return hits;
}

if (FifoHits("A B C A B D A E B A C B".Split(' '), 3) != 4) throw new Exception("expected 4");
if (FifoHits("A B C D A B C D".Split(' '), 3) != 0) throw new Exception("loop: expected 0");
if (FifoHits(["A", "A", "A"], 1) != 2) throw new Exception("expected 2");
if (FifoHits([], 2) != 0) throw new Exception("expected 0");
Console.WriteLine("ok");

What it costs

Policy	get	put	Extra space	Weak spot
FIFO	O(1)	O(1)	queue + set	ignores popularity completely
LRU (map + DLL)	O(1)	O(1)	2 pointers per entry	a one-off scan flushes the hot set
LFU (map + buckets)	O(1)	O(1)	count + 2 pointers per entry	stale popularity never decays
LRU via sorted timestamps	O(log n)	O(log n)	tree or heap	slower, but easy to get right
LRU via scanning for the oldest	O(1)	O(n)	none	fails “O(1) per operation”

Why O(1) needs both structures. A map alone has no order, so finding the victim is a scan. A list alone has order, but finding a key is a scan. The map gives you the node; the node gives you its position in the list. Each structure covers the other’s blind spot.

Where the time really goes. In real systems, a miss costs thousands of times more than a hit (a database query vs. a memory read). Raising the hit rate from 90% to 95% halves the misses. That’s why production caches spend effort on smarter policies, not faster pointer updates.

Variations you’ll meet

• Approximate LRU. Redis doesn’t keep a full list. On eviction it samples a few keys (maxmemory-samples, default 5) and drops the oldest of the sample. Close to LRU, far less memory.
• LFU with decay. Redis’s LFU uses a small logarithmic counter that also decays over time, so a key that was popular last week can fall out. That fixes the “popularity shift” scenario above.
• Segmented LRU / 2Q / ARC. Split the cache into a “seen once” area and a “seen twice” area, so one-off scans can’t flush the popular keys. ARC adapts the split automatically.
• W-TinyLFU (used by Java’s Caffeine): a small LRU window in front of a frequency-filtered main area, with approximate counts in a compact sketch.
• Size-aware eviction. Entries have different sizes; capacity is in bytes. Evict until the new entry fits, which may mean several victims.
• Write policies. Write-through (update the cache and the store together), write-back (update the cache, flush later), cache-aside (the app reads the store on a miss and fills the cache).

Pitfalls

• Updating an existing key evicts something. If the key is already cached, a put replaces its value and refreshes its position. Nothing should be evicted, because the size doesn’t change.
• Forgetting the key in the node. Without it, you find the LRU node but can’t delete its map entry. The map then points at a dead node.
• Off-by-one on “full”. Evict when size == capacity before inserting, not after.
• Capacity 0. Decide: every put is a no-op, or reject it. Say it out loud.
• LFU min_freq bugs. Bumping min_freq when a non-minimum bucket empties, or not resetting it to 1 on insert.
• A miss that changes state. A get on a missing key must not insert, reorder, or count as a use. Only statistics change.
• Caching mutable values. Hand out a reference to a cached list and the caller edits your cache. Copy, or store immutable values.

In the interview

• Ask: “Does get count as a use? Does updating a value count? What happens at capacity 0? Are keys hashable and values small?”
• Say the invariant: “The map and the list always hold the same keys, and the list is in recency order, most recent at the front.” Then check it after every operation in your tests.
• State costs per operation, and why the list is doubly linked.
• Expect follow-ups: delete a key, resize the capacity (evict several in order), add TTLs, add hit/miss statistics, make it thread-safe (one lock around each operation, or sharding by key hash), or “how would you pick a policy for this workload?” (measure the hit rate on a real trace, as in the sandbox above).

Check yourself

Check yourself

pick one

Why must the list in an O(1) LRU cache be doubly linked?

ASo you can iterate it in both directions when printingBSo you can unlink a node you found through the map without walking to its predecessorCBecause singly linked lists cannot have sentinels

Check yourself

pick one

Capacity 3. Requests: A B C D A B C D A B C D. How many hits does LRU get?

A0B3C6D9

Check yourself

pick one

In an LFU cache, a brand-new key is inserted after an eviction. What should min_freq become?

AUnchangedBmin_freq + 1C1DThe smallest count found by scanning all buckets

Practice on your own

These are classic exercises, not gym questions:

• Measure the hit rate of FIFO, LRU and LFU on a skewed (Zipf-like) random request stream. At what capacity do they converge?
• Implement Belady’s OPT offline for a known request list, using “next use” positions. Prove it never does worse than LRU on a few examples.
• Implement a CLOCK cache (second-chance): a circular buffer with one “referenced” bit per slot. Compare its hit rate to LRU.
• Implement 2Q: a FIFO for first-time keys and an LRU for keys seen twice.

Go deeper

• L. A. Belady, “A study of replacement algorithms for a virtual-storage computer”, IBM Systems Journal 5(2), 1966: the optimal policy.
• K. Shah, A. Mitra, D. Matani, “An O(1) algorithm for implementing the LFU cache eviction scheme” (2010).
• Redis docs, “Key eviction”: approximated LRU, LFU with decay.
• Python collections.OrderedDict and functools.lru_cache.

Related

Linked listsSentinels and O(1) splicing.

TTL and expiryEntries that go stale on a timer.

MemoizationA cache in front of a pure function.

Memory efficiencyWhat each entry really costs.