Mission Compile - System Design Learning Platform

1The Closet Analogy

💡 Simple Analogy

Your closet (cache) can only fit 20 items. You want to buy a new jacket but it's full. What do you donate?

LRU: Donate clothes you haven't worn in longest time
LFU: Donate clothes you wear least frequently
FIFO: Donate the oldest clothes you bought
Random: Close eyes and pick randomly

2Eviction Simulator

Eviction Policy Demo (Capacity: 4)

Cache contents (0/4):

Empty

3Common Eviction Policies

LRU (Least Recently Used)

Remove item that hasn't been accessed for longest time.

How: Track last access time for each item. Evict oldest.

Pros: Good for recency-based access patterns, Simple concept, Most popular policy

Cons: One-time accesses can pollute cache, Needs tracking metadata

Complexity: O(1) with hash map + doubly linked list

LFU (Least Frequently Used)

Remove item that has been accessed fewest times.

How: Track access count for each item. Evict lowest count.

Pros: Great for frequency-based patterns, Keeps hot data longer

Cons: Old popular items never evicted, More complex to implement

Complexity: O(log n) or O(1) with optimized structure

FIFO (First In, First Out)

Remove item that was added to cache longest ago.

How: Queue structure. Evict from front, add to back.

Pros: Very simple, Low overhead, Predictable

Cons: Ignores access patterns, Can evict frequently used items

Complexity: O(1)

Random

Remove a randomly selected item.

How: Pick random key and evict it.

Pros: Simplest to implement, No metadata needed

Cons: Unpredictable, Can evict important items

Complexity: O(1)

TTL (Time-To-Live)

Items expire after fixed time regardless of access.

How: Store expiration timestamp. Remove when expired.

Pros: Ensures freshness, Good for time-sensitive data

Cons: May evict frequently accessed data, Needs expiration checks

Complexity: O(1) with lazy expiration

4LRU Implementation

LRU is most commonly asked in interviews. Here's how it works:

Data Structure: Hash Map + Doubly Linked List

Hash Map:O(1) key lookup → pointer to list node

Linked List:Order by recency. Head = most recent, Tail = least recent

LRU Cache (Pseudocode)

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key → node
        self.head = Node()  # dummy head (most recent)
        self.tail = Node()  # dummy tail (least recent)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            self._move_to_head(node)  # Mark as recently used
            return node.value
        return -1

    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)
        else:
            if len(self.cache) >= self.capacity:
                # Evict LRU (tail.prev)
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]
            
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._add_to_head(new_node)

5Comparison Table

Policy	Best For	Avoid When
LRU	General purpose, web caches	Scan patterns (read once, never again)
LFU	Frequency-based access (CDN)	Access patterns change over time
FIFO	Simple caches, streaming data	Data has varying importance
TTL	Time-sensitive data, sessions	Access frequency matters more than age

6Interview Tips

Common Interview Question

"Design an LRU Cache" is a classic LeetCode problem. Key points:

Use Hash Map + Doubly Linked List for O(1) operations
Explain why both structures are needed
Handle edge cases: capacity=0, duplicate puts
Discuss thread safety if asked (locks, concurrent hash map)

7Key Takeaways

1LRU is most common-evicts least recently used items. Good default choice.

2LFU evicts least frequently used-better for stable access patterns.

3LRU needs Hash Map + Doubly Linked List for O(1) get/put.

4TTL is often combined with other policies for freshness.

5In interviews, be ready to implement LRU cache from scratch.

6Real systems like Redis support multiple eviction policies.

8Interview Follow-up Questions

Interview Follow-up Questions

Common follow-up questions interviewers ask

9Test Your Understanding

Test Your Understanding

5 questions

1

LRU cache implementation requires which data structures for O(1) operations?

2

Which eviction policy is best for data with stable popularity over time?

3

What is a key disadvantage of LFU eviction?

4

Redis uses which eviction approach?

5

In an LRU cache, when a key is accessed (get operation), what happens?

0 of 5 answered

Cache Eviction Policies