Entrevista técnica: ¿Cómo implementar una caché LFU en O(1)?

Problema y alcance

Implementa una LFUCache de capacidad fija. Si una clave existe, get(key) devuelve su valor e incrementa su frecuencia de acceso; de lo contrario, devuelve -1. put(key, value) inserta una nueva clave o modifica un valor existente. Actualizar una clave existente también cuenta como un acceso. Una clave nueva comienza con una frecuencia de 1. Al insertar en una caché llena, desaloja una clave con la frecuencia más baja. Si varias claves comparten esa misma frecuencia, desaloja la menos utilizada recientemente entre ellas.

Tanto get como put deben ejecutarse en tiempo O(1) esperado bajo el supuesto habitual de rendimiento promedio para tablas hash. Una capacidad de 0 es válida y convierte cada put en una operación sin efecto (no-op). El alcance se limita a una estructura de datos en memoria y de un solo hilo. Se excluyen TTL, capacidad basada en bytes, persistencia y consistencia distribuida.

Un registro de entrevista pública china de diciembre de 2025 enumera explícitamente LFU Cache, y una página de entrevista pública de 2026 conserva el mismo problema. LeetCode 460 proporciona un contrato estable, mientras que el artículo original de LFU en O(1) documenta la estructura enlazada de dos niveles. Esto respalda la representatividad actual de la pregunta sin establecer una atribución a una empresa verificada de forma independiente, por lo que companyName permanece nulo.

Qué evalúa el entrevistador

Primero, ¿puede el candidato derivar la estructura a partir de las dos dimensiones de desalojo? La búsqueda por clave requiere una tabla hash. La selección por frecuencia necesita un índice de frecuencias. Las claves con la misma frecuencia aún requieren un orden de recencia. Un único montículo (heap) puede encontrar la frecuencia más baja, pero cada acierto cambia una prioridad y normalmente cuesta O(log capacity).

Segundo, ¿puede el candidato enunciar los invariantes? Cada clave debe identificar exactamente un nodo. Cada nodo debe pertenecer exactamente a un bucket que coincida con su frecuencia. Cada bucket se ordena del más reciente al menos reciente. minFrequency debe identificar la frecuencia más pequeña presente actualmente. Recitar “dos mapas y una lista doblemente enlazada” no explica la eliminación de buckets vacíos, las actualizaciones ni el comportamiento con capacidad uno.

Tercero, ¿se mantiene correcto el desempate? Cuando un nodo pasa de la frecuencia f a f + 1, entra en el extremo más reciente de su nuevo bucket porque el acceso detonante acaba de ocurrir. El desalojo elimina el nodo menos reciente del bucket de frecuencia mínima. Un conjunto no ordenado puede satisfacer la primera regla de LFU, pero pierde el desempate por LRU.

Finalmente, el entrevistador espera escuchar una prueba de complejidad y una estrategia de pruebas. Cada operación solo puede realizar un número constante de operaciones de mapa, búsquedas de buckets y modificaciones de listas enlazadas. Las pruebas deben incluir empates de frecuencia, un bucket mínimo anterior que queda vacío, la actualización de una clave existente, capacidad cero y comparación diferencial contra un modelo de referencia lento sobre secuencias aleatorias largas.

Preguntas de clarificación antes de responder

• ¿Actualizar una clave existente incrementa su frecuencia? Sí. Después de cambiar el valor, put utiliza la misma ruta de promoción que un get exitoso.
• ¿Cómo se resuelven las frecuencias iguales? Mediante LRU dentro de esa frecuencia: se desaloja la clave cuyo último get exitoso o put de actualización sea el más antiguo.
• ¿Una nueva clave comienza en frecuencia 0 o 1? En 1, porque la inserción misma cuenta como un uso.
• ¿Es válida una capacidad de 0? Sí. Cada put retorna inmediatamente y cada get falla (miss).
• ¿El objetivo es O(1) estricto en el peor caso? Los cambios en listas enlazadas son constantes en el peor caso. Los mapas ordinarios ofrecen la garantía habitual de tiempo constante promedio o esperado, por lo que la afirmación general es O(1) esperado.
• ¿Pueden las frecuencias crecer sin límite? Las implementaciones de entrevista normalmente asumen que los enteros se mantienen dentro de un rango seguro. Una caché de producción de larga duración debe definir desbordamiento (overflow), envejecimiento o renormalización, lo que cambia el contrato.
• ¿Debe la caché ser segura para subprocesos (thread-safe)? No. Dado que get modifica la frecuencia y el orden, una versión concurrente debe hacer que la actualización multi-estructura sea una única sección crítica.

