Sesión 49: Cierre Magistral y Consolidación de la Semana 7 — Bits, Búsqueda Avanzada, Tries y DSU#

Navegación rápida:

• ← Sesión 48: Conjuntos Disjuntos (Union-Find / DSU): Optimizaciones de Rango y Compresión de Caminos
• Sesión 50: Trapping Rain Water (CTCI 17.21): Two Pointers vs Monotonic Stack →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 75-90 minutos.
• Código fuente compilado y probado: practica-rust/dia_49.rs

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

En esta sesión de integración y consolidación unificamos la manipulación de registros de silicio con estructuras de datos en árbol y partición de conjuntos para resolver problemas de nivel Staff y FAANG. Consulta el Glosario Maestro y la Guía de Diagramas.

Bitwise Trie (Trie Binario de Máximo XOR / LeetCode 421)#

• (a) En palabras simples (intuición): Imagina que quieres que el resultado de un interruptor XOR sea lo más grande posible. Para que un número sea gigantesco, lo que más importa es que sus dígitos de la izquierda (los más valiosos) sean 1. Cada número se ve como un camino de 32 decisiones: girar a la izquierda (0) o a la derecha (1). Si tu número actual tiene un 0 en el bit más valioso, buscas desesperadamente si en el árbol existe alguien con un 1 para hacer chispas y ganar ese bit millonario. Si existe, tomas ese camino; si no, te conformas con lo que hay.
• (b) Definición técnica paso a paso: Árbol de prefijos donde el alfabeto tiene cardinalidad exactamente 2 (Σ = {0, 1}). Almacena números enteros descompuestos en sus 32 bits desde el MSB (bit 31) hasta el LSB (bit 0):
• Inserción: Recorre los 32 bits de x; cada nodo solo posee dos punteros de hijos: children[0] y children[1].
• Búsqueda Voraz de Máximo XOR: Para un número y, en cada bit i, se evalúa si existe el hijo opuesto 1 - bitᵢ(y). Si existe, se enciende el bit i en el acumulador (max_xor |= (1 << i)) y se desciende por esa rama; si no, se desciende por la rama idéntica.
• Complejidad: O(32 · N) = O(N) tiempo lineal y O(32 · N) = O(N) espacio, frente al O(N²) de la fuerza bruta.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa sobre una Arena de nodos Vec<BitwiseNode> con children: [Option<usize>; 2]. No hay sobrecarga de HashMap ni punteros dispersos.
• (d) Error típico de Junior: Recorrer los bits desde el menos significativo (LSB, bit 0) hacia el más significativo; una decisión greedy solo es óptima si se maximizan primero las potencias más altas (2³¹, 2³⁰, …).

Kruskal's Minimum Spanning Tree (MST / Grokking Cap. 10 y 11)#

• (a) En palabras simples (intuición): Imagina que tienes varias ciudades y quieres tender cables de fibra óptica para que todas queden conectadas entre sí al menor costo total. Miras la lista de todas las carreteras posibles y eliges siempre la carretera más barata disponible. Solo hay una regla: si la carretera barata que quieres poner conecta dos ciudades que ya estaban unidas por otros cables, la descartas para no tirar el dinero haciendo un círculo inútil. Repites hasta que todas las ciudades formen una sola red.
• (b) Definición técnica paso a paso: Algoritmo voraz (greedy) para encontrar el árbol generador de peso mínimo en un grafo conexo ponderado no dirigido:

1. Ordenar todas las E aristas de forma ascendente por peso: O(E log E).
2. Inicializar un DSU con V componentes disjuntos.
3. Recorrer aristas: si dsu.union(u, v) es exitoso, la arista se añade al MST y se suma su costo. Si retorna false, se descarta por formar un ciclo.
4. Finaliza al seleccionar exactamente V - 1 aristas.

