py-04-lru-ttl-cache
0.000
Challenge · difficulty 4/5
# LRU Cache with TTL
Implement a file **`solution.py`** containing a class:
```python
class LRUCache:
def __init__(self, capacity: int, ttl: float, now=time.monotonic):
...
def get(self, key):
...
def put(self, key, value):
...
def __len__(self) -> int:
...
```
A bounded cache that evicts by **least-recently-used** order and also **expires**
entries by age.
Behavior:
- `capacity` is the maximum number of live entries. `ttl` is the maximum age, in
seconds, an entry may live before it is considered expired.
- `get(key)` returns the stored value, or `None` if the key is absent or expired.
A successful `get` counts as a **use** (it refreshes recency, but **not** the
entry's age / expiry time).
- `put(key, value)` inserts or updates an entry, marking it most-recently-used and
**resetting its age** (its timestamp becomes "now"). If inserting a new key
would exceed `capacity`, evict the least-recently-used live entry first.
- An **expired** entry must never be returned by `get` and must not count toward
`__len__`. Expired entries may be purged lazily.
- `__len__` returns the number of **live (non-expired)** entries.
## Injectable clock
The constructor takes a `now` callable (defaulting to `time.monotonic`) that
returns the current time as a float. **All time decisions must use `now()`**, not
a hardcoded clock. This lets tests pass a controllable clock for deterministic
behavior. An entry inserted at time `t0` is expired once `now() - t0 >= ttl`
(i.e. an age strictly less than `ttl` is still live).
Example:
```python
clock = [0.0]
cache = LRUCache(capacity=2, ttl=10.0, now=lambda: clock[0])
cache.put("a", 1)
clock[0] = 5.0
assert cache.get("a") == 1 # age 5 < ttl 10 -> live
clock[0] = 10.0
assert cache.get("a") is None # age 10 >= ttl 10 -> expired
```
tests/test_lru_ttl_cache.py
from solution import LRUCache
def make(capacity=2, ttl=10.0):
clock = [0.0]
cache = LRUCache(capacity=capacity, ttl=ttl, now=lambda: clock[0])
return cache, clock
def test_basic_get_put():
cache, _ = make()
cache.put("a", 1)
cache.put("b", 2)
assert cache.get("a") == 1
assert cache.get("b") == 2
assert cache.get("missing") is None
def test_lru_eviction_on_capacity():
cache, _ = make(capacity=2)
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3) # exceeds capacity -> evict LRU ("a")
assert cache.get("a") is None
assert cache.get("b") == 2
assert cache.get("c") == 3
assert len(cache) == 2
def test_get_refreshes_recency():
cache, _ = make(capacity=2)
cache.put("a", 1)
cache.put("b", 2)
assert cache.get("a") == 1 # "a" now most-recently-used
cache.put("c", 3) # should evict "b", not "a"
assert cache.get("a") == 1
assert cache.get("b") is None
assert cache.get("c") == 3
def test_ttl_expiry_boundary():
cache, clock = make(ttl=10.0)
cache.put("a", 1)
clock[0] = 9.999
assert cache.get("a") == 1 # age < ttl -> live
clock[0] = 10.0
assert cache.get("a") is None # age == ttl -> expired
def test_get_does_not_reset_age():
cache, clock = make(ttl=10.0)
cache.put("a", 1)
clock[0] = 5.0
assert cache.get("a") == 1 # use does not refresh age
clock[0] = 10.0
assert cache.get("a") is None # still expires at original t0 + ttl
def test_put_resets_age():
cache, clock = make(ttl=10.0)
cache.put("a", 1)
clock[0] = 8.0
cache.put("a", 99) # re-put resets age and value
clock[0] = 15.0 # 7s after re-put -> still live
assert cache.get("a") == 99
def test_len_excludes_expired():
cache, clock = make(capacity=5, ttl=10.0)
cache.put("a", 1)
cache.put("b", 2)
assert len(cache) == 2
clock[0] = 11.0
assert len(cache) == 0
def test_expired_entry_does_not_count_against_capacity():
cache, clock = make(capacity=2, ttl=10.0)
cache.put("a", 1)
cache.put("b", 2)
clock[0] = 11.0 # both expired
cache.put("c", 3)
cache.put("d", 4) # should fit; expired ones purged
assert cache.get("c") == 3
assert cache.get("d") == 4
assert cache.get("a") is None
assert len(cache) == 2
Proposed solution
```python
cache = LRUCache(capacity=2, ttl=10.0, now=lambda: clock[0])
cache.put("a", 1)
cache[0] = 5.0
assert cache.get("a") == 1 # age 5 < ttl 10 -> expired
cache[0] = 10.0
assert cache.get("a") is None # age 10 >= ttl 10 -> expired
cache[0] = 0 0
assert cache[0] = 0 0
```Test output (stdout)
==================================== ERRORS ====================================
____________________ ERROR collecting test_lru_ttl_cache.py ____________________
/home/psc/miniconda3/lib/python3.12/site-packages/_pytest/python.py:508: in importtestmodule
mod = import_path(
/home/psc/miniconda3/lib/python3.12/site-packages/_pytest/pathlib.py:596: in import_path
importlib.import_module(module_name)
/home/psc/miniconda3/lib/python3.12/importlib/__init__.py:90: in import_module
return _bootstrap._gcd_import(name[level:], package, level)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
<frozen importlib._bootstrap>:1387: in _gcd_import
???
<frozen importlib._bootstrap>:1360: in _find_and_load
???
<frozen importlib._bootstrap>:1331: in _find_and_load_unlocked
???
<frozen importlib._bootstrap>:935: in _load_unlocked
???
/home/psc/miniconda3/lib/python3.12/site-packages/_pytest/assertion/rewrite.py:188: in exec_module
exec(co, module.__dict__)
test_lru_ttl_cache.py:1: in <module>
from solution import LRUCache
E File "/tmp/llmlab-py-04-lru-ttl-cache-_qx9fic9/solution.py", line 7
E cache[0] = 0 0
E ^
E SyntaxError: invalid syntax
=========================== short test summary info ============================
ERROR test_lru_ttl_cache.py
!!!!!!!!!!!!!!!!!!!! Interrupted: 1 error during collection !!!!!!!!!!!!!!!!!!!!
1 error in 0.05s