Problem
Design a Least Recently Used (LRU) cache with O(1) get and put operations.
Example
Input: LRUCache(2), put(1,1), put(2,2), get(1)=1, put(3,3), get(2)=-1
Output: 1, then -1Solution
Hash map + doubly linked list. Map stores key -> node. List ordered by recency.
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.cache = {} # OrderedDict would simplify
from collections import OrderedDict
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.cap:
self.cache.popitem(last=False)class LRUCache {
constructor(capacity) {
this.cap = capacity;
this.cache = new Map();
}
get(key) {
if (!this.cache.has(key)) return -1;
const v = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, v);
return v;
}
put(key, value) {
if (this.cache.has(key)) this.cache.delete(key);
this.cache.set(key, value);
if (this.cache.size > this.cap) {
this.cache.delete(this.cache.keys().next().value);
}
}
}class LRUCache {
int cap;
list<pair<int, int>> lst;
unordered_map<int, list<pair<int, int>>::iterator> mp;
public:
LRUCache(int capacity) : cap(capacity) {}
int get(int key) {
if (!mp.count(key)) return -1;
lst.splice(lst.begin(), lst, mp[key]);
return mp[key]->second;
}
void put(int key, int value) {
if (mp.count(key)) {
mp[key]->second = value;
lst.splice(lst.begin(), lst, mp[key]);
return;
}
if (lst.size() == cap) {
mp.erase(lst.back().first);
lst.pop_back();
}
lst.push_front({key, value});
mp[key] = lst.begin();
}
};class LRUCache extends LinkedHashMap<Integer, Integer> {
private final int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}
public int get(int key) { return getOrDefault(key, -1); }
public void put(int key, int value) { super.put(key, value); }
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}Complexity
- Time: O(1)
- Space: O(capacity)
Explanation
Linked list gives O(1) reordering. Hash map gives O(1) lookup of nodes. Together they enable both ops in constant time.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?