LRU cache in O(1)

Medium30 minFree, no account

Both operations have to be constant time, which rules out the first thing everyone reaches for.

The question

Implement an LRU cache with get(key) and put(key, value), both O(1), evicting the least recently used entry at capacity.

A get counts as a use.

const c = new LRUCache(2);
c.put("a", 1); c.put("b", 2);
c.get("a");            // 1: "a" is now the most recent
c.put("c", 3);         // evicts "b", not "a"
c.get("b");            // undefined

30:00Commit to an answer before you open the solution. Reading it first teaches you to recognise good answers, which is not the skill being tested.

Stuck?

0 of 3 hints taken

The worked solution

written by a person · not a grade

Score yourself

0 of 5 marked

Both operations genuinely O(1)35
A get counts as a use20
A put on an existing key refreshes recency20
Eviction correct at the boundary15
Explained the structure choice rather than reciting it10

We run no AI here and nothing on this page grades you. The score is yours, and the useful number is the one you get on the same problem a month from now, cold.

kept in this browser only