LRU Cache Design
Design an LRU cache with O(1) get and put. Evict the least recently used key when capacity is exceeded.
Answers use simple, clear English.
Quick interview answer
Hash map from key → node plus a doubly linked list ordered by recency. get/put move nodes to the front; eviction removes from the tail. In Python, OrderedDict / dict move-to-end approximates this.
Detailed answer
Hash map from key → node plus a doubly linked list ordered by recency. get/put move nodes to the front; eviction removes from the tail. In Python, OrderedDict / dict move-to-end approximates this. Interviewers want the list+map structure explained even if language sugar exists.
Full explanation
Interviewers want the list+map structure explained even if language sugar exists.
Real example & use case
API gateway caching auth tokens with bounded memory and freshness by access.
Pros & cons
Pros: true O(1) ops. Cons: pointer-heavy implementation; concurrency needs locking.
Code example
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.data = OrderedDict()
def get(self, key: int) -> int:
if key not in self.data:
return -1
self.data.move_to_end(key)
return self.data[key]
def put(self, key: int, value: int) -> None:
if key in self.data:
self.data.move_to_end(key)
self.data[key] = value
if len(self.data) > self.cap:
self.data.popitem(last=False)Practice code · python (view only · no execution)
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.data = OrderedDict()
def get(self, key: int) -> int:
if key not in self.data:
return -1
self.data.move_to_end(key)
return self.data[key]
def put(self, key: int, value: int) -> None:
if key in self.data:
self.data.move_to_end(key)
self.data[key] = value
if len(self.data) > self.cap:
self.data.popitem(last=False)