¿Cómo implementarías una caché LRU-K?

Enunciado y contexto

Implementa una caché LRU-K acotada que admita get, put y desalojo. Mantén los K accesos más recientes por clave. Las entradas con menos de K accesos forman un nivel de historial incompleto y deben desalojarse antes que las entradas calientes (hot). Aclara K, la capacidad, las actualizaciones de claves existentes, las llamadas concurrentes y las claves faltantes.

Qué evalúa el entrevistador

• Si mantienes el historial de accesos y los dos niveles de candidatos correctamente.
• Si puedes elegir un heap, una tabla hash o una estructura ordenada y analizar su costo.
• Si manejas sobreescrituras, capacidad cero, valores de K inválidos y visibilidad concurrente.
• Si comprendes que LRU-K filtra la contaminación por escaneos (scan pollution) en lugar de ganar en todas las cargas de trabajo.

Preguntas aclaratorias antes de responder

Confirma la seguridad entre hilos (thread safety), el desalojo aproximado, los valores mutables, los requisitos de TTL y las métricas de tasa de aciertos (hit-rate). Un orden estricto suele requerir un bloqueo o actualizaciones serializadas; un mayor rendimiento puede requerir sharding y una política aproximada.

Estructura de respuesta en 30 segundos

Almacena el valor, las últimas K marcas de tiempo lógicas y una versión por clave. Divide los candidatos en niveles de historial incompleto y caliente. Cuando se supere la capacidad, desaloja el elemento más antiguo del nivel incompleto; de lo contrario, desaloja el elemento caliente con la K-ésima marca de tiempo más reciente más pequeña. Una tabla hash proporciona búsquedas en O(1) y los heaps mantienen a los candidatos; las versiones descartan nodos de heap obsoletos. get y put estrictos tienen una complejidad esperada de O(log n), con un espacio de historial de O(capacidad·K).

Análisis detallado paso a paso

1. Registrar el historial de accesos

Agrega un valor de reloj lógico en cada acierto o escritura y conserva únicamente los últimos K valores. Un reloj lógico compara el orden sin saltos de reloj de pared y distingue accesos en el mismo milisegundo. Una sobreescritura cuenta como un acceso a menos que el enunciado indique que las escrituras no cuentan.

2. Mantener los candidatos de desalojo

El nivel incompleto se ordena por su acceso más reciente; el nivel caliente por su K-ésimo acceso más reciente. Mantén dos min-heaps de (key, version, rank). Un nuevo acceso inserta un nuevo nodo e incrementa la versión; el desalojo valida la versión y el rango actual, omitiendo los nodos obsoletos.

3. Límites y concurrencia

No almacenes en caché cuando la capacidad sea cero o negativa; rechaza K cuando sea cero o negativo. El desalojo y las actualizaciones de valores deben compartir una sección crítica para que las llamadas concurrentes a put no puedan exceder la capacidad. Los bloqueos fragmentados (sharded locks) mejoran el rendimiento, pero la capacidad global requiere entonces coordinación.

Respuesta de muestra de alta calidad

Separo las entradas en niveles de historial incompleto y caliente. Cada entrada almacena su valor, los últimos K tiempos lógicos y su versión; un acceso actualiza el historial e inserta un nuevo nodo de rango en el min-heap correspondiente. El desalojo verifica primero el heap incompleto y luego el heap caliente, validando las versiones para omitir nodos obsoletos. La búsqueda es O(1) a través del mapa, el trabajo en el heap es O(log n) y el espacio del historial es O(capacidad·K). Las pruebas cubren K=1 comportándose como LRU, la promoción tras accesos repetidos, escaneos de una sola vez, sobreescrituras, capacidad cero, escrituras concurrentes que exceden la capacidad, nodos obsoletos en el heap y la tasa de aciertos. LRU-K apunta a la contaminación por escaneos; Redis utiliza aproximaciones de LRU por muestreo y PostgreSQL usa clock-sweep, por lo que su costo y comportamiento no deben confundirse.

Errores comunes

• Mantener una sola marca de tiempo e implementar accidentalmente LRU ordinario.
• Tratar el acceso más reciente como el K-ésimo acceso más reciente.
• Eliminar la raíz de un heap sin manejar los nodos obsoletos duplicados.
• Permitir que las llamadas concurrentes a put excedan la capacidad o actualizar el historial fuera del bloqueo.
• Afirmar que LRU-K siempre supera a LRU.

Preguntas de seguimiento y respuestas

¿Qué debería suceder cuando K es igual a 1?

El primer acceso le otorga a una entrada la semántica de caliente, por lo que el desalojo se ordena por su acceso más reciente y la política se reduce al ordenamiento de LRU ordinario.

¿Cómo puedes reducir la memoria de los nodos del heap?

Usa índices y un heap mutable para reducir nodos duplicados, o elige colas generacionales o desalojo por muestreo. Aclara que el ordenamiento se vuelve aproximado y vuelve a medir la tasa de aciertos.

¿Cómo medirías la reducción de la contaminación por escaneos?

Crea un conjunto caliente cíclico y luego inserta muchas claves a las que se accede una sola vez. Compara LRU y LRU-K en cuanto a la tasa de aciertos del conjunto caliente, desalojos, latencia y memoria, incluyendo un conjunto caliente cercano a la capacidad máxima.