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
        self._cache = {}  # key -> (value, timestamp)
        self._order = OrderedDict()  # key -> None, maintains LRU order (MRU at end)

    def _is_expired(self, key):
        if key not in self._cache:
            return True
        timestamp = self._cache[key][1]
        return self.now() - timestamp >= self.ttl

    def _evict_lru(self):
        if not self._order:
            return
        lru_key, _ = self._order.popitem(last=False)
        if lru_key in self._cache:
            del self._cache[lru_key]

    def get(self, key):
        if key not in self._cache:
            return None
        if self._is_expired(key):
            del self._cache[key]
            if key in self._order:
                del self._order[key]
            return None
        # Move to MRU position (end of OrderedDict)
        self._order.move_to_end(key)
        return self._cache[key][0]

    def put(self, key, value):
        now = self.now()
        if key in self._cache:
            # Update existing entry
            self._cache[key] = (value, now)
            self._order.move_to_end(key)
        else:
            # New entry
            self._cache[key] = (value, now)
            self._order[key] = None
            # Evict if over capacity
            while len(self._order) > self.capacity:
                self._evict_lru()

    def __len__(self) -> int:
        return sum(1 for key in self._order if not self._is_expired(key))
```

The user wants me to implement an LRU Cache with TTL (Time To Live) functionality.

Key requirements:
1. Bounded cache with LRU eviction
2. TTL-based expiration
3. `get(key)` returns value or None if expired/absent
4. `get(key)` refreshes recency but NOT the age/timestamp
5. `put(key, value)` inserts/updates, marks as MRU, resets age to current time
6. If capacity exceeded, evict LRU live entry
7. Expired entries don't count toward `__len__`
8. Expired entries can be purged lazily
9. Injectable `now()` function for testing

Let me think about the data structures:

For LRU, I need to track access order. A doubly-linked list is common for this.
For TTL, I need to track when each entry was inserted/updated.

I'll use:
- A dictionary to map keys to nodes in the linked list
- A doubly-linked list to maintain LRU order
- A dictionary to track timestamps for each key

When `get(key)` is called:
1. Check if key exists and is not expired
2. If expired, remove it and return None
3. If live, move it to the front (MRU position)
4. Return the value

When `put(key, value)` is called:
1. Check if key exists
2. If exists, update value and move to front (reset timestamp)
3. If new, add to front with current timestamp
4. If capacity exceeded, evict LRU entry (check if expired first)

For `__len__()`:
1. Count only live (non-expired) entries

Let me implement this:

```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
        self.cache = {}  # key -> (value, timestamp)
        self.order = []  # list of keys in LRU order (front is MRU)
    
    def _is_expired(self, key):
        if key not in self.cache:
            return True
        timestamp = self.cache[key][1]
        return self.now() - timestamp >= self.ttl
    
    def _evict_lru(self):
        if not self.order:
            return
        lru_key = self.order[-1]
        if not self._is_expired(lru_key):
            del self.cache[lru_key]
            self.order.pop()
    
    def get(self, key):
        if key not in self.cache:
            return None
        if self._is_expired(key):
            del self.cache[key]
            if key in self.order:
                self.order.remove(key)
            return None
        # Move to MRU position
        self.order.remove(key)
        self.order.insert(0, key)
        return self.cache[key][0]
    
    def put(self, key, value):
        if key in self.cache:
            # Update existing entry
            self.cache[key] = (value, self.now())
            self.order.remove(key)
            self.order.insert(0, key)
        else:
            # New entry
            self.cache[key] = (value, self.now())
            self.order.insert(0, key)
            # Evict if over capacity
            while len(self.order) > self.capacity:
                self._evict_lru()
    
    def __len__(self):
        return sum(1 for key in self.order if not self._is_expired(key))
```

I'm reconsidering the implementation to ensure it meets all the requirements precisely. The current approach looks promising, but I need to verify the eviction and expiration logic carefully.

The key challenge is managing the LRU order while handling TTL expiration. I'll need to ensure that expired entries are properly removed and don't count towards the cache size.

My implementation uses a dictionary for quick key lookups and a list to maintain LRU order. The `_is_expired` method checks if an entry has exceeded its time-to-live, and the `_evict_lru` method removes the least recently used entry when capacity is reached.

The `get` method handles both expiration and recency updates, while `put` manages insertion and potential eviction. The `__len__` method counts only live entries, ensuring accurate cache size tracking.

I'll continue refining the implementation to handle edge cases and ensure robust cache management.