Planteamiento y contexto aplicable
Implementa LRUCache(capacity) para un entero positivo capacity. Las claves y los valores son enteros no negativos. get(key) devuelve el valor almacenado o -1 cuando la clave no existe. put(key, value) inserta o actualiza una clave. Un get exitoso y cada put convierten a esa clave en la usada más recientemente. Insertar una nueva clave cuando la caché está llena desaloja exactamente una clave usada menos recientemente. Ambas operaciones públicas deben tomar un tiempo esperado de O(1).
Esta es una pregunta de código sobre estructuras de datos, no un diseño de caché distribuida. La implementación es para un solo proceso y un solo hilo; no incluye TTL, persistencia, pesos basados en tamaño ni acceso concurrente. «O(1) esperado» se basa en la suposición habitual de rendimiento promedio para las operaciones de tablas hash. Los cambios de punteros en la lista enlazada son O(1) en el peor caso.
El resultado importante no es simplemente la frase «mapa hash más lista doblemente enlazada». Una respuesta completa deduce por qué ambas estructuras son necesarias, establece el invariante entre el mapa y la lista, maneja la actualización de una clave existente sin desalojos accidentales y verifica el orden después de cada operación.
Qué evalúa el entrevistador
La primera señal es la traducción de los requisitos a operaciones. Se debe encontrar una clave sin realizar un escaneo, lo que exige un mapa hash. La recencia debe admitir mover un acierto arbitrario al extremo más reciente y eliminar el extremo menos reciente. Una lista doblemente enlazada puede hacer ambas cosas con un trabajo de punteros constante cuando el mapa ya proporciona el nodo.
La segunda señal es si las dos estructuras forman un solo estado. El mapa no puede almacenar solo valores; debe mapear cada clave a su nodo de la lista. Cada nodo real de la lista debe tener exactamente una entrada en el mapa, y cada entrada del mapa debe apuntar exactamente a un nodo real en la lista. Por lo tanto, el desalojo elimina la misma clave de ambas estructuras.
La tercera señal es la disciplina con los punteros. Los nodos ficticios (dummy) de cabeza y cola hacen que todos los nodos reales sean nodos interiores. Desvincular e insertar no requieren casos especiales para la primera, última o única entrada. El candidato debe ser capaz de indicar qué lado es el más reciente antes de programar y mantener esa convención sin cambios.
Finalmente, el entrevistador busca pruebas que expongan el orden, no solo los valores devueltos. Actualizar una clave existente al límite de capacidad, leer repetidamente una sola clave, usar una capacidad de uno e insertar después de un fallo (miss) revelan errores que un simple ejemplo de caso ideal no detecta.
Preguntas para aclarar antes de responder
- ¿
getactualiza la recencia? En este contrato sí lo hace. Unpeekde solo lectura sería una operación diferente y no movería el nodo. - ¿Actualizar una clave existente consume capacidad? No.
putcambia el valor y la recencia de la misma entrada; no debe desalojar otra clave. - ¿Qué devuelve un fallo de búsqueda (miss)? Este problema utiliza
-1, por lo que los valores deben restringirse en consecuencia o la API debe devolver un valor opcional. Aquí los valores son enteros no negativos y-1está reservado para un fallo. - ¿Es válida una capacidad de cero? Esta implementación rechaza capacidades no positivas. Admitir cero requeriría que cada inserción desapareciera de inmediato y cambia el contrato del constructor.
- ¿Debe ser una garantía estricta de peor caso
O(1)? Las tablas hash normalmente ofrecen un tiempo constante esperado. Una garantía estricta en el peor caso requiere una estructura de búsqueda diferente o suposiciones más fuertes. - ¿Se puede utilizar un mapa ordenado estándar? Puede ser aceptable en producción o en un ejercicio corto, pero el entrevistador aún puede exigir la implementación subyacente de la lista enlazada y sus invariantes.
- ¿Se requiere seguridad para hilos (thread safety)? No. Si se añade, recuerda que
getmuta la recencia, por lo que es una operación de escritura a efectos de sincronización.
Estructura de respuesta en 30 segundos
«Necesito una búsqueda y actualizaciones de recencia en tiempo constante esperado, así que mapearé cada clave a un nodo en una lista doblemente enlazada. El lado de la cabeza es el más reciente y el de la cola el menos reciente; los centinelas hacen que desvincular e insertar sean operaciones uniformes. Un acierto o actualización mueve su nodo al frente. Una nueva inserción que supere la capacidad elimina tail.prev de ambas estructuras. Dado que el mapa y la lista contienen los mismos nodos reales, get y put son de tiempo esperado O(1), con un espacio de O(capacity)».
Respuesta detallada paso a paso
Una lista por sí sola preserva la recencia, pero encontrar una clave o eliminar una entrada arbitraria cuesta O(n). Un mapa por sí solo encuentra un valor rápidamente, pero no puede identificar la clave usada menos recientemente sin escanear o almacenar una segunda estructura de ordenamiento. Un arreglo más un mapa sigue teniendo desplazamientos u operaciones de descubrimiento del predecesor de O(n). Los dos requisitos obligan a tener un índice de búsqueda y un orden mutable.
Utiliza esta orientación a lo largo de toda la respuesta:
head <-> most recent <-> ... <-> least recent <-> tailLos centinelas nunca entran en el mapa y nunca cuentan para la capacidad. Cada nodo real almacena key, value, prev y next; almacenar la clave es necesario porque el desalojo comienza desde tail.prev y debe eliminar la entrada correspondiente del mapa sin un escaneo inverso.
Cuatro invariantes hacen que la implementación sea fácil de revisar:
head.nextes el nodo real usado más recientemente ytail.preves el nodo real usado menos recientemente cuando la caché no está vacía.- Las claves del mapa y los nodos reales de la lista describen el mismo conjunto de entradas, en una correspondencia uno a uno.
- Para cada par adyacente,
left.next is rightyright.prev is left. - Después de cada operación pública,
0 <= len(nodes) <= capacity.
La implementación mantiene la manipulación de punteros en dos funciones auxiliares porque tanto get como put las reutilizan de manera genuina:
class Node:
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
if capacity <= 0:
raise ValueError("capacity must be positive")
self.capacity = capacity
self.nodes = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _detach(self, node: Node) -> None:
node.prev.next = node.next
node.next.prev = node.prev
def _attach_after_head(self, node: Node) -> None:
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _mark_recent(self, node: Node) -> None:
self._detach(node)
self._attach_after_head(node)
def get(self, key: int) -> int:
node = self.nodes.get(key)
if node is None:
return -1
self._mark_recent(node)
return node.value
def put(self, key: int, value: int) -> None:
node = self.nodes.get(key)
if node is not None:
node.value = value
self._mark_recent(node)
return
node = Node(key, value)
self.nodes[key] = node
self._attach_after_head(node)
if len(self.nodes) > self.capacity:
victim = self.tail.prev
self._detach(victim)
del self.nodes[victim.key]El orden de las asignaciones de punteros en _attach_after_head es fundamental. El nuevo nodo primero captura el antiguo primer nodo, luego ese antiguo nodo apunta de vuelta al nuevo nodo, y solo entonces cambia head.next. Sobrescribir head.next demasiado pronto puede hacer que se pierda el vecino que aún necesita que se actualice su prev.
La corrección se deduce por inducción sobre las operaciones. La inicialización satisface los cuatro invariantes. Un fallo de búsqueda (miss) no cambia nada. Un acierto o la actualización de una clave existente desvincula un nodo mapeado y reinserta ese mismo nodo al frente, por lo que la pertenencia y el tamaño no cambian. Una nueva inserción agrega el nodo a ambas estructuras; si el tamaño llega a capacity + 1, eliminar tail.prev de la lista y su clave del mapa restaura el conjunto uno a uno y el límite de capacidad. Una capacidad positiva garantiza que la víctima sea un nodo real.
Con una capacidad de dos, la traza put(1,10), put(2,20), get(1), put(3,30), put(1,15) produce los órdenes de recencia [1], [2,1], [1,2], [3,1], [1,3]. La clave 2 es desalojada, mientras que actualizar la clave 1 cambia su valor sin desalojar la clave 3.
Bajo un rendimiento promedio de tabla hash, cada método público realiza una búsqueda más un número fijo de operaciones de punteros y de mapa, por lo que el tiempo esperado es O(1). El mapa y la lista contienen como máximo capacity nodos reales, por lo que el espacio es O(capacity). Esta no es una garantía estricta de peor caso para la tabla hash.
La validación debe combinar trazas de ejemplo con verificaciones de invariantes. Prueba un fallo en caché vacía, el rechazo de capacidad cero, capacidad de uno, valores repetidos bajo claves diferentes, una actualización a capacidad completa, aciertos repetidos, desalojos alternados y una secuencia larga de operaciones aleatorias. Para la prueba aleatoria, compara los resultados y el orden con un modelo de referencia simple de O(n) y, después de cada operación, comprueba los punteros recíprocos, la ausencia de nodos duplicados, la igualdad entre mapa y lista, y el límite de capacidad.
Un mapa con orden de acceso puede expresar la misma política de forma más compacta cuando se permite el uso de bibliotecas estándar. LinkedHashMap de Java admite orden de acceso y un hook para remover la entrada más antigua. Esa es una opción útil para producción, pero no reemplaza la demostración en la entrevista. Asimismo, mantén diferenciada la LRU exacta dentro de un proceso del desalojo en producción: un servidor puede utilizar una LRU aproximada por muestreo para reducir los metadatos globales y la contención.
Respuesta de ejemplo de alta calidad
«Primero definiría el contrato: capacidad positiva, get devuelve -1 en caso de fallo, y cada acierto o put actualiza la recencia. Actualizar una clave existente no incrementa el tamaño. El objetivo es un tiempo esperado de O(1), basado en la búsqueda promedio de una tabla hash.
Un mapa hash resuelve la búsqueda de claves pero no el orden de desalojo. Una lista doblemente enlazada resuelve el orden y me permite desvincular un nodo arbitrario con un trabajo constante de punteros, siempre que ya tenga la referencia a dicho nodo. Por lo tanto, almaceno key -> node en el mapa y ordeno los nodos desde el más reciente después de una cabeza ficticia (dummy head) hasta el menos reciente antes de una cola ficticia (dummy tail). Los nodos almacenan su clave para que el desalojo en la cola también pueda eliminar la entrada del mapa.
El invariante principal es que el mapa y los nodos reales de la lista conforman el mismo conjunto. En un acierto, desvinculo ese nodo y lo inserto después de la cabeza. En una actualización, cambio su valor y realizo el mismo movimiento. En un put nuevo, lo agrego a ambas estructuras; si el tamaño excede la capacidad, elimino tail.prev de ambas. Los centinelas hacen que estas operaciones sean idénticas para la primera, última y única entrada.
Probaría una capacidad de uno, una actualización mientras está llena, gets repetidos que cambien la víctima y un fallo de búsqueda que no debe alterar el orden. También recorrería la lista después de cada operación aleatoria y la compararía con un modelo de referencia lento. La complejidad final es de O(1) esperado por operación y un espacio de O(capacity)».
Errores comunes
- Almacenar solo valores en el mapa → un acierto aún necesita buscar en la estructura de orden → mapea cada clave directamente a su nodo de la lista.
- Usar una lista simplemente enlazada → el mapa proporciona el nodo pero no su predecesor, por lo que una eliminación arbitraria puede requerir un escaneo → almacena tanto
prevcomonext. - Olvidar la clave dentro de cada nodo → el desalojo en la cola no puede eliminar la entrada del mapa sin una búsqueda inversa → almacena tanto la clave como el valor en el nodo.
- Tratar el orden de inserción como recencia → un
getexitoso no logra cambiar la futura víctima → mueve cada acierto al extremo más reciente. - Desalojar en la actualización de una clave existente → el tamaño no creció, por lo que desaparece una entrada no relacionada → maneja la actualización y retorna antes de la comprobación de capacidad para nuevas entradas.
- Eliminar una víctima de una sola estructura → entradas obsoletas en el mapa o nodos fantasma en la lista corrompen operaciones posteriores → realiza el desalojo de forma simétrica y comprueba la igualdad entre mapa y lista.
- Escribir ramas separadas para la cabeza, la cola y listas de un solo elemento → los casos de punteros se multiplican y eventualmente un límite diverge → utiliza dos centinelas permanentes.
- Afirmar un
O(1)estricto → las tablas hash generalmente dan un límite esperado y pueden degradarse con colisiones → establece la suposición de hashing. - Probar solo los valores de retorno → los valores correctos pueden ocultar un orden corrupto hasta un desalojo posterior → comprueba la secuencia de recencia completa y los invariantes de punteros.
Preguntas de seguimiento y respuestas
Pregunta de seguimiento 1: ¿Cómo la harías segura para hilos (thread-safe)?
get es una escritura porque modifica la lista. La extensión correcta más simple coloca un mutex alrededor de todo el get o put, manteniendo la actualización del mapa y la lista como atómica. El bloqueo de lectura/escritura (read-write lock) no hace que los aciertos ordinarios sean lectores. La fragmentación (sharding) reduce la contención, pero entonces cada fragmento tiene su propio orden LRU; ya no implementa una LRU global exacta a menos que se reintroduzca un mecanismo de ordenamiento compartido.
Pregunta de seguimiento 2: ¿Cómo agregarías expiración por TTL?
El TTL y la recencia son reglas de desalojo independientes. Un acierto primero debe rechazar entradas expiradas, mientras que put puede necesitar eliminar entradas expiradas antes de aplicar la política de capacidad. Un min-heap de tiempos de expiración admite una limpieza perezosa (lazy), pero añade un mantenimiento de O(log n) y registros obsoletos en el heap; una rueda de temporizadores (timing wheel) cambia la precisión y la implementación. No sigas afirmando que ambas operaciones son O(1) sin redefinir el mecanismo de expiración y su cota.
Pregunta de seguimiento 3: ¿Puedes ofrecer O(1) estricto en el peor caso?
La parte de la lista enlazada ya tiene un número constante estricto de operaciones de punteros. La parte de búsqueda depende de las garantías de la tabla hash. Lograr una búsqueda constante estricta en el peor caso requiere un modelo de diccionario más fuerte, un universo acotado de claves con direccionamiento directo o suposiciones de hashing especializadas. En un mapa hash estándar de cualquier lenguaje, describe el resultado como O(1) esperado o amortizado según el contrato de dicha implementación.
Pregunta de seguimiento 4: ¿Por qué no usar LinkedHashMap u OrderedDict?
Utiliza la biblioteca cuando su semántica de orden de acceso y desalojo coincida con el producto y el código manual de punteros no aporte valor. En una entrevista, explica primero el mapa subyacente y el invariante del orden enlazado, y luego ofrece la alternativa de la biblioteca. Verifica si la actualización, la lectura, la iteración y la eliminación del elemento más antiguo cuentan como accesos; los mapas ordenados con nombres similares no siempre comparten una semántica de recencia idéntica.
Pregunta de seguimiento 5: ¿Usarías LRU exacta en un servidor de caché grande?
No automáticamente. Mantener un orden de acceso global exacto añade escrituras de metadatos y un punto de contención en cada acierto. Una caché de producción puede fragmentar el orden, muestrear claves candidatas o elegir LFU cuando la frecuencia predice mejor la reutilización. Esas opciones intercambian la selección exacta de la víctima por memoria y rendimiento (throughput). El objeto de la entrevista sigue siendo útil porque permite validar mediante pruebas la política exacta y sus invariantes.