Vibe Engines Learn
CODING CHALLENGE · N°13

LRU Cache

Medium SystemsCachingData Structures

The eviction policy behind every cache with a size limit: when you run out of room, throw out whatever was used least recently. The trick is doing get and put in O(1) — an ordered hash map (Python dict / JS Map) gives you exactly that.

The problem

Implement a fixed-capacity LRU (least-recently-used) cache as a driver: lru_cache(capacity, ops) replays a list of operations and returns the results of the get calls (in order). Each op is a list: ["get", key] returns the stored value or -1 if absent, and counts as a use (the key becomes most-recently-used). ["put", key, value] inserts or updates the key (also most-recently-used); if that pushes the cache over capacity, evict the least-recently-used key. Only get results go into the returned list.

EXAMPLE 1
Input capacity=2, ops=[["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["put",4,4],["get",1],["get",3],["get",4]]
Output [1, -1, -1, 3, 4]
put(3) evicts key 2; put(4) evicts key 1 — the classic trace
EXAMPLE 2
Input capacity=1, ops=[["put",1,1],["put",2,2],["get",1],["get",2]]
Output [-1, 2]
capacity 1 → each put evicts the previous key
EXAMPLE 3
Input capacity=2, ops=[["get",5]]
Output [-1]
a miss returns -1
CONSTRAINTS
  • Both get and put mark the key as most-recently-used.
  • On overflow, evict the least-recently-used key (the one untouched the longest).
  • A Python dict (or JS Map) preserves insertion order — pop and re-insert a key to move it to the most-recently-used end; the first key is the LRU.
  • Return only the values produced by get operations, in order.
SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement lru_cache(capacity, ops). Replay the ops against an LRU cache of the given capacity and return the list of results from the get calls.

HINTS — 4 IDEAS
  1. Keep a dict/Map from key → value; its iteration order is your recency order (oldest first).
  2. On get: if present, pop the key and re-insert it (now newest) before returning its value; else return -1.
  3. On put: if the key exists, pop it first; set key → value (newest); then if size > capacity, delete the first (oldest) key.
  4. The oldest key is next(iter(cache)) in Python / cache.keys().next().value in JS.
CPython · WebAssembly

Explore the topic

See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.

Caching & Performance