Estructura de respuesta en 30 segundos

“Utilizaré un mapa de clave a nodo y otro de frecuencia a una lista doblemente enlazada. Cada lista contiene únicamente nodos de igual frecuencia, ordenados del más nuevo al frente al más antiguo al final. minFrequency identifica directamente el bucket de desalojo. Un get exitoso o un put de actualización elimina el nodo de la frecuencia f, elimina el bucket anterior si queda vacío, incrementa la frecuencia e inserta el nodo al frente del nuevo bucket. Para una clave nueva, si la caché está llena, elimino el nodo del final del bucket minFrequency; luego agrego el nuevo nodo a la frecuencia 1 y establezco el mínimo en 1. Cada paso utiliza un número constante de operaciones de mapa y punteros, por lo que get y put son O(1) esperados, con espacio O(capacity).”

Solución paso a paso

Paso 1: Descartar enfoques directos que no cumplen el límite

Con un solo mapa de key a {value, frequency, lastUsed}, el desalojo escanea todas las claves y cuesta O(capacity). Un min-heap reduce el desalojo a O(log capacity), pero un acceso exitoso cambia tanto la frecuencia como la recencia, lo que requiere un índice de posiciones y reparar el heap. Un árbol balanceado ordenado por (frequency, time) también cuesta O(log capacity).

Obtener O(1) esperado requiere desacoplar el orden. Un mapa localiza una frecuencia directamente. Una lista doblemente enlazada mantiene la recencia únicamente entre nodos de una misma frecuencia y permite eliminación, inserción al frente y eliminación al final para un nodo conocido. Un entero registra la frecuencia mínima actual.

Paso 2: Definir cuatro invariantes

1. Cada clave en nodes apunta exactamente a un nodo real, y cada nodo real aparece en nodes.
2. Un nodo con frecuencia f aparece únicamente en frequencyLists.get(f); el mapa no conserva listas vacías.
3. Cada lista de frecuencia va desde el más recientemente usado al frente hasta el menos recientemente usado al final.
4. Cuando la caché no está vacía, minFrequency es la frecuencia mínima de todos los nodos; es 0 cuando la caché está vacía.

Una promoción mueve un nodo únicamente de f a f + 1. Si f es el mínimo y su bucket queda vacío, el nuevo mínimo es exactamente f + 1: no existía ningún bucket inferior, y el nodo promovido garantiza que existe un bucket f + 1. Un nodo recién insertado tiene frecuencia 1, por lo que la inserción restablece directamente minFrequency a 1.

Paso 3: Implementar nodos y listas de frecuencia

Una lista doblemente enlazada utiliza centinelas en la cabeza y la cola para evitar bifurcaciones condicionales para casos vacíos, de un solo nodo y de extremos. Un nodo almacena su clave para que el desalojo pueda eliminar la entrada coincidente de nodes sin una búsqueda inversa.

class Entry {
  frequency = 1
  prev: Entry | null = null
  next: Entry | null = null

  constructor(
    readonly key: number,
    public value: number,
  ) {}
}

class FrequencyList {
  private readonly head = new Entry(0, 0)
  private readonly tail = new Entry(0, 0)
  size = 0

  constructor() {
    this.head.next = this.tail
    this.tail.prev = this.head
  }

  addFirst(node: Entry): void {
    node.prev = this.head
    node.next = this.head.next
    this.head.next!.prev = node
    this.head.next = node
    this.size += 1
  }

  remove(node: Entry): void {
    node.prev!.next = node.next
    node.next!.prev = node.prev
    node.prev = null
    node.next = null
    this.size -= 1
  }

