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'll use it to track recency
        # Each entry is (value, timestamp)
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return None
        
        value, timestamp = self.cache[key]
        
        # Check if expired
        if self.now() - timestamp >= self.ttl:
            # Remove expired entry
            del self.cache[key]
            return None
        
        # Move to end to mark as most recently used
        self.cache.move_to_end(key)
        return value

    def put(self, key, value):
        current_time = self.now()
        
        # If key already exists, remove it first (to handle recency and potential expiration)
        if key in self.cache:
            del self.cache[key]
        elif len(self.cache) >= self.capacity:
            # Evict the least recently used entry (first item in OrderedDict)
            # But first check if there are any expired entries we should evict instead
            # Actually, per spec, we only evict LRU live entry when inserting new key
            # So we need to find the first (oldest) entry that is still live
            
            # Check if cache is empty after eviction
            while self.cache:
                # Get the least recently used key (first item)
                lru_key = next(iter(self.cache))
                _, timestamp = self.cache[lru_key]
                
                # If this entry is expired, remove it and continue checking
                if current_time - timestamp >= self.ttl:
                    del self.cache[lru_key]
                else:
                    # Found the first live entry, evict it
                    del self.cache[lru_key]
                    break
        
        # Insert new entry with current timestamp
        self.cache[key] = (value, current_time)

    def __len__(self) -> int:
        count = 0
        current_time = self.now()
        
        # Count only live entries
        for key in list(self.cache.keys()):
            _, timestamp = self.cache[key]
            if current_time - timestamp < self.ttl:
                count += 1
            else:
                # Expired entry, remove it
                del self.cache[key]
        
        return count
```