Key-Value Store with TTL

You've inherited a small in-memory key-value store, something like a stripped-down Redis or an application cache. Setting, getting, deleting, and counting keys already work and are already tested. You're asked to extend it so keys can expire, and then so the store stays within a fixed capacity.

The existing code accepts a ttl argument today and ignores it. Making that argument mean something, without breaking the behavior the current tests pin down, is the exercise.

What's in the codebase

• kv_store.py. The whole store. Entry holds a value and an optional absolute expires_at. KVStore has the working baseline: set(key, value, ttl=None), get(key), delete(key), __len__, and __contains__. The TODO markers show where the two parts go.
• tests/test_kv_baseline.py. Pins the behavior that already works. It passes now and has to stay passing.
• tests/test_kv_ttl.py. The expiry tests, failing until you implement.
• tests/test_kv_lru.py. The eviction tests, for the second part.
• tests/conftest.py. A FakeClock the tests advance by hand.

Two details in the existing code are worth reading before you extend it. Time is injected: the store calls self._clock() rather than reading the wall clock, which is what lets the tests control expiry without sleeping. And get raises KeyError on a missing key rather than returning None, so a stored None stays distinguishable from an absent key, the way dict behaves.

Your task

Make ttl do something. A key set with ttl=10 should be gone ten seconds later, and once it's expired, get and in should behave as if it were never there. A ttl of None still means the key never expires.

Route all timing through self._clock(). Calling time.monotonic() inside a method makes the behavior untestable, which the shipped tests will tell you immediately.

What to focus on

• Storing a deadline, not a duration. A key set with ttl=10 expires at a fixed moment. Storing the ten and comparing it against something later invites arithmetic that drifts.
• The boundary you can't infer. At exactly expires_at, is the key alive or gone? Neither answer is wrong, and the interviewer wants to hear you pick one on purpose.
• What len() counts. If a key expired ten minutes ago and nothing has touched it since, it's still sitting in the dictionary. Counting only live keys is more correct and costs a scan. Counting the raw dictionary is constant time and over-reports. The shipped test encodes one choice, and arguing for the other is fine if you can defend it.

The eviction follow-up

The second part bounds the store: given a capacity of N and a full store, something has to go when a new key arrives. Least-recently-used is the expected policy, and both get and set count as a use.

Two details separate a working implementation from a solid one. Overwriting an existing key is not a new insertion, so it must not evict anything. And when the store is full, an already-expired key should be reclaimed before a live one gets evicted, since dropping an expired key costs nothing.

If your get and set are still constant time after eviction lands, you've done it right. collections.OrderedDict gets you there, and so does a dictionary paired with a doubly linked list.

Using AI on this problem

An LRU cache is one of the most reproduced snippets in any model's training data, so an agent will hand you a correct one instantly and you'll learn nothing. Use it for the parts that are actually specific to this store: how the expiry check interacts with eviction, and whether a generated __len__ matches the semantics the baseline tests expect.

If you generate the eviction code, trace an overwrite through it by hand before you run the tests.

Leveling signals