What is an LRU cache and how can you implement it in O(1)?

Answer

LRU (Least Recently Used) evicts the item that hasn’t been used for the longest time. A common O(1) design is: HashMap for key→node lookup + doubly linked list to move items to the front on access and evict from the tail.

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))