Data structures and patterns · Question 42 of 50

Design an LRU cache.

What they're checking

Combining two structures to get O(1).

The answer

An LRU (least recently used) cache holds at most N items and, when full, throws out the one used longest ago. For O(1) get and put you need two structures: a hash map from key to node, for the lookup, and a doubly linked list in order of use, for moving a node to the front and dropping the back.

get: find the node, move it to the front, return it. put: update or insert at the front; if over capacity, remove the back node and delete its key from the map. In JavaScript a Map keeps insertion order, so deleting and re-setting a key makes it the newest.

class LRU {
  constructor(cap) { this.cap = cap; this.map = new Map() }
  get(k) {
    if (!this.map.has(k)) return -1
    const v = this.map.get(k)
    this.map.delete(k); this.map.set(k, v)   // now the newest
    return v
  }
  put(k, v) {
    this.map.delete(k); this.map.set(k, v)
    if (this.map.size > this.cap) this.map.delete(this.map.keys().next().value)
  }
}

The picture

map: { a → •, b → •, c → • }
list, newest to oldest:  [c] ⇄ [b] ⇄ [a]
get(a): move a to the front     → [a] [c] [b]
put(d) when full: drop the back → [d] [a] [c]
The follow-up they'll ask

How would you make it safe across threads?

Show the answer

A lock around get and put, or split it into shards with a lock each to cut contention.

Your progress stays on this device.