  removeLast(): Entry {
    const node = this.tail.prev
    if (!node || node === this.head) {
      throw new Error("cannot remove from an empty frequency list")
    }
    this.remove(node)
    return node
  }
}

Los centinelas no son entradas de caché, no aparecen en nodes y no cuentan contra la capacidad. remove solo acepta un nodo real actualmente en esa lista; los invariantes de LFUCache establecen esta precondición.

Paso 4: Implementar promoción, lecturas y escrituras

class LFUCache {
  private readonly nodes = new Map<number, Entry>()
  private readonly frequencyLists = new Map<number, FrequencyList>()
  private minFrequency = 0

  constructor(private readonly capacity: number) {
    if (!Number.isInteger(capacity) || capacity < 0) {
      throw new RangeError("capacity must be a non-negative integer")
    }
  }

  get(key: number): number {
    const node = this.nodes.get(key)
    if (!node) return -1

    this.promote(node)
    return node.value
  }

  put(key: number, value: number): void {
    if (this.capacity === 0) return

    const existing = this.nodes.get(key)
    if (existing) {
      existing.value = value
      this.promote(existing)
      return
    }

    if (this.nodes.size === this.capacity) {
      const victimList = this.frequencyLists.get(this.minFrequency)
      if (!victimList) throw new Error("missing minimum-frequency list")

      const victim = victimList.removeLast()
      this.nodes.delete(victim.key)
      if (victimList.size === 0) {
        this.frequencyLists.delete(this.minFrequency)
      }
    }

    const node = new Entry(key, value)
    this.getOrCreateList(1).addFirst(node)
    this.nodes.set(key, node)
    this.minFrequency = 1
  }

  private promote(node: Entry): void {
    const oldFrequency = node.frequency
    const oldList = this.frequencyLists.get(oldFrequency)
    if (!oldList) throw new Error("missing source frequency list")

    oldList.remove(node)
    if (oldList.size === 0) {
      this.frequencyLists.delete(oldFrequency)
      if (this.minFrequency === oldFrequency) {
        this.minFrequency = oldFrequency + 1
      }
    }

    node.frequency = oldFrequency + 1
    this.getOrCreateList(node.frequency).addFirst(node)
  }

  private getOrCreateList(frequency: number): FrequencyList {
    let list = this.frequencyLists.get(frequency)
    if (!list) {
      list = new FrequencyList()
      this.frequencyLists.set(frequency, list)
    }
    return list
  }
}

La rama de clave existente debe preceder a la comprobación de capacidad. No incrementa el recuento de entradas y no debe desalojar una clave no relacionada, aunque sí promueve el nodo y renueva la recencia dentro del nuevo bucket. Para una clave nueva, el desalojo ocurre antes de la inserción, mientras minFrequency todavía identifica el bucket víctima.

Paso 5: Demostrar corrección y complejidad

Los cuatro invariantes se mantienen después de la inicialización. Un fallo de caché (miss) no cambia nada. Un acceso exitoso elimina un nodo del bucket anterior correcto e inserta ese mismo nodo, con su nueva frecuencia, en el extremo más reciente del nuevo bucket. La membresía no cambia, pero la asignación de bucket y la recencia sí, y el manejo del mínimo vacío preserva el mínimo correcto.

Actualizar una clave existente solo cambia su valor antes de ejecutar la misma promoción. Si la inserción encuentra una caché llena, el nodo final del bucket de frecuencia mínima satisface ambas reglas para ser víctima: tiene la frecuencia más baja y es el más antiguo dentro de esa frecuencia. Eliminarlo de la lista y de nodes preserva el invariante de pertenencia uno a uno. El nuevo nodo entra en el extremo más reciente de la frecuencia 1, y minFrequency = 1 restaura cada invariante.

Cada método realiza un número fijo de búsquedas, inserciones o eliminaciones en el mapa y un número fijo de cambios de punteros en la lista enlazada. Bajo el supuesto de rendimiento promedio para mapas, tanto get como put son O(1) esperados. Cada nodo real existe en un mapa de claves y en una lista, mientras que el número de buckets no puede exceder el número de nodos, por lo que el espacio es O(capacity).

