Sesión 56: LFU Cache (Least Frequently Used) en O(1) Estricto (LeetCode 460 Hard) & Graduación de Maestría Staff#

Navegación rápida:

• ← Sesión 55: Aritmética de Alto Rendimiento y Números K-Múltiplos (CTCI 17.9)
• Sesión 57: Grokking Cap. 10 — K-Nearest Neighbors (KNN), Distancias Vectoriales y Regresión →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 75-90 minutos.
• Código fuente compilado y probado: practica-rust/dia_56.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

En esta sesión culminante de la Semana 8 abordamos la cúspide del diseño de estructuras de datos para entrevistas FAANG y sistemas de producción de ultra-baja latencia: la Caché LFU (Least Frequently Used) con operaciones get y put en tiempo estrictamente O(1). Consulta el Glosario Maestro y la Guía de Diagramas.

LFU Cache (Least Frequently Used Cache / LeetCode 460 Hard)#

• (a) En palabras simples (intuición): Imagina un estante de biblioteca con espacio para solo 10 libros. Cada vez que alguien consulta un libro, le pones una calcomanía dorada. Si el estante se llena y llega un libro nuevo, el bibliotecario busca el libro que tenga menos calcomanías (el menos popular). Si hay dos o más libros empatados con la misma cantidad mínima de calcomanías, desaloja aquel que lleve más tiempo sin abrirse (desempate LRU). Tanto buscar un libro como colocar uno nuevo debe tomar exactamente un segundo.
• (b) Definición técnica paso a paso: Algoritmo de reemplazo de páginas y memoria caché que desaloja el elemento con menor frecuencia acumulada de accesos. Ante empates en la frecuencia mínima, aplica la política LRU (Least Recently Used). Requiere:
• get(key): Retorna el valor en O(1) e incrementa la frecuencia de la clave en +1.
• put(key, value): Si la clave existe, actualiza su valor e incrementa su frecuencia. Si no existe y la caché está llena, desaloja el nodo LRU de la frecuencia mínima actual min_freq en O(1) e inserta la nueva clave con frecuencia 1.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa mediante una Arena de Nodos indexada por enteros (usize) con dos tablas Hash: key_to_idx: HashMap<i32, usize> y freq_to_list: HashMap<usize, Dll>. Elimina punteros inseguros o ciclos de referencias Rc<RefCell<Node>>.
• (d) Error típico de Junior: Usar una Priority Queue (Min-Heap) ordenada por frecuencia; aunque desaloja el mínimo, actualizar la frecuencia en get tomaría O(log N) o requeriría un heap indexado complejo, violando el requerimiento estricto de O(1).

Arquitectura de Dos Niveles (Hash Map + Múltiples Doubly Linked Lists)#

• (a) En palabras simples (intuición): Imagina un edificio con varios pisos numerados: Piso 1, Piso 2, Piso 3... Cada piso es una lista de espera de personas que tienen exactamente esa cantidad de puntos. Cuando ganas un punto en el Piso 1, tomas el elevador y te mudas a la cabeza de la fila del Piso 2 en un solo paso. Si el Piso 1 queda desierto, el piso habitado más bajo ahora es el Piso 2.
• (b) Definición técnica paso a paso: Patrón de diseño donde el espacio de claves se segmenta por cubetas de frecuencia discretas:
• Nivel 1: key_to_idx permite acceso directo al nodo en memoria en O(1).
• Nivel 2: freq_to_list asocia cada entero de frecuencia f con una lista doblemente enlazada (Doubly Linked List).
• Cada lista mantiene el orden temporal: la cabeza es el elemento Más Recientemente Usado (MRU) y la cola es el Menos Recientemente Usado (LRU) de esa frecuencia específica.
• (c) Cómo funciona en Rust (memoria y tipos): La estructura Dll almacena índices opcionales head: Option<usize> y tail: Option<usize>, operando sobre un vector preasignado nodes: Vec<Option<Node>>.
• (d) Error típico de Junior: Olvidar actualizar la variable min_freq cuando el último nodo que residía en la lista de frecuencia mínima es promovido a la siguiente frecuencia.

Desalojo Determinista con Desempate LRU#

• (a) En palabras simples (intuición): Si tienes varios libros con solo 1 calcomanía cada uno, el libro que debes tirar es el que entró hace más horas o que lleva más tiempo acumulando polvo en el fondo de la repisa.
• (b) Definición técnica paso a paso: Garantía de unicidad en la política de desalojo. Al expulsar un elemento, se consulta la lista en freq_to_list[min_freq] y se extrae su nodo de cola:

Esto garantiza que el elemento seleccionado tiene la frecuencia mínima global y, a su vez, es el menos recientemente accedido dentro de ese grupo. Tiempo: exactamente O(1) operaciones fijas de puntero.

• (c) Cómo funciona en Rust (memoria y tipos): La clave desalojada se borra de key_to_idx, el nodo se vacía con .take() y su índice se guarda en free_indices para ser reciclado en la siguiente inserción.
• (d) Error típico de Junior: Iterar sobre todas las claves para buscar el mínimo, degradando la inserción a O(N).

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

La Prueba Formal de Complejidad O(1) Estricta para LFU#

¿Cómo es matemáticamente posible mantener ordenadas las frecuencias sin ningún algoritmo de ordenamiento?

Analicemos los posibles cambios de estado en cada llamada:

1. Operación get(key):#

• Acceso a key_to_idx.get(&key): O(1) tiempo promedio en tabla Hash.
• Extracción del nodo de la lista de su frecuencia antigua f: En una lista doblemente enlazada, si tienes el puntero directo al nodo, desvincularlo (remove) solo modifica dos punteros adyacentes:

• Verificación de min_freq: Si la lista antigua quedó vacía y f == min_freq, la nueva frecuencia mínima es indiscutiblemente f + 1 (porque el nodo que acabamos de promover era el único que tenía frecuencia f). Modificar min_freq = f + 1 toma O(1).
• Inserción en la lista de nueva frecuencia f + 1: Insertar en la cabeza de una lista enlazada toma O(1).
• Costo total de get: O(1) + O(1) + O(1) + O(1) = O(1).

2. Operación put(key, value):#

• Si la clave ya existía: Actualiza el valor y ejecuta la misma promoción de frecuencia explicada arriba ⟹ O(1).
• Si la clave es nueva y la capacidad está llena:
• Consulta freq_to_list[min_freq].pop_tail(): Extraer de la cola de la lista doblemente enlazada toma exactamente O(1).
• Elimina la entrada de key_to_idx: O(1).
• Inserta el nuevo nodo con frecuencia inicial 1: Como la nueva clave tiene frecuencia 1, la nueva frecuencia mínima global pasa a ser forzosamente min_freq = 1 en O(1).
• Inserta el nuevo nodo en la cabeza de freq_to_list[1]: O(1).
• Costo total de put: Estrictamente O(1) en el peor caso.

3. Visualización de Arquitectura y Memoria en Rust#

Diagrama Arquitectónico de Doble Nivel#

Consulta el diagrama vectorial:

flowchart LR
    subgraph HASHMAP["Nivel 1: key_to_idx"]
        K1["Key 1 -> Slot 0"]
        K2["Key 2 -> Slot 1"]
        K3["Key 3 -> Slot 2"]
    end

    subgraph FREQ_MAP["Nivel 2: freq_to_list & min_freq"]
        F1["Freq 1: [Head] <-> (Key 3, val 30) <-> [Tail]"]
        F2["Freq 2: [Head] <-> (Key 1, val 10) <-> (Key 2, val 20) <-> [Tail]"]
    end

    K1 -->|O(1)| F2
    K2 -->|O(1)| F2
    K3 -->|O(1)| F1

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Trazado tras put(1, 10), put(2, 20), get(1), put(3, 30) con capacidad 2:

PASO 1: put(1, 10), put(2, 20)
Stack: capacity = 2, min_freq = 1
Heap key_to_idx: { 1: 0, 2: 1 }
Heap freq_to_list[1]: Head <-> [Slot 1 (k:2, v:20)] <-> [Slot 0 (k:1, v:10)] <-> Tail

PASO 2: get(1) -> actualiza freq de Slot 0 (de 1 a 2)
Slot 0 sale de freq_to_list[1]. Lista freq 1 aún tiene a Slot 1 -> min_freq sigue siendo 1.
Slot 0 entra a freq_to_list[2].
Heap freq_to_list[1]: Head <-> [Slot 1 (k:2, v:20)] <-> Tail
Heap freq_to_list[2]: Head <-> [Slot 0 (k:1, v:10)] <-> Tail

