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.
Audio N/AQuick 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)