What Is a Cache Eviction Policy? The Decision Every Cache Has to Make

Your cache is full. A new item just arrived. Something has to leave. A cache eviction policy is the bouncer making that call, and unlike an actual bouncer, it has to be right every single time.

Why Caches Have to Evict Anything

A cache is fast, bounded storage that sits between slow storage and your program. CPU caches sit between RAM and the processor. Redis sits between your database and your application. A browser cache sits between the network and your page renderer.

The "bounded" part is what forces eviction. RAM costs money. Cache coherence gets complicated. And past a certain size, a larger cache stops being faster. So every practical cache has a maximum capacity, and once it fills up, adding a new item means removing an old one.

The removed item is evicted. The rule that picks which item goes is the eviction policy. Get it right and your hit rate stays high. Get it wrong and you keep evicting items you are about to need again.

The Four Eviction Policies You Need to Know

FIFO: First In, First Out

Remove whichever item arrived first. No tracking of access patterns, just a queue. Item A went in before item B, so A leaves first when space runs out.

FIFO evicts like a company with a no-exceptions seniority rule: the longest-tenured employee goes first in a layoff, regardless of performance. Your hottest, most-requested item gets tossed because it happened to arrive first. An item added ten minutes ago might be your most active lookup. FIFO does not care. It's old, it's gone.

In practice, FIFO performs worse than almost every alternative on realistic workloads. There is a reason nobody builds production caches with it.

Random Replacement

Pick a victim at random. Surprisingly, not terrible. It avoids the pathological cases that hurt FIFO and LRU under certain access patterns. Some CPU cache designs use it because the hardware cost of tracking recency is too high.

For software interviews you will not implement it, but knowing it exists is worth something in system design conversations. Sometimes "just pick something" is the most honest eviction philosophy available.

LFU: Least Frequently Used

Track how many times each item has been accessed. When you need to evict, remove the item with the lowest access count.

LFU rewards items that are genuinely popular over the long run. If one item has been hit 500 times and another twice, LFU correctly identifies the low-frequency item as the better eviction candidate.

The problem: LFU suffers from cache pollution. An item accessed heavily in the past but never again will have a high count and resist eviction forever. Your LFU cache fills up with museum pieces from access patterns that no longer exist. There is also the tie-breaking question when multiple items share the lowest frequency. The standard answer: among ties, evict the least recently used. That is what LeetCode 460 expects.

LFU requires O(1) get and put, which takes a non-obvious three-component design. See LFU Cache implementation for the full breakdown.

LRU: Least Recently Used

Remove the item that was accessed longest ago. Not the oldest by insertion time, the one that went longest without being touched.

LRU is the default answer for almost every cache eviction question in interviews. It approximates the optimal eviction policy (OPT, which requires seeing the future) better than any other practical policy on most real-world workloads. Modern operating systems use variants of LRU for virtual memory page replacement. Redis supports it. CPU cache controllers use approximations of it.

Your interviewer wrote "LRU" on their notepad before you walked in the door. The question is whether your explanation earns a checkmark next to it.

How LRU Actually Works

You need two data structures in a committed relationship.

1. O(1) lookup by key: is this item in the cache?
2. O(1) update of access order: move an item to "most recently used" in constant time.

A hash map gives you (1). A doubly linked list gives you (2). Together they give you LRU in O(1) for both get and put.

The doubly linked list maintains access order: head is most recently used, tail is least recently used. On every get or put, the accessed node moves to the head. When you need to evict, remove from the tail.

Here is the Python implementation using OrderedDict, which wraps the doubly linked list for you:

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

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

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

In an interview you may be asked to implement it explicitly with a ListNode class and sentinel nodes. That proves you understand the mechanics rather than just the API.

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.cache = {}
        self.head = Node()
        self.tail = Node()
        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.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._insert_front(node)
        return node.val

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

