Since memory (RAM) is expensive and finite, a cache cannot store data forever. An Eviction Policy determines which data to remove when the cache becomes full.

Think of a Small Bookshelf:

1. You can only fit 10 books.
2. You buy an 11th book. Which one do you throw away?
   • FIFO: Throw away the very first book you ever bought. (Fair, but maybe you still use it!).
   • LRU: Throw away the book you haven't touched in the longest time. (Most popular).
   • LFU: Throw away the book you have only ever read once.

---

1. LRU (Least Recently Used)

• Concept: Discards the least recently used items first.
• Logic: If you haven't used it recently, you probably won't use it soon.
• Usage: Used in almost all modern caches (Redis, Memcached) and OS memory management.

2. LFU (Least Frequently Used)

• Concept: Counts how many times an item is used. Discards items with the lowest count.
• Usage: Best when certain items are "persistently popular" regardless of when they were last used.

3. FIFO (First In First Out)

• Concept: The oldest entry is removed first.
• Usage: Simple but often inefficient because "old" might still be "popular."

4. Random Replacement (RR)

• Concept: Randomly selects a candidate for eviction.
• Usage: Surprisingly useful in systems with very low memory overhead where tracking usage is too expensive.

---

Use Case: LRU

Whenever an interviewer asks about cache management, LRU is usually the safest and most standard answer.

Implementation: How do you build LRU?

This is a common coding question!

• Answer: Use a Doubly Linked List (to keep track of order) + a Hash Map (for $O(1)$ lookup).
• When an item is used, move it to the "Head" of the list. When the cache is full, delete the "Tail."

Key Question

"What happens if your eviction policy is bad?" Answer: You get a high Cache Miss Ratio, which puts massive pressure on your Database and slows down your entire system. 🧹