Intermediate LevelData Structures & Algorithms
How do you implement an LRU Cache in O(1) time?
ā Interview Prompt: Design an LRU (Least Recently Used) cache with O(1) get and put using a doubly linked list and hash map.
LRU Cache: Evicts the least recently used item when at capacity.
Data Structures:
ā¢
Hash Map (key ā node): $O(1)$ lookup.
ā¢
Doubly Linked List (ordered by recency): $O(1)$ insertion and deletion from both ends.
ā¢
Head = most recently used (MRU).
ā¢
Tail = least recently used (LRU).
Operations:
ā¢
Get(key): Move node to head. Return value.
ā¢
Put(key, val): Insert at head. If at capacity ā evict tail.
Code Implementation Example
typescript
class LRUCache {
private map = new Map<number, { key: number; val: number; prev: any; next: any }>();
private head = { key: 0, val: 0, prev: null as any, next: null as any };
private tail = { key: 0, val: 0, prev: null as any, next: null as any };
private capacity: number;
constructor(capacity: number) {
this.capacity = capacity;
this.head.next = this.tail;
this.tail.prev = this.head;
}
private moveToFront(node: any) {
this.remove(node);
this.insertFront(node);
}
private remove(node: any) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private insertFront(node: any) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
get(key: number): number {
if (!this.map.has(key)) return -1;
const node = this.map.get(key)!;
this.moveToFront(node);
return node.val;
}
put(key: number, value: number): void {
if (this.map.has(key)) {
const node = this.map.get(key)!;
node.val = value;
this.moveToFront(node);
} else {
if (this.map.size === this.capacity) {
const lru = this.tail.prev;
this.remove(lru);
this.map.delete(lru.key);
}
const node = { key, val: value, prev: null, next: null };
this.insertFront(node);
this.map.set(key, node);
}
}
}š”LRU Cache with O(1) get/put using doubly linked list + hash map.
šÆ Interview Key Takeaway
LRU Cache = HashMap (O(1) lookup) + Doubly Linked List (O(1) eviction order). This exact design is used in CPU caches, CDNs, and OS page tables.
#DSA#LRU Cache#Design#Hash Map#Intermediate
Back to all Data Structures & Algorithms Questionsā