Paso 6: Verificar con trazas y pruebas diferenciales

Para capacidad 2, ejecuta esta secuencia:

put(1, 10)  -> key 1 has frequency 1
put(2, 20)  -> keys 1 and 2 tie; 2 is newer
get(1)      -> returns 10; key 1 moves to frequency 2
put(3, 30)  -> evicts key 2 at frequency 1
get(3)      -> returns 30; key 3 moves to frequency 2 and is newer than 1
put(4, 40)  -> keys 1 and 3 tie; evicts older key 1

El conjunto de pruebas también debe cubrir capacidades 0 y 1, fallos de caché que dejan el estado sin cambios, actualizaciones de claves existentes, promociones consecutivas que vacían el bucket mínimo y cambios repetidos de recencia entre claves de igual frecuencia. Una comprobación más rigurosa implementa un modelo de referencia O(capacity) que escanea buscando una víctima, y luego compara cada resultado de get y el estado visible final de clave-valor sobre un flujo determinista de operaciones aleatorias. Esto detecta desviaciones en minFrequency y enlaces rotos en las listas que podrían manifestarse solo tras trazas largas.

Respuesta de muestra de alta calidad

“Comenzaré fijando el contrato: una clave nueva tiene frecuencia 1; tanto un get exitoso como un put de actualización incrementan la frecuencia; frecuencias iguales usan LRU; y la capacidad 0 es válida. El objetivo es O(1) esperado bajo el comportamiento habitual de mapas.

Mantendré key -> node, frequency -> doubly linked list y minFrequency. Un nodo almacena su clave, valor, frecuencia y enlaces de lista. Dentro de una misma frecuencia, el frente es el más nuevo y el final es el más antiguo. Ante un acierto, desacoplo el nodo del bucket f y elimino el bucket anterior si queda vacío. Si ese bucket era el mínimo, avanzo el mínimo a f+1. Luego inserto el nodo al frente del bucket f+1.

Para put, una clave existente cambia de valor y se promueve sin desalojo. Para una clave nueva en una caché llena, elimino el nodo final del bucket de frecuencia mínima y borro su índice de clave. Luego inserto el nuevo nodo en la frecuencia 1 y restablezco el mínimo a 1. Los invariantes clave son una clave por nodo, un bucket correcto por nodo, orden de recencia dentro de cada bucket y una frecuencia mínima precisa. Cada paso utiliza un número constante de operaciones hash y de punteros, con espacio lineal respecto a la capacidad.

Probaría la traza de desempate con capacidad dos, capacidades cero y uno, actualizaciones de claves existentes y un bucket mínimo vaciado, para luego ejecutar pruebas diferenciales deterministas contra un modelo de escaneo. Las extensiones de producción requieren contratos separados para envejecimiento de frecuencia, desbordamiento, concurrencia y TTL; no pueden incluirse directamente en la afirmación de complejidad actual.”

Errores comunes

• Mantener únicamente key -> frequency → el desalojo sigue escaneando todas las claves → rastrea el bucket de frecuencia mínima directamente.
• Usar un conjunto no ordenado en cada bucket de frecuencia → se desconoce la clave más antigua de igual frecuencia → mantén una lista LRU doblemente enlazada por bucket.
• Agregar un nodo promovido al final → una clave recién accedida se convierte en la más antigua → inserta los nodos promovidos en el extremo más reciente.
• Conservar un bucket anterior vacío → minFrequency puede apuntar a ninguna víctima → elimina buckets vacíos y avanza el mínimo cuando sea necesario.
• Comprobar la capacidad antes de manejar una clave existente → una actualización desaloja una entrada no relacionada a pesar de no aumentar el tamaño → actualiza, promueve y retorna primero.
• Eliminar una víctima únicamente de su lista → el mapa de claves retiene un nodo fantasma → elimina la misma clave de ambas estructuras.
• No restablecer el mínimo después de la inserción → un desalojo posterior puede omitir la frecuencia 1 → establécelo en 1 para cada clave nueva.
• Llamar O(1) a la solución con montículo (heap) → los cambios de prioridad provocados por accesos requieren reparar el heap → acepta O(log capacity) o utiliza buckets de frecuencia.
• Afirmar O(1) estricto → los mapas ordinarios dependen del rendimiento hash promedio → establece O(1) esperado.
• Ejecutar únicamente el ejemplo publicado → el vaciado de buckets y el desvío en el orden de desempate permanecen ocultos → agrega verificaciones de invariantes y pruebas diferenciales aleatorias.

