Como você projeta um cache LRU com get e put em O(1)?

Question

Accepted Answer

Um **cache LRU (Least Recently Used)** remove o item que não foi acessado por mais tempo quando atinge a capacidade. O design clássico combina uma **hash map** (busca O(1)) com uma **doubly linked list** (reordenação O(1)), resultando em **get e put em O(1)**. ## Estrutura de duas estruturas de dados ```text HashMap: key -> node DLL (recency order): MRU <-> ... <-> LRU get/put: map finds node move touched node to front (MRU) in O(1); DLL splices it evict the tail (LRU) when full to the front in O(1) ``` ## Código ```python from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cap = capacity self.cache = OrderedDict() # preserves access order def get(self, key): # O(1) if key not in self.cache: return -1 self.cache.move_to_end(key) # mark as most recently used return self.cache[key] def put(self, key, value): # O(1) if key in self.cache: self.cache.move_to_end(key) self.cache[key] = value if len(self.cache) > self.cap: self.cache.popitem(last=False) # evict least recently used ``` `OrderedDict` é em si uma hash map mais uma doubly linked list, exatamente a estrutura descrita acima. | Operação | Tempo | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Por que a doubly linked list Uma doubly linked list permite que você **desconecte um nó do meio em O(1)** (você mantém seus `prev`/`next`), o que é impossível com uma singly linked list ou array sem um shift O(n). ## Por que isso importa Caches LRU ficam na frente de bancos de dados, servidores web e CPUs para manter dados quentes rápidos e memória limitada. Este problema é uma questão clássica de entrevista sênior porque testa a combinação de duas estruturas para que a *fraqueza de uma seja coberta pela outra* — uma habilidade-chave de design de sistemas.