¿Cómo diseñas un LRU cache con O(1) get y put?

Question

Accepted Answer

Un **LRU (Least Recently Used) cache** desaloja el elemento que no ha sido accedido durante más tiempo cuando alcanza la capacidad. El diseño clásico combina un **hash map** (búsqueda O(1)) con una **lista doblemente vinculada** (reordenamiento O(1)), dando **O(1) get y put**. ## El diseño de dos estructuras ```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` es en sí mismo un hash map más una lista doblemente vinculada, exactamente la estructura descrita arriba. | Operación | Tiempo | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Por qué la lista doblemente vinculada Una lista doblemente vinculada te permite **desconectar un nodo del medio en O(1)** (sostienes su `prev`/`next`), lo cual es imposible con una lista simplemente vinculada o array sin un desplazamiento O(n). ## Por qué es importante Los LRU caches se sitúan delante de bases de datos, servidores web y CPUs para mantener los datos activos rápidos y la memoria acotada. Este problema es una pregunta estándar en entrevistas senior porque prueba combinar dos estructuras de modo que *cada una cubra la debilidad de la otra* - una habilidad clave de diseño de sistemas.