LRU Cache

PracticalmediumPremium

45:00

Desktop only

Coding Challenges are optimized for Desktop

Come back on a wider screen - the live editor needs room to breathe. You can still read the problem brief above.

Problem

CDN edges, database page caches, and session stores all share one constraint: memory is bounded and every miss costs real latency. When the cache is full, something must go - and "least recently used" is the policy that production systems reach for first. You will build that cache in stages: correctness first, then the eviction policy, then the O(1) requirement that separates the memorizers from the engineers, then recency queries, and finally time-based expiry.

The cache maps string keys to integer values. capacity is fixed at construction. On a full cache, put evicts the least recently used entry. Both get and put count as a use.

Level 1 - Core operations

get(key) returns the stored value, or None (Python) / null (JS/TS) when the key is absent. put(key, value) stores or overwrites. Capacity is unbounded at this level.

Example:

cache = LRUCache()
cache.put("session", 42)
cache.get("session")   -> 42
cache.get("missing")   -> None
cache.put("session", 7)
cache.get("session")   -> 7    # overwritten

Level 2 - Bounded capacity with eviction

The constructor takes capacity. When put would exceed capacity, evict the least recently used key first. Both get and put refresh recency.

Example:

cache = LRUCache(capacity=2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a")         -> 1   # "a" is now most recently used
cache.put("c", 3)             # full; evicts "b", not "a"
cache.get("b")         -> None
cache.get("a")         -> 1

Level 3 - Every operation in O(1) average time

Same contract as Level 2, but get and put must both run in O(1) average time. Scanning a list for the least recently used entry is now a failing answer.

Example:

cache = LRUCache(capacity=3)
for i in range(1000):
    cache.put(f"key{i}", i)      # 1000 evictions, no per-put scan
cache.get("key999")       -> 999
cache.get("key0")         -> None   # evicted long ago

Level 4 - Recency queries

def get_k_recent(self, k: int) -> list[str]: ...

Return the k most recently used keys, most recent first, in O(k) time. k larger than the cache size returns all keys. A get or put refreshes recency; get_k_recent itself must not.

Example:

cache = LRUCache(capacity=5)
cache.put("a", 1); cache.put("b", 2); cache.put("c", 3)
cache.get("a")                    # "a" is most recent now
cache.get_k_recent(2)      -> ["a", "c"]
cache.get_k_recent(10)    -> ["a", "c", "b"]

Level 5 - TTL expiry

The constructor gains an optional ttl (seconds). An entry expires ttl seconds after its last put or get. An expired key behaves exactly like a missing key: get returns None/null, it is not evicted by capacity pressure until touched, and get_k_recent skips it. When ttl is not provided, entries never expire.

The cache takes a clock callable at construction (Python) / a now function (JS/TS), defaulting to real time - tests inject a fake clock. A get on an expired key must evict it (lazy expiry).

Example:

clock = FakeClock(100)
cache = LRUCache(capacity=2, ttl=30, clock=clock)
cache.put("token", 5)          # expires at t=130
clock.advance(20)
cache.get("token")      -> 5   # t=120, still fresh; refresh extends expiry to 150
clock.advance(40)
cache.get("token")      -> None # t=160 > 150 - expired and evicted
cache.get_k_recent(5)   -> []

Patterns used

Foundations primers this challenge draws on.

Hash Maps

Loading editor...

The live editor for this challenge unlocks with Premium.

Browse free problems

0/0 passed