AniUI Academy

LRU (Least Recently Used) Cache

hardData StructuresHigh freq+350 XPFrontend AlgoArena

A least-recently-used cache keeps a bounded set of items and, when it has to evict, drops whichever one was touched longest ago. It is the standard pattern for route caches, image thumbnails, API response caches — anywhere memory is finite but recent reads should stay warm.

Implement LRUCache(capacity) with .get(key) and .put(key, value). Both operations must mark the touched key as _most_ recently used, and once size exceeds capacity, the oldest entry has to go.

Aim for O(1) time on both methods. The clean trick: a JavaScript Map preserves insertion order, so delete-then-set moves a key to the back without any manual bookkeeping.

Arguments

capacitynumber
Constructor argument. The maximum number of entries the cache will hold before it starts evicting.
.get(key)(key: K) => V | -1
Returns the stored value for key and marks it as most recently used. Returns -1 when the key is absent.
.put(key, value)(key: K, value: V) => void
Inserts or updates the entry for key and marks it most recently used. When size would exceed capacity, the least recently used entry is evicted.

Returns

LRUCache — A cache instance exposing .get and .put. Both operations run in amortized O(1).

Examples

const lru = new LRUCache(2);
lru.put(1, "a");
lru.put(2, "b");
lru.get(1);        // "a" — key 1 is now most recent
lru.put(3, "c");   // over capacity: evicts key 2 (least recent)
lru.get(2);        // -1 — gone
lru.get(3);        // "c"

What it has to do

  • .get(key) returns value or -1 if absent, marking key as recently used.
  • .put(key, value) inserts or updates value. Evicts least recently used item when capacity is exceeded.

Notes

  • Updating an existing key with .put should also refresh its recency — not just overwrite the value in place.
  • A doubly-linked list plus a hash map is the textbook O(1) implementation; Map lets you skip the linked list entirely in JavaScript.
Asked atGoogleAmazonMicrosoftMeta
Try it yourself
Loading playground...
1 tests · +350 XP

Discussion

Sign in to post
Sign in to join the conversation.Sign in

No comments yet. Be the first to say something.