PASO 3: put(3, 30) -> Capacidad llena (len 2 >= cap 2).
1. Consulta freq_to_list[min_freq = 1].
2. Extrae nodo de la cola: pop_tail() -> desaloja Slot 1 (k:2, v:20).
3. Elimina key 2 de key_to_idx.
4. Inserta nuevo nodo k:3, v:30 en el slot libre con freq = 1.
5. min_freq = 1.
Estado Final:
Heap key_to_idx: { 1: 0, 3: 1 }
Heap freq_to_list[1]: Head <-> [Slot 1 (k:3, v:30)] <-> Tail
Heap freq_to_list[2]: Head <-> [Slot 0 (k:1, v:10)] <-> Tail
¡Clave 2 expulsada limpiamente en tiempo O(1)!

4. Las 3 Trampas Clásicas en Entrevistas y Cómo Evitarlas#

Trampa 1: Pánico por Borrow Checker al Desvincular Nodos en Rust#

• El error: Usar referencias tradicionales mutables &mut Node dentro de estructuras circulares o bidireccionales (prev y next).
• Por qué falla: El modelo de propiedad de Rust prohíbe terminantemente tener dos referencias mutables simultáneas al mismo objeto en memoria, impidiendo crear listas doblemente enlazadas clásicas sin código unsafe o RefCell.
• La solución: Usar el patrón de Arena de Nodos indexada con enteros usize:

  struct Node { key: i32, val: i32, freq: usize, prev: Option<usize>, next: Option<usize> }

Los punteros son simples números enteros que indexan un Vec<Option<Node>>. Es 100% código seguro (safe Rust), sin fugas y con rendimiento nativo de silicio.

Trampa 2: No Incrementar min_freq cuando la Lista Queda Vacía#

• El error: Promover un nodo de min_freq a min_freq + 1 sin verificar si la lista antigua quedó vacía.
• Por qué falla: Si el nodo promovido era el único que tenía esa frecuencia baja, la lista de min_freq queda vacía. En el siguiente desalojo, el algoritmo intentará desalojar de una lista vacía, causando un error crítico o un pánico por unwrap().
• La solución: Verificar siempre si la lista quedó vacía tras la remoción:

  if dll.is_empty() && self.min_freq == old_freq {
      self.min_freq = new_freq;
  }

Trampa 3: No Reiniciar min_freq = 1 al Insertar un Nuevo Elemento#

• El error: Conservar el valor previo de min_freq cuando se inserta una clave nueva tras un desalojo.
• Por qué falla: Toda nueva clave arranca obligatoriamente con frecuencia de acceso 1. Por definición axiomática, la menor frecuencia presente en toda la caché a partir de ese instante pasa a ser estrictamente 1.
• La solución: Asignar explícitamente self.min_freq = 1 en cada inserción de un elemento nuevo.

5. Implementación Canónica en Rust y Comparativa con Python#

Implementación en Rust (practica-rust/dia_56.rs)#

use std::collections::HashMap;

#[derive(Debug, Clone)]
struct Node {
    key: i32,
    val: i32,
    freq: usize,
    prev: Option<usize>,
    next: Option<usize>,
}

#[derive(Debug, Clone, Default)]
struct Dll {
    head: Option<usize>,
    tail: Option<usize>,
    len: usize,
}

impl Dll {
    fn new() -> Self {
        Self { head: None, tail: None, len: 0 }
    }

    fn is_empty(&self) -> bool {
        self.len == 0
    }

    fn insert_head(&mut self, nodes: &mut [Option<Node>], idx: usize) {
        if let Some(node) = nodes[idx].as_mut() {
            node.prev = None;
            node.next = self.head;
        }

        if let Some(old_head_idx) = self.head {
            if let Some(old_head) = nodes[old_head_idx].as_mut() {
                old_head.prev = Some(idx);
            }
        } else {
            self.tail = Some(idx);
        }

        self.head = Some(idx);
        self.len += 1;
    }

    fn remove(&mut self, nodes: &mut [Option<Node>], idx: usize) {
        let (p, n) = if let Some(node) = nodes[idx].as_ref() {
            (node.prev, node.next)
        } else {
            return;
        };

        if let Some(prev_idx) = p {
            if let Some(prev_node) = nodes[prev_idx].as_mut() {
                prev_node.next = n;
            }
        } else {
            self.head = n;
        }

        if let Some(next_idx) = n {
            if let Some(next_node) = nodes[next_idx].as_mut() {
                next_node.prev = p;
            }
        } else {
            self.tail = p;
        }

        if let Some(node) = nodes[idx].as_mut() {
            node.prev = None;
            node.next = None;
        }

        self.len -= 1;
    }

