Add Expiry to an LRU Cache
The pricing service caches prices in an LRU cache, and product wants entries to go stale after a TTL. The README has the rules. Build it with the assistant: accept, edit, or reject each suggestion, and keep the tests green.
lru.py1 of 3
Files
lru.py
Python · Editableimport time
from collections import OrderedDict
class LRUCache:
"""Least recently used cache. Entries expire ttl_s seconds after they are written."""
def __init__(self, capacity, ttl_s, clock=time.monotonic):
if capacity < 1:
raise ValueError("capacity must be at least 1")
self.capacity = capacity
self.ttl_s = ttl_s
self.clock = clock
self.data = OrderedDict() # key -> (value, expires_at)
def get(self, key):
if key not in self.data:
return None
value, expires_at = self.data[key]
self.data.move_to_end(key)
return value
def put(self, key, value):
self.data[key] = (value, self.clock() + self.ttl_s)
self.data.move_to_end(key)
if len(self.data) > self.capacity:
self.data.popitem(last=False)
def __len__(self):
return len(self.data)
import pytest
from lru import LRUCache
class FakeClock:
def __init__(self):
self.now = 0.0
def __call__(self):
return self.now
def make(capacity=2, ttl_s=10):
clock = FakeClock()
return LRUCache(capacity, ttl_s, clock=clock), clock
def test_get_returns_value_before_ttl():
cache, clock = make()
cache.put("a", 1)
clock.now = 9.9
assert cache.get("a") == 1
def test_entry_is_gone_at_ttl():
cache, clock = make()
cache.put("a", 1)
clock.now = 10
assert cache.get("a") is None
def test_get_does_not_extend_expiry():
cache, clock = make()
cache.put("a", 1)
clock.now = 9
cache.get("a")
clock.now = 11
assert cache.get("a") is None
def test_get_refreshes_recency():
cache, _ = make()
cache.put("a", 1)
cache.put("b", 2)
cache.get("a")
cache.put("c", 3)
assert cache.get("b") is None
assert cache.get("a") == 1
def test_expired_entries_make_room_first():
cache, clock = make()
cache.put("a", 1) # expires at 10
clock.now = 5
cache.put("b", 2) # expires at 15
cache.get("a") # b is now least recently used
clock.now = 11 # a has expired, b is live
cache.put("c", 3)
assert cache.get("b") == 2
assert cache.get("c") == 3
def test_len_counts_live_entries():
cache, clock = make()
cache.put("a", 1)
clock.now = 5
cache.put("b", 2)
clock.now = 12
assert len(cache) == 1
def test_rejects_non_positive_ttl():
with pytest.raises(ValueError):
LRUCache(2, 0)
# Price Cache
The pricing service caches prices in LRUCache (lru.py). Prices change, so product wants cached entries to go stale.
## What to Build
- An entry written at time t is gone from t + ttl_s on.
- Reading an entry refreshes its recency. It does not extend its expiry.
- When the cache is full, expired entries make room before any live entry is evicted.
- len(cache) counts live entries only.
- ttl_s must be positive.
The cache is used from one thread. The tests in test_lru.py use a fake clock.
Test Output
No runs yet.