LRU cache
On the roadmap:Beginner · step 7: Caching basics
A fixed-size cache that evicts the least recently used entry, using the insertion order of a Map for O(1) operations.
In plain words
A small cache that is full on purpose. When it needs room it throws away whatever has gone longest without being used.
Why it matters
Memory is limited, so a cache needs a rule for what to drop. 'Least recently used' works well because recent items tend to be asked for again.
Where you meet it
- Redis and memcached eviction
- Browser, operating system and database page caches
- Application caches in front of a database
You will be able to
- Keep get and set at constant time
- Track hits and misses to judge a cache
- Compare LRU with other rules such as LFU
In interviews
A classic coding question and a building block for 'design a cache'.
Practise on the Interview Ready roadmap1Learn the idea first
2See it work before you read the code
3Build it and run the check
What you build
- get() refreshes recency by re-inserting the key
- set() evicts the oldest key when full
- Hit and miss counters
export class LruCache<V> {
private map = new Map<string, V>(); // a Map iterates in insertion order
hits = 0;
misses = 0;
constructor(private capacity: number) {}
get(key: string): V | undefined {
if (!this.map.has(key)) { this.misses++; return undefined; }
const v = this.map.get(key)!;
this.map.delete(key); this.map.set(key, v); // move to most recent
this.hits++;
return v;
}
set(key: string, value: V): void {
this.map.delete(key);
this.map.set(key, value);
if (this.map.size > this.capacity) this.map.delete(this.map.keys().next().value as string); // oldest first
}
}
Rather run it on your own computer?
Save the code as index.ts and the check as check.ts in one folder. The check exits with an error if anything is wrong and prints lru-cache ok when everything passes. You need Node.js installed.
mkdir lru-cache && cd lru-cache
# save index.ts and check.ts in this folder
npx tsx check.tsHow real systems do it
This lab is the core idea in a small form. Here is what production versions add or do differently.
- Redis does not track exact recency. It samples a few keys and evicts the oldest of the sample, which is cheaper at scale.
- Modern caches such as Caffeine use admission policies like TinyLFU, which also consider how often a key is used, so one big scan cannot flush the cache.
- Real caches add expiry times, byte-size limits and sharded locks so many threads can use them at once.
Cache eviction rules
| What it drops | Strength | Weakness | Pick it when | |
|---|---|---|---|---|
| LRU (least recently used) | The entry unused for the longest time | Adapts to what is popular now | One big scan can flush the cache | General purpose caching |
| LFU (least frequently used) | The entry used the fewest times | Keeps long-term favourites | Slow to forget what was once popular | Popularity is stable |
| FIFO | The oldest entry added | Trivial | Ignores how much an entry is used | A simple buffer |
| TinyLFU (admission policy) | Only admits a new entry if it looks more valuable | Resists scans | More complex | High-traffic caches |
| Random | A random entry | Very cheap | Unpredictable hit rate | Cost matters more than hit rate |
What it cannot do
A scan can empty the cache
Reading every key once pushes out everything useful. Admission policies exist to prevent this.
It ignores how often something is used
An item used a thousand times and one used once look the same if both are recent.
It ignores size and cost
A huge, cheap entry and a tiny, costly one count equally.
Many threads need locks or sharding
Every read changes the order, so concurrent access needs care.
4Now extend it
Each one makes your version closer to what real systems do. Pick one and make the check cover it.
- Rewrite with an explicit doubly linked list and hash map
- Add LFU and compare hit rates on a skewed workload
- Add a size-in-bytes limit