    fn pop_tail(&mut self, nodes: &mut [Option<Node>]) -> Option<usize> {
        let tail_idx = self.tail?;
        self.remove(nodes, tail_idx);
        Some(tail_idx)
    }
}

pub struct LFUCache {
    capacity: usize,
    min_freq: usize,
    key_to_idx: HashMap<i32, usize>,
    freq_to_list: HashMap<usize, Dll>,
    nodes: Vec<Option<Node>>,
    free_indices: Vec<usize>,
}

impl LFUCache {
    pub fn new(capacity: i32) -> Self {
        let cap = if capacity > 0 { capacity as usize } else { 0 };
        Self {
            capacity: cap,
            min_freq: 0,
            key_to_idx: HashMap::with_capacity(cap),
            freq_to_list: HashMap::new(),
            nodes: Vec::with_capacity(cap),
            free_indices: Vec::new(),
        }
    }

    fn update_freq(&mut self, idx: usize) {
        let old_freq = self.nodes[idx].as_ref().unwrap().freq;
        let new_freq = old_freq + 1;

        if let Some(dll) = self.freq_to_list.get_mut(&old_freq) {
            dll.remove(&mut self.nodes, idx);
            if dll.is_empty() && self.min_freq == old_freq {
                self.min_freq = new_freq;
            }
        }

        self.nodes[idx].as_mut().unwrap().freq = new_freq;
        self.freq_to_list
            .entry(new_freq)
            .or_insert_with(Dll::new)
            .insert_head(&mut self.nodes, idx);
    }

    pub fn get(&mut self, key: i32) -> i32 {
        if self.capacity == 0 {
            return -1;
        }
        if let Some(&idx) = self.key_to_idx.get(&key) {
            let val = self.nodes[idx].as_ref().unwrap().val;
            self.update_freq(idx);
            val
        } else {
            -1
        }
    }

    pub fn put(&mut self, key: i32, value: i32) {
        if self.capacity == 0 {
            return;
        }

        if let Some(&idx) = self.key_to_idx.get(&key) {
            self.nodes[idx].as_mut().unwrap().val = value;
            self.update_freq(idx);
            return;
        }

        if self.key_to_idx.len() >= self.capacity {
            if let Some(min_dll) = self.freq_to_list.get_mut(&self.min_freq) {
                if let Some(evicted_idx) = min_dll.pop_tail(&mut self.nodes) {
                    if let Some(evicted_node) = self.nodes[evicted_idx].take() {
                        self.key_to_idx.remove(&evicted_node.key);
                        self.free_indices.push(evicted_idx);
                    }
                }
            }
        }

        let node_idx = if let Some(free_idx) = self.free_indices.pop() {
            self.nodes[free_idx] = Some(Node { key, val: value, freq: 1, prev: None, next: None });
            free_idx
        } else {
            let idx = self.nodes.len();
            self.nodes.push(Some(Node { key, val: value, freq: 1, prev: None, next: None }));
            idx
        };

        self.key_to_idx.insert(key, node_idx);
        self.min_freq = 1;
        self.freq_to_list
            .entry(1)
            .or_insert_with(Dll::new)
            .insert_head(&mut self.nodes, node_idx);
    }
}

Implementación de Referencia en Python (practica/dia_56_lfu_cache_and_final_certification.py)#

from typing import Dict, Optional


class LFUNode:
    def __init__(self, key: int, val: int) -> None:
        self.key, self.val = key, val
        self.freq = 1
        self.prev: Optional["LFUNode"] = None
        self.next: Optional["LFUNode"] = None


class DoublyLinkedList:
    def __init__(self) -> None:
        self.head, self.tail = LFUNode(0, 0), LFUNode(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head
        self.size = 0

    def insert_head(self, node: LFUNode) -> None:
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
        self.size += 1

    def remove(self, node: LFUNode) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

    def pop_tail(self) -> Optional[LFUNode]:
        if self.size == 0:
            return None
        node = self.tail.prev
        self.remove(node)
        return node

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

7. Rúbrica de Graduación y Certificación Final de Maestría Staff#

Con esta sesión concluye el bloque intensivo de Semana 7 y Semana 8 (Días 43 al 56).

Navegación final:

• ← Sesión 55: Aritmética de Alto Rendimiento y Números K-Múltiplos (CTCI 17.9)
• Sesión 57: Grokking Cap. 10 — K-Nearest Neighbors (KNN), Distancias Vectoriales y Regresión →
• Glosario Maestro
• Guía de Diagramas de Arquitectura