Engineering practice · 35 MIN

Project · A bounded LRU cache

Keep recency and capacity as explicit invariants.

A least recently used cache evicts the entry that has gone longest without a read or update. Map preserves insertion order, so remove and reinsert a key to mark it recent. Update an existing entry before checking capacity. This local cache models one process; a shared cache additionally needs consistency, expiry and stampede controls. Returning -1 for a miss is this exercise’s contract, not a universal API design.

Treat the function as a small service: define a contract, maintain an invariant, and test the boundaries.

Read the example

const cache = new Map([["a", 1], ["b", 2]]);
cache.delete("a"); cache.set("a", 1);
console.log([...cache.keys()].join(","));

Check the expected output

b,a

Your challenge

Input is {capacity: nonnegative integer, operations: arrays of ["put", key, value] or ["get", key]}. Return a list of get results, using -1 for misses. Keys are strings; values are integers. Capacity zero retains nothing.

Solution cost: Expected O(m) for m operations with hash-based Map implementations; ECMAScript guarantees average sublinear access, not strict O(1). time · O(c + r), c cached entries and r returned reads. space

Common trap

Checking if (cache.get(key)) treats a stored zero as a miss. Failing to refresh reads produces FIFO eviction.

Open interactive exercise →See the syllabus