Caching Applications
A Cache is a high-speed data storage layer that stores a subset of data, so that future requests for that data are served up faster.
The most common caching eviction policy is LRU (Least Recently Used):
- If the cache is full, remove the item that hasn’t been used for the longest time.
- If an item is accessed (read or written), move it to the “Most Recently Used” position.
The Challenge: O(1) Everything
We need a data structure that supports:
- Get(key): O(1)
- Put(key, value): O(1)
- Delete(key): O(1) (for eviction)
- Maintain Order: Know which item is oldest.
Solution: Combine a Hash Map with a Doubly Linked List.
- Hash Map: Maps
Key→Node. Gives O(1) access. - Doubly Linked List: Maintains order.
Head= Most Recent,Tail= Least Recent. Moving a node to the head is O(1).
Interactive LRU Simulator
Capacity: 3 items. Watch how the order changes as you access items. The item at the bottom (Tail) is the next to be evicted!
LRU Cache (Size 3)
Cache is empty.
HASH MAP (Key → Node)
LINKED LIST (Head=MRU, Tail=LRU)
Implementation Code
Using Python’s OrderedDict, an LRU Cache is trivial (it maintains insertion order automatically).
Java
Go
```java
// Using LinkedHashMap for simplicity.
// In interviews, you may need to implement the DoublyLinkedList manually.
class LRUCache extends LinkedHashMap<Integer, Integer> {
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true); // true for access-order
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
```
```go
import "container/list"
type LRUCache struct {
capacity int
cache map[int]*list.Element
list *list.List
}
type Pair struct {
key int
value int
}
func Constructor(capacity int) LRUCache {
return LRUCache{
capacity: capacity,
cache: make(map[int]*list.Element),
list: list.New(),
}
}
func (this *LRUCache) Get(key int) int {
if element, exists := this.cache[key]; exists {
this.list.MoveToFront(element)
return element.Value.(*Pair).value
}
return -1
}
func (this *LRUCache) Put(key int, value int) {
if element, exists := this.cache[key]; exists {
element.Value.(*Pair).value = value
this.list.MoveToFront(element)
return
}
if this.list.Len() == this.capacity {
// Evict LRU
lru := this.list.Back()
this.list.Remove(lru)
delete(this.cache, lru.Value.(*Pair).key)
}
// Insert MRU
newElement := this.list.PushFront(&Pair{key, value})
this.cache[key] = newElement
}
```
In a pure “Design” interview, you would implement the Doubly Linked List manually to show you understand the pointers.