LRU Cache Concept
DSA · Hash Maps & Setssyntax
Least Recently Used cache: evict the oldest unused entry when at capacity.
Implement with: Hash Map + Doubly Linked List
- Map: key → node (O(1) lookup)
- DLL: maintains access order (O(1) move/remove)example
// JavaScript — Simplified using Map (preserves insertion order)
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}
get(key) {
if (!this.cache.has(key)) return -1;
const val = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, val); // move to end (most recent)
return val;
}
put(key, value) {
this.cache.delete(key);
this.cache.set(key, value);
if (this.cache.size > this.capacity) {
const oldest = this.cache.keys().next().value;
this.cache.delete(oldest);
}
}
}
# Python — Using OrderedDict
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)output
cache = LRUCache(2)
cache.put(1, 1); cache.put(2, 2)
cache.get(1) → 1
cache.put(3, 3) → evicts key 2
cache.get(2) → -1Note Both get and put must be O(1). In a real interview, they may want the DLL implementation from scratch — practice building a Node class with prev/next pointers. This is one of the most commonly asked design questions at top companies.