Data structures and patterns · Question 42 of 50
Design an LRU cache.
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]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.