LRU Cache

Background

The textbook Least Recently Used cache -- a common phone-screen and onsite question:

• LRUCache(capacity) creates a cache with a positive maximum size capacity.
• get(key) returns the value stored for key, or -1 if it is absent.
• put(key, value) updates the value if key is present; otherwise inserts the pair. If the insert pushes the number of keys past capacity, evict the key that was used least recently.
• get and put must each run in O(1) average time.

Input:
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output:
[null, null, null, 1, null, -1, null, -1, 3, 4]

With capacity 2: after put(1,1) and put(2,2), get(1) returns 1; put(3,3) evicts key 2 (least recently used); get(2) returns -1; put(4,4) evicts key 1; then get(1) returns -1, get(3) returns 3 and get(4) returns 4.

Constraints from the original question: 1 <= capacity <= 3000, 0 <= key <= 10^4, 0 <= value <= 10^5, at most 2 * 10^5 calls to get and put.

This workspace is not the from-scratch version. The recency tracker is its own module, a TTL extension sits on top in a second class, and the performance gate asks for the doubly linked list the textbook already promised you.

What is in the workspace

src/recency.py          RecencyOrder -- which key was used least recently
src/cache.py            LRUCache     -- the LRU cache, capacity-bounded
src/ttl.py              TTLCache     -- you fill in put / purge_expired
main.py                 runnable demo: the example above on a capacity-2 cache, then the TTL cache on a fake clock
tests/test_recency.py   Phase 1
tests/test_cache.py     Phase 1
tests/test_ttl.py       Phase 2
tests/test_performance.py  Phase 3

The tests put src/ on sys.path themselves, so you can run them from anywhere in the repo.

Phase 1 -- Fix the defects

There are exactly 3 defects in src/recency.py and src/cache.py. The docstrings state the intended behavior; the code does not always match them. Read the failing tests, then fix the code.

python -m unittest discover -s tests -p "test_recency.py" -v
python -m unittest discover -s tests -p "test_cache.py" -v

Phase 2 -- Implement the TTL cache

Implement put and purge_expired in src/ttl.py per the docstrings. get, __len__, __contains__ and keys() are already wired; they call purge_expired() once it exists, so the cache reflects live entries on the way out and on explicit sweeps.

The clock is injected: TTLCache(capacity=2, ttl_s=10.0, now=clock) lets the test advance a fake clock and step past deadlines without sleeping.

python -m unittest discover -s tests -p "test_ttl.py" -v

Phase 3 -- Make the recency tracker O(1)

Your Phase 1 code is correct and too slow for the scale tests. The recency order walks the list from the front on every touch -- a linear scan plus a linear remove plus a re-insert, every single call. Cut it.

python -m unittest discover -s tests -p "test_performance.py" -v

Running everything

python -m unittest discover -s tests -v
python main.py

Python 3.9+, standard library only. No third-party packages, no network.

What is evaluated

• All four suites pass with the tests unedited.
• get and put are O(1) average: a hash map for lookup plus a doubly linked list for recency.
• The TTL cache honours both capacity and deadlines using the injected clock.

Interview notes

Candidates report being asked to explain the design choice (a hash map paired with a doubly linked list) and to walk through edge cases line by line while coding, often on a whiteboard alongside behavioral questions in the same round.