Sesión 68: Gran Simulacro Onsite FAANG / Staff — Resolución en Vivo: Sliding Window Median (LeetCode 480 Hard)#

Tiempo estimado: 75-85 minutos. Nivel: De Junior/Trainee a Staff Specialist. Herramientas obligatorias: Hoja cuadriculada, lápiz, regla y bolígrafos de dos colores.

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

Consulta rápida: Glosario Maestro | Guía de Diagramas

Sliding Window Median (Mediana en Ventana Deslizante — LeetCode 480 Hard)#

(a) En palabras simples (intuición): Imagina que ves pasar una fila de 100 personas y en todo momento quieres saber quién es la persona de estatura mediana entre las últimas 5 personas que acaban de pasar. Cada vez que entra una persona nueva por la derecha, la persona más vieja por la izquierda sale del grupo. Debes recalcular la mediana al instante sin ordenar a las 5 personas desde cero cada vez.
(b) Definición técnica paso a paso: Problema algorítmico que calcula el valor mediano de todos los subarreglos continuos de tamaño fijo $K$ en un arreglo de longitud $N$ :
Si $K$ es impar: El elemento que ocupa la posición central exacta $⌊ K/2 ⌋$ cuando la ventana está ordenada.
Si $K$ es par: El promedio aritmético de los dos elementos centrales: $(elem₁ + elem₂) / (2.0)$ .
(c) Cómo funciona en Rust (memoria y tipos): Se implementa mediante una arquitectura de dos colas de prioridad balanceadas (BinaryHeap<i64> y BinaryHeap<Reverse<i64>>) con una tabla Hash HashMap<i64, usize> en el Heap para eliminaciones perezosas. Los valores numéricos se promueven a i64 para evitar desbordamientos enteros en sumas.
(d) Error típico de Junior: Usar window.sort() en cada paso, consumiendo $O(N \cdot K log K)$ , o usar BinaryHeap común intentando invocar un método .remove(val) que no existe en Rust y que en otros lenguajes toma $O(K)$ lineal.

Arquitectura de Montículos Duales Balanceados (Balanced Dual Heaps)#

(a) En palabras simples (intuición): Imagina que tienes dos cajas para clasificar a los candidatos: en la caja izquierda pones a la mitad con notas más bajas, y en la caja derecha pones a la mitad con notas más altas. La caja izquierda tiene un resorte que siempre empuja hacia arriba al mejor de los peores (el más inteligente del grupo bajo). La caja derecha tiene un resorte que siempre empuja hacia arriba al peor de los mejores. ¡La mediana siempre está asomada en la superficie de una o de ambas cajas!
(b) Definición técnica paso a paso: Partición del conjunto de datos en dos mitades ordenadas:

small (Max-Heap): Almacena los $⌈ K/2 ⌉$ elementos menores o iguales a la mediana.
large (Min-Heap): Almacena los $⌊ K/2 ⌋$ elementos mayores o iguales a la mediana.

Invariante de Balance Estricto: $small_size == large_size lor small_size == large_size + 1$
(c) Cómo funciona en Rust (memoria y tipos): Rust solo provee Max-Heap por defecto; para crear el Min-Heap se envuelven los enteros en la estructura adaptadora std::cmp::Reverse<i64>.
(d) Error típico de Junior: Olvidar que un elemento que entra a la ventana podría pertenecer a large pero insertarlo a ciegas en small, corrompiendo la separación de mitades.

Eliminación Perezosa (Lazy Removal)#

(a) En palabras simples (intuición): En un montículo (Heap) binario no puedes sacar fácilmente a alguien que esté enterrado en el fondo sin desarmar todo el árbol. La técnica de eliminación perezosa consiste en no sacarlo de inmediato: simplemente anotas su nombre en una lista de "personas caducadas". Si esa persona nunca llega a la cima del montículo, nunca nos estorba. En cuanto asome su cabeza en la cima, miras tu lista, confirmas que está caducado y lo arrojas a la basura en ese momento.
(b) Definición técnica paso a paso: Optimización que pospone la remoción física de un elemento del montículo hasta que alcanza la posición de la raíz (peek()):
Al salir un elemento de la ventana deslizante, se incrementa su contador en una tabla Hash delayed: HashMap<i64, usize>.
Se ajustan los contadores lógicos de tamaño small_size o large_size en $O(1)$ .
Durante las operaciones de rebalanceo o consulta de mediana, se ejecuta la rutina de poda (prune): mientras el elemento en la cima del montículo tenga un conteo pendiente en delayed, se extrae con .pop() en $O(log K)$ y se decrementa el contador.
(c) Cómo funciona en Rust (memoria y tipos): La tabla hash delayed almacena enteros primitivos en el Heap, eliminando claves cuyo contador llegue a 0 para no acumular memoria residual.
(d) Error típico de Junior: Disminuir el tamaño del heap físico en lugar de mantener variables de conteo lógico small_size y large_size, provocando desbalances falsos.

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

