Implement a bounded least-recently-used cache
ExpertSenior · 5–8 yearsData structures
Python 3.10+; standard library only. GIL discussion refers to conventional CPython builds, not optional free-threaded builds.
Problem statement
Implement get and put with eviction of the least recently used key when capacity is exceeded.
Keep a bounded set of frequently accessed lookup results.
Input: Nonnegative capacity and a sequence of key/value operations; values exclude None.
Output: get returns value or None for a miss.
- Values are not None.
- Single-threaded; no TTL.
- Capacity zero must retain no entries.
Sample 1
Input: capacity2: put(a,1),put(b,2),get(a),put(c,3),get(b) Output: None
b is least recent and evicted.
Sample 2
Input: capacity0:put(a,1),get(a) Output: None
No capacity to store entries.
Brute-force solution
Keep an ordered list and linearly search/move keys on every operation.
O(1) expected per get/put.
from collections import OrderedDict
class LRU:
def __init__(self,capacity):
if capacity<0: raise ValueError("negative capacity")
self.capacity=capacity;self.data=OrderedDict()
def get(self,key):
if key not in self.data: return None
self.data.move_to_end(key);return self.data[key]
def put(self,key,value):
self.data[key]=value;self.data.move_to_end(key)
if len(self.data)>self.capacity:self.data.popitem(last=False)
c=LRU(2);c.put("a",1);c.put("b",2);c.get("a");c.put("c",3);print(c.get("b"))
Optimized solution
OrderedDict combines a hash lookup with a linked order, enabling constant-time expected promotion and eviction.
- Move hits to the end.
- Move inserted/updated keys to the end.
- Evict from the beginning when over capacity.
from collections import OrderedDict
class LRU:
def __init__(self,capacity):
if capacity<0: raise ValueError("negative capacity")
self.capacity=capacity;self.data=OrderedDict()
def get(self,key):
if key not in self.data: return None
self.data.move_to_end(key);return self.data[key]
def put(self,key,value):
self.data[key]=value;self.data.move_to_end(key)
if len(self.data)>self.capacity:self.data.popitem(last=False)
c=LRU(2);c.put("a",1);c.put("b",2);c.get("a");c.put("c",3);print(c.get("b"))
Complexity analysis
Time: O(1) expected per get/put.
Auxiliary space: O(capacity)
Test cases
- Zero capacity.
- Update existing key.
- Missing key must not change order.
c=LRU(2)
c.put("a",1);c.put("b",2)
assert c.get("a")==1
c.put("c",3)
assert c.get("b") is None
c.put("a",4)
assert c.get("a")==4
z=LRU(0);z.put("a",1);assert z.get("a") is NoneCommon mistakes
- Not promoting a successful get.
- Evicting an entry unnecessarily on overwrite.
Key takeaways
- Maintain an explicit recency invariant.
- Bound memory.
- Document miss and value semantics.
Follow-up challenges
- How would you add TTL?
- How would you synchronize concurrent calls?