Una caché LRU con get y put en O(1) se construye normalmente con…
Opciones
- Una lista ordenada por último uso
- Un hash map más una doubly linked list (Opción correcta)
- Un min-heap ordenado por timestamp
- Dos pilas que intercambian sus elementos
Respuesta
Un hash map más una doubly linked list
Por qué
LRU = Least Recently Used: cuando se llena, elimina el elemento que lleva más tiempo sin usarse.
El hash map encuentra cualquier elemento en O(1). La doubly linked list mantiene los elementos en orden de uso: mueve un elemento al frente al usarlo y quita del final al llenarse, ambos en O(1).
En Python, OrderedDict (con move_to_end y popitem(last=False)) hace exactamente esto.
Recuerda
Caché LRU = hash map + doubly linked list.