La Matemática de la Mediana y Prevención de Desbordamiento#

Consideremos dos valores en la frontera máxima de enteros de 32 bits:

a = 2,147,483,647 (i32::MAX), b = 2,147,483,647 (i32::MAX)

El Bug Clásico de Entrevista: Si calculas la mediana en i32: $suma = a + b = 2,147,483,647 + 2,147,483,647 = 4,294,967,294$ En complemento a dos de 32 bits con signo, $4,294,967,294$ se interpreta como $-2$ . Al dividir entre dos: $mediana errónea = (-2) / (2) = -1.0$ ¡El promedio de dos números gigantes positivos resulta ser un número negativo!
La Solución en Silicio: Promover inmediatamente los valores de entrada a enteros de 64 bits (i64): $suma = (a as i64) + (b as i64) = 4,294,967,294 (cabe holgadamente en i64)$ $mediana correcta = (4,294,967,294.0) / (2.0) = 2,147,483,647.0$

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

Diagrama Arquitectónico de Dual-Heap#

Consulta el diagrama vectorial:

Visualización del Día 68 y Memoria en Rust

Código fuente: Fuente Mermaid

DIAGRAMA MERMAID

flowchart TD
    subgraph DualHeap["Dual-Heap Balanceado en Rust"]
        LOW["small: BinaryHeap&lt;i64&gt;<br/>Max-Heap (Mitad Inferior)"]
        HIGH["large: BinaryHeap&lt;Reverse&lt;i64&gt;&gt;<br/>Min-Heap (Mitad Superior)"]
    end
    LOW <-->|balance() O(log K)| HIGH
    DELAY["delayed: HashMap&lt;i64, usize&gt;<br/>(Eliminación Perezosa)"] -.->|prune()| LOW
    DELAY -.->|prune()| HIGH
    MED["Mediana = if impar { small.peek() } else { (small.peek() + large.peek()) / 2.0 }"]

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

Ventana $K = 3$ sobre nums = [1, 3, -1, -3]:

TEXT

PASO 1: Inserción de los primeros K=3 elementos [1, 3, -1]
  num = 1: entra a small. small: [1], large: []
  num = 3: entra a large (3 > 1). small: [1], large: [3]
  num = -1: entra a small (-1 <= 1). small: [1, -1], large: [3]
  Invariante: small.len() = 2, large.len() = 1 (2 == 1 + 1 OK).
  Mediana Ventana 1 [1, 3, -1] -> k impar -> small.peek() = 1.0.

PASO 2: Deslizar a num = -3 (sale nums[0] = 1, entra num = -3)
  1. add(-3):
     -3 <= small.peek() (1) -> small.push(-3).
     small_size = 3, large_size = 1.
  2. remove(1):
     1 sale de la ventana activa -> delayed[1] += 1.
     1 estaba en small -> small_size pasa a 2.
     ¿El tope de small es 1? SÍ -> prune_small() ejecuta pop().
     delayed[1] pasa a 0 y se borra.
     small queda con: [-1, -3].
  3. balance():
     small_size = 2, large_size = 1. ¡Perfectamente balanceado!
  Mediana Ventana 2 [3, -1, -3] -> small.peek() = -1.0.

4. Implementación Canónica en Rust (Compilable con `rustc --test`)#

Archivo de referencia: practica-rust/dia_68.rs

RUST

use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};

pub struct DualHeapMedianFinder {
    small: BinaryHeap<i64>,          // Max-Heap: mitad inferior
    large: BinaryHeap<Reverse<i64>>, // Min-Heap: mitad superior
    delayed: HashMap<i64, usize>,    // Tabla de eliminaciones pendientes
    small_size: usize,
    large_size: usize,
}

impl DualHeapMedianFinder {
    pub fn new() -> Self {
        Self {
            small: BinaryHeap::new(),
            large: BinaryHeap::new(),
            delayed: HashMap::new(),
            small_size: 0,
            large_size: 0,
        }
    }

    fn prune_small(&mut self) {
        while let Some(&top) = self.small.peek() {
            if let Some(count) = self.delayed.get_mut(&top) {
                if *count > 0 {
                    *count -= 1;
                    if *count == 0 {
                        self.delayed.remove(&top);
                    }
                    self.small.pop();
                } else {
                    break;
                }
            } else {
                break;
            }
        }
    }