• (c) Cómo funciona en Rust (memoria y tipos): La lista de aristas se ordena con sorted_edges.sort_by_key(|e| e.2). DSU controla la conectividad en O(E · α(V)).
• (d) Error típico de Junior: No comprobar si al final se obtuvieron exactamente V - 1 aristas; si el grafo original estaba desconectado en varias islas, el algoritmo no produce un árbol completo y debe retornar un error o indicador especial.

Síntesis Algorítmica Compuesta (Hybrid Data Structures)#

• (a) En palabras simples (intuición): Es como construir una navaja suiza: en lugar de usar una sola herramienta básica, combinas un destornillador con una tijera para resolver un problema complejo que ninguna herramienta aislada podría solucionar por sí sola.
• (b) Definición técnica paso a paso: Metodología de ingeniería de software donde se ensamblan múltiples paradigmas (ej. operadores de silicio + árboles de prefijos en Bitwise Trie, o algoritmos greedy + conjuntos disjuntos en Kruskal) para transformar problemas de complejidad intratable (O(N²) o exponencial) en tiempos asintóticos estrictamente lineales o cuasi-lineales.
• (c) Cómo funciona en Rust (memoria y tipos): Exige modularidad estricta y dominio del ownership: una estructura puede poseer colecciones vectoriales contiguas mientras presta vistas inmutables a los algoritmos de ordenamiento o consulta.
• (d) Error típico de Junior: Intentar resolver problemas compuestos con fuerza bruta o estructuras monolíticas no desacopladas.

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

La Matemática de la Estrategia Voraz en Bitwise Trie (O(32 · N))#

¿Por qué tomar siempre el bit opuesto en el nivel i garantiza matemáticamente el máximo XOR global?

Consideremos la suma de potencias de 2:

Esta desigualdad fundamental de la base binaria demuestra que:

• Tener un 1 en la posición i vale estrictamente más que tener unos en TODAS las posiciones inferiores juntas ($0$ hasta i - 1).
• Por ejemplo: 2⁴ = 16, mientras que 2³ + 2² + 2¹ + 2⁰ = 8 + 4 + 2 + 1 = 15.
• Un 1 en la posición 4 derrota a cualquier combinación posible en las posiciones 3, 2, 1 y 0.

Por lo tanto:

1. Al evaluar el bit 31, si podemos conseguir que sea 1 eligiendo la rama opuesta, debemos elegirla sin dudarlo, sin importar qué ocurra en los 30 bits siguientes.
2. Esta propiedad de subestructura óptima e independencia de ramas garantiza que la decisión local voraz desde el bit 31 hacia el 0 produce el óptimo global sin necesidad de backtracking.

Demostración de Kruskal: Correctitud del Enfoque Voraz (Propiedad del Corte)#

¿Por qué elegir siempre la arista más barata que no genere ciclos produce el Árbol de Expansión Mínima óptimo?

Teorema de la Propiedad del Corte (Cut Property): Sea un grafo conexo ponderado G = (V, E). Considera cualquier partición del conjunto de vértices V en dos subconjuntos no vacíos S y V setminus S (un "corte").

• Si e = (u, v) es la arista de peso estrictamente mínimo que cruza el corte (es decir, u ∈ S y v ∈ V setminus S), entonces e pertenece obligatoriamente a todo Árbol de Expansión Mínima de G.

En el algoritmo de Kruskal:

• En cualquier iteración, si una arista (u, v) une dos componentes distintas en DSU, define implícitamente un corte entre la componente de u y el resto del grafo.
• Dado que las aristas se procesan en estricto orden ascendente de peso, la primera arista que cruza entre estas dos componentes es, por definición, la arista de peso mínimo que cruza dicho corte.
• Por la Propiedad del Corte, su inclusión en el MST es matemáticamente óptima.

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

Diagrama de Árbol de Expansión Mínima (Kruskal + DSU)#

Consulta el diagrama vectorial:

flowchart TD
    EDGES["Lista de Aristas Ordenadas por Peso:<br/>(2,3): 4, (0,3): 5, (0,2): 6, (0,1): 10, (1,3): 15"] --> E1["Procesar (2,3) peso 4: find(2)!=find(3) -> UNION -> MST: {(2,3)}"]
    E1 --> E2["Procesar (0,3) peso 5: find(0)!=find(3) -> UNION -> MST: {(2,3), (0,3)}"]
    E2 --> E3["Procesar (0,2) peso 6: find(0)==find(2) -> ¡CICLO! -> DESCARTAR"]
    E3 --> E4["Procesar (0,1) peso 10: find(0)!=find(1) -> UNION -> MST: {(2,3), (0,3), (0,1)}"]
    E4 --> STOP["|MST| == V - 1 = 3 aristas. Detener algoritmo. Costo: 19."]

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

Nodos creados en la Arena de BitwiseTrie al insertar 5 = 000…0101₂ y 25 = 000…11001₂:

STACK:
[ trie: BitwiseTrie { nodes: Vec<BitwiseNode> { len: 35, cap: 64 } } ]

HEAP (Buffer de Arena contigua):
Los primeros 27 bits son idénticos (ceros en ambos números):
[0] (Raíz) -> children[0] = Some(1)
[1] -> children[0] = Some(2)
...
[26] (Bit 5): children[0] = Some(27)
[27] (Bit 4): ¡Bifurcación!
    - 5 tiene bit 4 en 0 -> children[0] = Some(28)
    - 25 tiene bit 4 en 1 -> children[1] = Some(29)

BÚSQUEDA VORAZ DE 5 CONTRA EL TRIE:
En el bit 4 de 5 (que es 0), el bit opuesto es 1.
El algoritmo consulta: ¿nodes[27].children[1] existe?
¡Sí! Apunta a nodo 29 (el camino de 25).
El algoritmo enciende max_xor |= (1 << 4) (gana 16 puntos) y desciende por el nodo 29.
Resultado final: 5 ^ 25 = 28 (0b0001_1100).

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

Trampa 1: Intentar Resolver Máximo XOR con Fuerza Bruta O(N²)#

• El error: Escribir dos bucles anidados para calcular nums[i] ^ nums[j] para todos los pares.
• Por qué falla: Para N = 2 × 10⁵ (restricción estándar de LeetCode 421), N² = 4 × 10¹⁰ operaciones. A 10⁸ operaciones por segundo, esto toma más de 400 segundos, resultando en un categórico Time Limit Exceeded (TLE).
• La solución: Usar un Bitwise Trie. Con 32 iteraciones fijas por número, procesa los 200,000 números en apenas 32 × 200,000 = 6.4 × 10⁶ operaciones (< 0.05 segundos).

Trampa 2: No Detectar Grafos Desconectados en Kruskal#

• El error: Retornar la suma acumulada de pesos cuando se acaban las aristas, sin verificar si el árbol conectó a todos los nodos.
• Por qué falla: Si el grafo tiene componentes desconectadas (islas), es imposible construir un Árbol de Expansión. El algoritmo terminará con menos de V - 1 aristas y con más de 1 componente en DSU.
• La solución: Validar estrictamente:

  if mst_edges.len() == num_nodes - 1 && dsu.components == 1 {
      Some((total_cost, mst_edges))
  } else {
      None // Grafo desconectado
  }

Trampa 3: Usar Estructuras Dinámicas con Sobrecarga de Punteros en Bitwise Trie#

• El error: Crear nodos con HashMap<u8, Box<Node>>.
• Por qué falla: Cada inserción de 32 bits crea hasta 32 nodos. Para N = 100,000, son millones de asignaciones individuales en el Heap con dispersión en tablas hash, destruyendo la memoria y el rendimiento.
• La solución: Usar un arreglo estático children: [Option<usize>; 2] dentro de una Arena de vector contiguo.

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

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

/// Nodo para el Bitwise Trie (ramas binarias 0 y 1).
#[derive(Debug, Clone, Copy)]
pub struct BitwiseNode {
    pub children: [Option<usize>; 2],
}

impl BitwiseNode {
    pub fn new() -> Self {
        Self { children: [None, None] }
    }
}