Preguntas de seguimiento

Pregunta de seguimiento 1: ¿Por qué minFrequency puede aumentar exactamente en uno cuando el bucket mínimo se vacía?

Un nodo solo se mueve de f a f + 1. Si f es el mínimo actual y su bucket anterior queda vacío, todos los demás nodos ya tienen una frecuencia de al menos f + 1, mientras que el nodo promovido garantiza que existe un bucket f + 1. Por lo tanto, el nuevo mínimo es exactamente f + 1; no se necesita un escaneo ascendente. Si al desalojo le sigue inmediatamente una nueva inserción, el mínimo final se restablece a 1 de todos modos.

Pregunta de seguimiento 2: ¿Cómo agregarías TTL?

TTL introduce un segundo orden basado en el tiempo de expiración. Un acierto debe verificar la expiración, y el desalojo por capacidad puede eliminar primero las entradas expiradas. Un min-heap puede ordenar las expiraciones, pero las actualizaciones y eliminaciones normalmente se convierten en O(log n). Una rueda de tiempo (timing wheel) reduce algunos costos pero introduce compromisos de precisión y estado. Define si la expiración o LFU tiene prioridad primero, y luego reevalúa la complejidad.

Pregunta de seguimiento 3: ¿Qué sucede cuando las frecuencias crecen durante mucho tiempo?

Los contadores pueden desbordarse y las claves populares antiguas pueden ocupar la caché indefinidamente. Las opciones incluyen decaimiento periódico, renormalización cuando el mínimo global cruza un umbral o una política aproximada con decaimiento temporal. Una renormalización completa crea una tarea ocasional de O(n). Mantener una latencia estable requiere una migración incremental o un contrato amortizado, explicitando la diferencia semántica respecto a los conteos exactos de por vida.

Pregunta de seguimiento 4: ¿Cómo la harías segura para subprocesos (thread-safe)?

La extensión correcta más simple coloca un mutex alrededor de cada get y put completos, porque una lectura exitosa modifica un nodo, dos buckets y el mínimo. La partición (sharding) reduce la contención pero otorga a cada partición una política de desalojo independiente, lo cual difiere de una LFU global exacta. El bloqueo de grano fino debe definir un orden fijo para el índice de claves, el bucket antiguo y el bucket nuevo, y evitar que el desalojo se entrelace con la promoción.

Pregunta de seguimiento 5: ¿Es LFU siempre mejor que LRU?

Depende de la distribución de accesos. LFU preserva claves que son frecuentemente accedidas a largo plazo, pero se adapta lentamente cuando claves históricamente populares pasan a ser frías. LRU reacciona más rápido a los cambios en el conjunto de trabajo y tiene una implementación más simple. Las cachés de producción a menudo combinan envejecimiento, políticas de admisión o estrategias aproximadas. La implementación de entrevista evalúa con precisión una regla de desalojo compuesta; no prescribe LFU pura para todas las cargas de trabajo.

Pregunta de seguimiento 6: ¿Por qué no se pueden reutilizar sin cambios los buckets de frecuencia de Top-K dinámico existentes?

Top-K dinámico solo enumera resultados por recuento y generalmente puede dejar sin especificar el orden entre elementos con conteos iguales. Esta caché debe desalojar exactamente al alcanzar la capacidad y requiere un desempate por LRU, por lo que cada bucket necesita un orden de recencia y cada actualización debe refrescarlo. Ambas estructuras usan buckets de frecuencia, pero sus interfaces, invariantes y objetivos de corrección difieren.