Academy
hardJS ES6+#142

LRU cache with Map

Prompt

Implement class LRUCache(capacity):

  1. get(key) → value, or -1 if missing; a hit makes the key most-recently-used
  2. put(key, value) → inserts/updates; over capacity evicts the least-recently-used entry
  3. Both operations O(1)

Hint: a JS Map remembers insertion order — that's the whole trick.

Solution

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.map = new Map()
  }
  get(key) {
    if (!this.map.has(key)) return -1
    // refresh recency: delete + re-insert moves the key to the "newest" end
    const value = this.map.get(key)
    this.map.delete(key)
    this.map.set(key, value)
    return value
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key)
    this.map.set(key, value)
    if (this.map.size > this.capacity) {
      // Map iterates in insertion order — first key is the LRU
      const oldest = this.map.keys().next().value
      this.map.delete(oldest)
    }
  }
}
Mentor's take

LRU is the interview's favorite cache because the naive answers are all O(n): an array you re-sort, timestamps you scan for the minimum. The senior insight is that JS Map preserves insertion order and supports O(1) delete — so "recency order" and "insertion order" become the same thing if you re-insert on every touch.

Why this shape:

  • delete + set = move to back. That two-line idiom is the entire recency bookkeeping. In a language without ordered maps you'd hand-roll a doubly-linked list over a hash map — worth saying in the interview, because it shows you know what Map is doing for you.
  • Eviction reads the first key via map.keys().next().value — the iterator's first element is always the stalest entry. No scan.
  • put on an existing key must delete first, or the update keeps the old position and a "fresh" key gets evicted as if it were stale.

Where this lands in a React Native app: memory is the constrained resource, and unbounded caches are slow-motion leaks. Image caches, memoized API responses, even react-query's garbage collection are LRU-shaped decisions. An unbounded Map used as a memo cache is the same bug as an uncancelled Animated.loop — it just OOMs slower.

Red flag: storing a lastUsed timestamp per entry and scanning for the minimum on eviction — it works, but it's O(n) eviction and signals you didn't know the data structure. Name the linked-list-over-hashmap design even if you use Map.

Say it: "Map gives me ordered keys with O(1) delete, so delete-and-reinsert is my recency update and the first key is always the eviction victim — same design as a linked hash map, one structure instead of two."