Solution: LRU Cache with Hash Map + Doubly Linked List
class Node:
"""Doubly linked list node"""
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
"""
LRU Cache implementation
Time Complexity:
- get: O(1)
- put: O(1)
Space Complexity: O(capacity)
"""
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # key -> Node
# Dummy head and tail for easier list manipulation
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
"""Remove node from linked list"""
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node
def _add_to_front(self, node):
"""Add node right after head (most recent position)"""
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _move_to_front(self, node):
"""Move existing node to front"""
self._remove(node)
self._add_to_front(node)
def get(self, key: int) -> int:
"""
Get value for key
If exists, mark as recently used (move to front)
Time: O(1)
"""
if key not in self.cache:
return -1
node = self.cache[key]
self._move_to_front(node)
return node.value
def put(self, key: int, value: int) -> None:
"""
Insert or update key-value pair
Mark as recently used
Evict LRU if at capacity
Time: O(1)
"""
if key in self.cache:
# Update existing
node = self.cache[key]
node.value = value
self._move_to_front(node)
else:
# Add new
if len(self.cache) >= self.capacity:
# Evict LRU (tail.prev)
lru_node = self.tail.prev
self._remove(lru_node)
del self.cache[lru_node.key]
# Add new node
new_node = Node(key, value)
self._add_to_front(new_node)
self.cache[key] = new_node
# Test
lru = LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
print(lru.get(1)) # Returns 1
lru.put(3, 3) # Evicts key 2
print(lru.get(2)) # Returns -1 (not found)
lru.put(4, 4) # Evicts key 1
print(lru.get(1)) # Returns -1 (not found)
print(lru.get(3)) # Returns 3
print(lru.get(4)) # Returns 4
Alternative: Using OrderedDict (Python)
from collections import OrderedDict
class LRUCache:
"""
Simpler implementation using OrderedDict
OrderedDict maintains insertion order and supports move_to_end()
Note: In interviews, implement from scratch with linked list
This is good for production code or quick prototyping
"""
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.cache:
return -1
# Move to end (most recent)
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
# Move to end
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
# Remove first item (LRU)
self.cache.popitem(last=False)
JavaScript Implementation
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map(); // Map maintains insertion order
}
get(key) {
if (!this.cache.has(key)) {
return -1;
}
// Move to end (most recent)
const value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
put(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key);
}
this.cache.set(key, value);
if (this.cache.size > this.capacity) {
// Remove first item (LRU)
const firstKey = this.cache.keys().next().value;
this.cache.delete(firstKey);
}
}
}
Complexity Analysis
- Time Complexity:
- get: O(1) - hash map lookup + list operations
- put: O(1) - hash map operations + list operations
- Space Complexity: O(capacity) - store up to capacity items
Follow-up Questions
Q: How would you implement LFU (Least Frequently Used) cache?
A: Use hash map + min heap or hash map + doubly linked lists organized by frequency.
Q: How to make it thread-safe?
A: Add locks/mutexes around get/put operations. Use read-write locks for better concurrency.
Q: How to persist to disk?
A: Implement write-through (sync) or write-back (async) to persistent storage.
Q: How to handle cache invalidation?
A: Add TTL (time-to-live), version numbers, or explicit invalidation API.
Related Problems
