Co to jest cache LRU i jak zaimplementować go w O(1)?

Odpowiedź

LRU (Least Recently Used) usuwa element, którego najdłużej nie używano. Typowa implementacja w O(1): HashMap do lookupu key→węzeł + lista dwukierunkowa, aby po użyciu przesuwać element na początek i usuwać z końca.

type Node = { key: string; prev?: Node; next?: Node }

// idea:
// map: key -> node
// list: head <-> ... <-> tail
// get(key): move node to head (O(1))
// put(key): insert/move to head; if over capacity, evict tail (O(1))