/// Trie binario para enteros de 32 bits.
#[derive(Debug, Default)]
pub struct BitwiseTrie {
    nodes: Vec<BitwiseNode>,
}

impl BitwiseTrie {
    pub fn new() -> Self {
        let mut trie = Self { nodes: Vec::new() };
        trie.nodes.push(BitwiseNode::new());
        trie
    }

    pub fn insert(&mut self, num: u32) {
        let mut curr = 0;
        for i in (0..32).rev() {
            let bit = ((num >> i) & 1) as usize;
            let next = match self.nodes[curr].children[bit] {
                Some(child_idx) => child_idx,
                None => {
                    let new_idx = self.nodes.len();
                    self.nodes.push(BitwiseNode::new());
                    self.nodes[curr].children[bit] = Some(new_idx);
                    new_idx
                }
            };
            curr = next;
        }
    }

    pub fn find_max_xor_pair(&self, num: u32) -> u32 {
        let mut curr = 0;
        let mut max_xor = 0u32;

        for i in (0..32).rev() {
            let bit = ((num >> i) & 1) as usize;
            let opposite_bit = 1 - bit;

            if let Some(child_idx) = self.nodes[curr].children[opposite_bit] {
                max_xor |= 1 << i;
                curr = child_idx;
            } else if let Some(child_idx) = self.nodes[curr].children[bit] {
                curr = child_idx;
            } else {
                break;
            }
        }

        max_xor
    }
}

/// LeetCode 421: Maximum XOR of Two Numbers in an Array.
pub fn find_maximum_xor(nums: &[u32]) -> u32 {
    if nums.len() < 2 {
        return 0;
    }

    let mut trie = BitwiseTrie::new();
    for &num in nums {
        trie.insert(num);
    }

    let mut max_xor = 0;
    for &num in nums {
        let candidate = trie.find_max_xor_pair(num);
        if candidate > max_xor {
            max_xor = candidate;
        }
    }

    max_xor
}

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

from typing import Dict, List, Tuple


class BitwiseTrie:
    def __init__(self) -> None:
        self.root: Dict[int, dict] = {}

    def insert(self, num: int) -> None:
        curr = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if bit not in curr:
                curr[bit] = {}
            curr = curr[bit]

    def find_max_xor_pair(self, num: int) -> int:
        curr = self.root
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            opposite = 1 - bit
            if opposite in curr:
                max_xor |= (1 << i)
                curr = curr[opposite]
            else:
                curr = curr.get(bit, {})
        return max_xor


def find_maximum_xor(nums: List[int]) -> int:
    """LeetCode 421: Maximum XOR en O(32 * N) = O(N)."""
    if len(nums) < 2:
        return 0
    trie = BitwiseTrie()
    for num in nums:
        trie.insert(num)
    return max(trie.find_max_xor_pair(num) for num in nums)

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

7. Ejercicios de Práctica Independiente y Casos Límite#

1. Paso Límite 1: Arreglo de 2 Números Idénticos: - Para nums = [7, 7], verifica que find_maximum_xor(&nums) retorne 0 (7 oplus 7 = 0).
2. Paso Límite 2: Kruskal en Grafo Completo K₄: - Para un grafo de 4 nodos donde todos están conectados con todos con distintos pesos, verifica que Kruskal selecciona exactamente 3 aristas de costo mínimo.
3. Paso Límite 3: Maximum XOR con Restricción de Cota Superior (LeetCode 1707): - Investiga cómo ordenar consultas fuera de línea (offline queries) para responder consultas de máximo XOR donde los números permitidos del arreglo deben ser menores o iguales a un límite m.

Navegación final:

• ← Sesión 48: Conjuntos Disjuntos (Union-Find / DSU): Optimizaciones de Rango y Compresión de Caminos
• Sesión 50: Trapping Rain Water (CTCI 17.21): Two Pointers vs Monotonic Stack →
• Glosario Maestro
• Guía de Diagramas de Arquitectura