Design a cache with get and put in O(1). Evict least recently used when full.
Input: capacity=2, put(1,1), put(2,2), get(1)=1, put(3,3), get(2)=-1, put(4,4), get(1)=-1, get(3)=3, get(4)=4
GetO(1)hash lookup
PutO(1)hash + DLL add/remove
SpaceO(capacity)
Step0/10
head ↔ tail (empty)
Ready
Press Play or Step. Hash map + doubly linked list. Head = MRU, tail = LRU. Move to head on access; evict from tail when full.
⌨ Type It
Practice until you don't need to look. The green highlights are the nuances to burn into memory.
# get: if in map, move node to head, return val. Else -1.
# put: if exists, update val and move to head. Else: add at head. If over cap, remove tail.
#
# Node: key, val, prev, next
# _remove(node): unlink from list
# _add_to_head(node): insert after head
#
# get: map.get(key) or -1; if found: _remove, _add_to_head
# put: if key in map: update, _remove, _add_to_head. Else: new node, _add_to_head, map[key]=node. If len(map)>cap: tail=LRU, _remove(tail), del map[tail.key]