Sentinel nodes (the dummy head and tail) eliminate the edge-case handling you would otherwise need when the list is empty or you are removing from the ends. They are load-bearing dummies. Every insert and remove uses the same code path regardless of list state. Memorize this pattern.

Your chair pile is a working LRU cache. The floor is your working set. The closet is disk. Cache misses require opening the closet.

Complexity

Policy	Get	Put	Space
FIFO	O(1)	O(1)	O(n)
Random	O(1)	O(1)	O(n)
LRU	O(1)	O(1)	O(n)
LFU	O(1)	O(1)	O(n)

All four are O(n) space for a cache of size n. The difference is whether get and put are genuinely O(1) or require traversal. A naive LRU using a sorted list would be O(n) per operation.

The important complexity question in interviews is not the policy itself but the implementation. Interviewers want to see that you know why the naive approach is too slow and how the combined data structure fixes it. Saying "hash map plus doubly linked list" without explaining why neither structure alone is sufficient is half an answer.

The Clock Algorithm: LRU's Cheaper Cousin

Real operating systems cannot afford a full doubly linked list for every page in virtual memory. Instead they use the clock algorithm, also called second-chance FIFO. Each page has a reference bit. When a page is accessed, its bit is set to 1. When the OS needs to evict, it sweeps through pages in circular order: if the bit is 1, clear it and move on (second chance); if the bit is 0, evict.

This approximates LRU with O(1) amortized cost and no pointer manipulation. You probably will not implement it in a coding interview, but knowing it exists shows depth in a system design round and makes for a good follow-up when the interviewer asks "how would a real OS do this?"

Why Interviews Are Obsessed with LRU Cache

LRU Cache (LeetCode 146) is one of the most commonly asked problems at FAANG and beyond. Phone screens, onsites, take-homes. The reason it is popular: it requires combining two data structures whose interaction is non-obvious, and it tests whether you can reason about O(1) constraints under pressure.

The question has a clear brute-force path (sorted list, O(n) per operation) and a clear optimal path (HashMap + DLL, O(1)). The gap between them is the entire point. A candidate who immediately jumps to the optimal solution without explaining why skips most of what the interviewer is listening for.

"Great, you've been styling dropdowns for five years. Quick: implement an LRU cache in O(1)."

Eviction policy also shows up in system design. If you are designing a distributed cache, you need to pick a policy and justify it based on the access pattern you expect. "How would you modify your LRU to support TTL expiration?" is a common follow-up. So is "what if you needed most frequently accessed items instead of most recently accessed?" Both questions have real answers and real tradeoffs.

If you want to practice explaining your eviction reasoning out loud under real interview conditions, SpaceComplexity runs voice-based mock interviews where you have to talk through data structure decisions in real time, which is closer to the actual interview than typing solutions in silence.

For a deeper comparison of when LRU beats LFU and which workloads flip the outcome, see LRU vs LFU Cache.

Key Takeaways

• A cache must evict when full. The policy decides which item leaves.
• FIFO ignores access patterns. Random is decent. LFU tracks long-run popularity. LRU tracks recency.
• LRU is the default interview answer because it approximates optimal behavior on most real workloads.
• LRU requires O(1) get and put. That means HashMap plus doubly linked list. Neither structure alone is sufficient.
• Sentinel nodes eliminate edge cases in the linked list. Use them.
• The clock algorithm approximates LRU cheaply. It is how operating systems actually do page replacement.
• LRU Cache (LC 146) and LFU Cache (LC 460) are both high-frequency interview problems. Know both.

Further Reading

• Cache replacement policies, Wikipedia, thorough overview of FIFO, LRU, LFU, Clock, and more
• Redis eviction policies, how Redis lets you pick between allkeys-lru, volatile-lfu, and others at configuration time
• LRU Cache, LeetCode 146, the canonical interview problem
• LFU Cache, LeetCode 460, the harder follow-up, requires the three-map design
• CPU cache, Wikipedia, how hardware caches apply replacement policies at nanosecond timescales