    fn prune_large(&mut self) {
        while let Some(&Reverse(top)) = self.large.peek() {
            if let Some(count) = self.delayed.get_mut(&top) {
                if *count > 0 {
                    *count -= 1;
                    if *count == 0 {
                        self.delayed.remove(&top);
                    }
                    self.large.pop();
                } else {
                    break;
                }
            } else {
                break;
            }
        }
    }

    fn balance(&mut self) {
        if self.small_size > self.large_size + 1 {
            let val = self.small.pop().unwrap();
            self.large.push(Reverse(val));
            self.small_size -= 1;
            self.large_size += 1;
            self.prune_small();
        } else if self.small_size < self.large_size {
            let Reverse(val) = self.large.pop().unwrap();
            self.small.push(val);
            self.large_size -= 1;
            self.small_size += 1;
            self.prune_large();
        }
    }

    pub fn add(&mut self, num: i64) {
        if self.small.is_empty() || num <= *self.small.peek().unwrap() {
            self.small.push(num);
            self.small_size += 1;
        } else {
            self.large.push(Reverse(num));
            self.large_size += 1;
        }
        self.balance();
    }

    pub fn remove(&mut self, num: i64) {
        *self.delayed.entry(num).or_insert(0) += 1;
        if num <= *self.small.peek().unwrap() {
            self.small_size -= 1;
            if num == *self.small.peek().unwrap() {
                self.prune_small();
            }
        } else {
            self.large_size -= 1;
            if let Some(&Reverse(top)) = self.large.peek() {
                if num == top {
                    self.prune_large();
                }
            }
        }
        self.balance();
    }

    pub fn get_median(&mut self, k: usize) -> f64 {
        self.prune_small();
        self.prune_large();
        if k % 2 == 1 {
            *self.small.peek().unwrap() as f64
        } else {
            let a = *self.small.peek().unwrap() as f64;
            let Reverse(b) = *self.large.peek().unwrap();
            (a + (b as f64)) / 2.0
        }
    }
}

pub fn median_sliding_window(nums: Vec<i32>, k: i32) -> Vec<f64> {
    let k = k as usize;
    if nums.is_empty() || k == 0 {
        return Vec::new();
    }

    let mut finder = DualHeapMedianFinder::new();
    let mut result: Vec<f64> = Vec::with_capacity(nums.len() - k + 1);

    for i in 0..k {
        finder.add(nums[i] as i64);
    }
    result.push(finder.get_median(k));

    for i in k..nums.len() {
        finder.add(nums[i] as i64);
        finder.remove(nums[i - k] as i64);
        result.push(finder.get_median(k));
    }

    result
}

Implementación de Referencia en Python Tipado#

PYTHON

from collections import defaultdict
import heapq
from typing import List


class DualHeapMedianFinderPy:
    def __init__(self) -> None:
        self.small = []  # Max-Heap (valores negativos)
        self.large = []  # Min-Heap
        self.delayed = defaultdict(int)
        self.small_size = 0
        self.large_size = 0

    def _prune(self, heap, is_small: bool) -> None:
        while heap:
            val = -heap[0] if is_small else heap[0]
            if self.delayed[val] > 0:
                self.delayed[val] -= 1
                heapq.heappop(heap)
            else:
                break

    def _balance(self) -> None:
        if self.small_size > self.large_size + 1:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
            self.small_size -= 1
            self.large_size += 1
            self._prune(self.small, True)
        elif self.small_size < self.large_size:
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -val)
            self.large_size -= 1
            self.small_size += 1
            self._prune(self.large, False)

    def add(self, num: int) -> None:
        if not self.small or num <= -self.small[0]:
            heapq.heappush(self.small, -num)
            self.small_size += 1
        else:
            heapq.heappush(self.large, num)
            self.large_size += 1
        self._balance()

    def remove(self, num: int) -> None:
        self.delayed[num] += 1
        if num <= -self.small[0]:
            self.small_size -= 1
            if num == -self.small[0]:
                self._prune(self.small, True)
        else:
            self.large_size -= 1
            if self.large and num == self.large[0]:
                self._prune(self.large, False)
        self._balance()

    def get_median(self, k: int) -> float:
        self._prune(self.small, True)
        self._prune(self.large, False)
        if k % 2 == 1:
            return float(-self.small[0])
        return (-self.small[0] + self.large[0]) / 2.0

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

Pregunta 1: En una entrevista FAANG bajo presión, ¿por qué los candidatos promedio fallan al intentar usar multiconjuntos (Multiset / Red-Black Trees) para este problema en Rust?

Respuesta:

Ausencia de Multiset con Índices en la Librería Estándar de Rust:
En C++, existe std::multiset (árbol rojo-negro balanceado que permite duplicados y borrado por iterador en $O(log K)$ ).
En Rust, std::collections::BTreeSet elimina duplicados de forma obligatoria, por lo que si dos números en la ventana son idénticos (ej. [2, 2]), el BTreeSet borra la presencia del duplicado, corrompiendo la mediana.
Además, BTreeSet no soporta indexación por orden (order-statistic tree o find_by_order) en $O(log K)$ sin librerías externas de terceros (crates).
Dominar la arquitectura de Dual-Heap con Lazy Removal es la única solución pura estándar compatible con la biblioteca estándar de Rust.

Pregunta 2: ¿Cómo garantiza la técnica de eliminación perezosa (Lazy Removal) que el consumo de memoria permanezca estrictamente acotado a

O(K)

Respuesta:

Acotación Proporcional al Tamaño de la Ventana:
En cualquier instante, el número de elementos vivos en la ventana es exactamente $K$ .
La cantidad de elementos "fantasma" pendientes de borrado en la tabla delayed y en los montículos solo puede acumularse si esos elementos no están en la cima.
Sin embargo, en cuanto un elemento fantasma alcanza la cima de cualquiera de los dos montículos durante balance() o get_median(), es expulsado inmediatamente por el método prune().
El tamaño total de los montículos nunca excede $O(K + número de fantasmas)$ , el cual está asintóticamente dominado por $O(K)$ .

Pregunta 3: ¿Por qué en la función remove verificamos if num <= *self.small.peek().unwrap() para decidir si decrementar small_size o large_size?

Respuesta:

Determinación del Montículo de Residencia:
Como los elementos vivos de small son todos menores o iguales que los elementos de large, el valor del tope small.peek() define la frontera de partición entre ambas mitades.
Si el número caducado $num \leq tope de small$ , el elemento forzosamente reside en small. Por ende, el tamaño lógico small_size debe decrementarse en $-1$ .
Si $num > tope de small$ , el elemento forzosamente reside en large, por lo que se decrementa large_size.
Esto mantiene los conteos lógicos exactos para que balance() sepa cuándo transferir elementos reales entre ambos árboles.

Pregunta 4: ¿Cuál es la complejidad temporal estricta de median_sliding_window y por qué es matemáticamente óptima?

Respuesta:

Análisis de Complejidad:
Para cada uno de los $N$ elementos del arreglo: 1. add(num) ejecuta un push en el montículo en $O(log K)$ . 2. remove(num) inserta en la tabla Hash en $O(1)$ promedio y potencialmente poda la raíz en $O(log K)$ . 3. balance() realiza a lo sumo una transferencia entre montículos en $O(log K)$ . 4. get_median() realiza lecturas $O(1)$ tras la poda.
Tiempo total: $N \times O(log K) = O(N log K)$ .
Optimalidad: Para calcular la mediana exacta en una ventana deslizante de tamaño $K$ , cualquier algoritmo basado en comparaciones requiere $Ω(log K)$ por paso debido a la cota inferior de teoría de la información de ordenamiento.

Pregunta 5: Durante una ronda Onsite de nivel Staff / Principal, ¿qué comportamiento de comunicación técnica distingue a un candidato sénior de un líder Staff?

Respuesta:

Liderazgo Técnico y Gestión de Incertidumbre:

Preguntas de aclaración antes de codificar: El candidato Staff pregunta explícitamente: "¿Qué pasa con números enteros extremos? ¿Pueden existir duplicados? ¿El tamaño de la ventana $K$ puede ser 1 o mayor que $N$ ?".
Enunciación de Invariantes antes del código: Explica con claridad cristalina el invariante de tamaño: small_size == large_size || small_size == large_size + 1.
Análisis de Silicio y Fallos en Producción: Justifica el uso de i64 para evitar bugs de desbordamiento en media y discute el impacto del recolector de basura o la memoria contigua de la caché L1.

Sesión 68: Gran Simulacro Onsite FAANG / Staff — Resolución en Vivo: Sliding Window Median (LeetCode 480 Hard)#

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

Sliding Window Median (Mediana en Ventana Deslizante — LeetCode 480 Hard)#

Arquitectura de Montículos Duales Balanceados (Balanced Dual Heaps)#

Eliminación Perezosa (Lazy Removal)#

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

La Matemática de la Mediana y Prevención de Desbordamiento#

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

Diagrama Arquitectónico de Dual-Heap#

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

4. Implementación Canónica en Rust (Compilable con rustc --test)#

Implementación de Referencia en Python Tipado#

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

6. Navegación#

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

4. Implementación Canónica en Rust (Compilable con `rustc --test`)#