py-04-lru-ttl-cache

# 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
```

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

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```python
import time
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int, ttl: float, now=time.monotonic):
        self.capacity = capacity
        self.ttl = ttl
        self.now = now
        # OrderedDict maintains insertion order. We will use it as a doubly linked list
        # where the most recently used item is at the end (right) and the least recently
        # used is at the beginning (left).
        self.cache: OrderedDict = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return None
        
        # Check if expired
        entry_time, value = self.cache[key]
        if self.now() - entry_time >= self.ttl:
            # Expired: remove and return None
            del self.cache[key]
            return None
        
        # Not expired: move to end (most recently used)
        self.cache.move_to_end(key)
        return value

    def put(self, key, value):
        if key in self.cache:
            # Update existing key: reset age, move to end
            self.cache.move_to_end(key)
            self.cache[key] = (self.now(), value)
        else:
            # Insert new key
            self.cache[key] = (self.now(), value)
            
            # If capacity exceeded, evict least recently used (leftmost)
            if len(self.cache) > self.capacity:
                self.cache.popitem(last=False)

    def __len__(self) -> int:
        # Count only live (non-expired) entries
        current_time = self.now()
        live_count = 0
        # Iterate from left (LRU) to right (MRU)
        for key in list(self.cache.keys()):
            entry_time, _ = self.cache[key]
            if current_time - entry_time < self.ttl:
                live_count += 1
            else:
                # Expired: remove lazily
                del self.cache[key]
        return live_count
```