Sesión 04: Cracking the Coding Interview (Capítulo 1, Parte 2) — Hash Maps, Tablas Hash y Análisis de Frecuencia#

Navegación rápida:

• ← Sesión 03: Memoria, Arrays y Strings
• Sesión 05: Técnica de Dos Punteros →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 50-65 minutos.
• Código fuente compilado y probado: practica-rust/dia_04.rs

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

Las Tablas Hash son la navaja suiza de las entrevistas técnicas, permitiendo reducir complejidades de O(N²) a O(N). Consulta el Glosario Maestro.

Tabla Hash / Diccionario (HashMap<K, V>)#

• (a) En palabras simples (intuición): Un guardarropa con cientos de perchas numeradas. Entregas tu boleto (clave), una fórmula matemática calcula al instante el número de percha exacto y te devuelven tu abrigo (valor) en 1 segundo sin buscar percha por percha.
• (b) Definición técnica paso a paso: Estructura de datos asociativa que implementa una interfaz de mapa clave-valor. Transforma la clave mediante una función matemática de hash en un número entero, el cual se proyecta mediante la operación módulo (±od M) a un índice dentro de un arreglo de casillas o cubetas (buckets), logrando acceso, inserción y eliminación en O(1) tiempo promedio.
• (c) Cómo funciona en Rust (memoria y tipos): La biblioteca estándar de Rust utiliza la arquitectura Swiss Tables (basada en hashbrown). Mantiene una tabla de bytes de control (1 byte por casilla) que aprovecha instrucciones vectoriales SIMD de la CPU para comprobar hasta 16 casillas simultáneamente en un solo ciclo de reloj.
• (d) Error típico de Junior: Creer que el acceso a un HashMap es O(1) estricto garantizado. Si la función hash es deficiente o sufre de colisiones masivas, el rendimiento se degrada a O(N) en el peor caso.

Función Hash y Colisiones#

• (a) En palabras simples (intuición): Una trituradora matemática que toma cualquier texto o número y lo convierte en un código numérico fijo. Si dos palabras distintas arrojan por mala suerte el mismo número, tenemos un "choque" o colisión.
• (b) Definición técnica paso a paso: Una función determinista h(k): K → ℤ que mapea datos de longitud arbitraria a enteros de longitud fija. Una colisión ocurre cuando k₁ ≠ k₂, pero h(k₁) ≡ h(k₂) ±od M.
• (c) Cómo funciona en Rust (memoria y tipos): Por defecto, Rust usa SipHash 1-3, una función criptográficamente segura resistente a ataques de denegación de servicio (HashDoS Attack). Aunque es ultra-segura, para algoritmos competitivos se puede usar FxHash o AHash que operan a velocidades de GHz.
• (d) Error típico de Junior: Usar claves mutables o tipos que modifican su valor de hash mientras residen dentro de la tabla, corrompiendo la capacidad de encontrar el elemento posteriormente.

API Entry en Rust (entry().or_insert())#

• (a) En palabras simples (intuición): En lugar de preguntar al bibliotecario "¿está el libro?" y luego volver a hacer la fila para decirle "si está, ponle un sello", haces todo en una sola visita al mostrador.
• (b) Definición técnica paso a paso: Mecanismo ergonómico de Rust para operaciones de "inspeccionar o insertar" (upsert). Realiza el cálculo del hash y la búsqueda en la tabla exactamente una sola vez, retornando una referencia mutable directa al valor alojado dentro de la cubeta.
• (c) Cómo funciona en Rust (memoria y tipos): La instrucción *map.entry(key).or_insert(0) += 1 evalúa el enum Entry::Occupied o Entry::Vacant. Evita duplicar el costo del hash y las lecturas en memoria RAM.
• (d) Error típico de Junior: Escribir en Rust el patrón estilo Python if map.contains_key(&k) { map.get_mut(&k)... } else { map.insert(k, 1); }, realizando dos o tres búsquedas de hash completas e innecesarias.

Invariante de Palíndromo en Frecuencia#

• (a) En palabras simples (intuición): Para armar una palabra simétrica como "radar" o "reconocer", cada letra debe tener una pareja gemela idéntica (frecuencia par), excepto a lo sumo una letra central solitaria si la longitud total es impar.
• (b) Definición técnica paso a paso: Una cadena puede reordenarse como palíndromo si y solo si la cantidad de caracteres con frecuencia de aparición impar es estrictamente ≤ 1.
• (c) Cómo funciona en Rust (memoria y tipos): Podemos rastrear esta paridad con una sola variable de 32 bits u32 mediante operaciones de bits XOR (bitmask ^= 1 << shift). Al final, verificar si a lo sumo un bit está encendido se resuelve con la fórmula matemática (v & (v - 1)) == 0 en 1 ciclo de CPU.
• (d) Error típico de Junior: Generar todas las permutaciones posibles de la cadena (O(N!)) y verificar una por una si alguna es palíndromo, provocando un desbordamiento temporal inmanejable.

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

El Algoritmo Two Sum: De O(N²) a O(N) en Una Pasada#

Problema (LeetCode 1): Dado un arreglo nums y un entero target, encuentra los dos índices cuya suma sea igual a target.

Enfoque de Fuerza Bruta (O(N²)):#

Compara cada elemento nums[i] con todos los demás elementos nums[j]:

for i in 0..n {
    for j in (i + 1)..n {
        if nums[i] + nums[j] == target { return Some((i, j)); }
    }
}

Esto realiza (N(N-1)) / (2) comparaciones. Si N = 100,000, son 5,000,000,000 operaciones.

Enfoque Óptimo con Tabla Hash en Una Sola Pasada (O(N)):#

Por álgebra elemental:

Llamamos a target - nums[i] el complemento. Conforme recorremos el arreglo:

1. Calculamos el complemento del número actual: complemento = target - num.
2. Preguntamos a la Tabla Hash si ya ha visto ese complemento en iteraciones previas: - Si SÍ: ¡Encontramos la pareja! Retornamos el índice guardado en el mapa y el índice actual i. - Si NO: Guardamos el número actual y su índice en el mapa: map.insert(num, i).

Cada consulta e inserción toma O(1) promedio. Recorremos el arreglo una sola vez: tiempo total O(N).

3. Visualización Paso a Paso y Gráfica de Memoria en Rust#

Flujo de Análisis de Frecuencia con entry()#

Consulta la visualización vectorial de arquitectura:

• Gráfico SVG: ![Visualización del Día 04 y Memoria en Rust](../diagrams/sesiones/dia_04.svg)
• Enlace al código fuente Mermaid: Fuente Mermaid

flowchart LR
    IN["Texto 'banana'"] --> FOR["Para cada char c"]
    FOR --> ENTRY["counts.entry(c).or_insert(0)"]
    ENTRY --> INC["*val += 1 (Incremento directo)"]
    INC --> OUT["Resultado final: { 'a': 3, 'n': 2, 'b': 1 }"]

Visualización Cuadro por Cuadro de Memoria: Two Sum#

Entrada: nums = [2, 11, 7, 15], target = 9.

ESTADO INICIAL:
map = {} (vacío en Heap)

PASO 1 (i = 0):
- Elemento actual: nums[0] = 2.
- Complemento requerido: 9 - 2 = 7.
- ¿Está 7 en map? -> NO.
- Acción: map.insert(2, 0).
- Estado Heap: { 2: 0 }

PASO 2 (i = 1):
- Elemento actual: nums[1] = 11.
- Complemento requerido: 9 - 11 = -2.
- ¿Está -2 en map? -> NO.
- Acción: map.insert(11, 1).
- Estado Heap: { 2: 0, 11: 1 }

PASO 3 (i = 2):
- Elemento actual: nums[2] = 7.
- Complemento requerido: 9 - 7 = 2.
- ¿Está 2 en map? -> ¡SÍ! Su índice es map[2] = 0.
- Retorno inmediato: Some((0, 2)).
Termina en apenas 3 pasos sin necesidad de examinar el resto del arreglo.

4. Implementación Canónica en Rust + Comparativa con Python#

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

//! Implementación canónica de Hash Maps y análisis de frecuencia en Rust.
//! Compilable y verificable con `rustc --test`.

use std::collections::HashMap;

/// CTCI 1.2: Verifica si s1 y s2 son permutaciones (anagramas).
pub fn check_permutation_anagram(s1: &str, s2: &str) -> bool {
    if s1.len() != s2.len() {
        return false;
    }

    let mut counts = HashMap::new();
    for c in s1.chars() {
        *counts.entry(c).or_insert(0) += 1;
    }

    for c in s2.chars() {
        match counts.get_mut(&c) {
            Some(count) => {
                if *count == 0 {
                    return false;
                }
                *count -= 1;
            }
            None => return false,
        }
    }

    true
}

/// LeetCode 1: Two Sum en una sola pasada O(N).
pub fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    let mut map = HashMap::with_capacity(nums.len());

    for (i, &num) in nums.iter().enumerate() {
        let complement = target - num;
        if let Some(&prev_idx) = map.get(&complement) {
            return Some((prev_idx, i));
        }
        map.insert(num, i);
    }

    None
}

/// CTCI 1.4: Permutación de palíndromo mediante bit vector O(1) espacio auxiliar.
pub fn is_palindrome_permutation(s: &str) -> bool {
    let mut bit_vector: u32 = 0;

    for c in s.chars() {
        if c.is_alphabetic() {
            let lower = c.to_ascii_lowercase();
            if lower.is_ascii_lowercase() {
                let shift = (lower as u8 - b'a') as u32;
                bit_vector ^= 1 << shift; // Alterna el bit con XOR
            }
        }
    }

    // A lo sumo 1 bit encendido: (v & (v - 1)) == 0
    (bit_vector & bit_vector.saturating_sub(1)) == 0
}

/// LeetCode 49: Agrupación de anagramas con clave ordenada.
pub fn group_anagrams(words: &[String]) -> Vec<Vec<String>> {
    let mut map: HashMap<String, Vec<String>> = HashMap::new();

    for word in words {
        let mut chars: Vec<char> = word.chars().collect();
        chars.sort_unstable();
        let key: String = chars.into_iter().collect();
        map.entry(key).or_default().push(word.clone());
    }

    map.into_values().collect()
}

/// LeetCode 49 Optimizado O(N * K): Clave mediante array de frecuencia [u8; 26].
pub fn group_anagrams_frequency(words: &[String]) -> Vec<Vec<String>> {
    let mut map: HashMap<[u8; 26], Vec<String>> = HashMap::new();

    for word in words {
        let mut counts = [0u8; 26];
        for b in word.bytes() {
            if b.is_ascii_lowercase() {
                counts[(b - b'a') as usize] += 1;
            }
        }
        map.entry(counts).or_default().push(word.clone());
    }

    map.into_values().collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_check_permutation_anagram() {
        assert!(check_permutation_anagram("anagram", "nagaram"));
        assert!(!check_permutation_anagram("rat", "car"));
    }

    #[test]
    fn test_two_sum() {
        let nums = [2, 7, 11, 15];
        assert_eq!(two_sum(&nums, 9), Some((0, 1)));
    }

    #[test]
    fn test_is_palindrome_permutation() {
        assert!(is_palindrome_permutation("Tact Coa"));
        assert!(!is_palindrome_permutation("hello"));
    }
}

Implementación Canónica en Python (practica/dia_04_hash_tables_frequency.py)#

from collections import defaultdict
from typing import List, Tuple, Optional

def check_permutation_anagram(s1: str, s2: str) -> bool:
    if len(s1) != len(s2):
        return False
    counts = defaultdict(int)
    for c in s1:
        counts[c] += 1
    for c in s2:
        counts[c] -= 1
        if counts[c] < 0:
            return False
    return True

def two_sum(nums: List[int], target: int) -> Optional[Tuple[int, int]]:
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return None

5. Las 3 Trampas Clásicas en Entrevistas#

1. Usar el Mismo Elemento Dos Veces en Two Sum: - En una solución ingenua con HashMap de dos pasadas (llenar el mapa primero y luego consultar), si nums = [3, 2, 4] y target = 6, al evaluar el primer 3, el complemento es 6 - 3 = 3. Si no compruebas i != map[complement], retornarás erróneamente (0, 0). El patrón de una sola pasada previene este error por construcción, pues el número actual aún no se ha insertado.
2. Ignorar Espacios y Mayúsculas/Minúsculas en Permutaciones de Palíndromos: - "Tact Coa" es permutación de "taco cat". Debes normalizar con .to_ascii_lowercase() y filtrar espacios o signos de puntuación.
3. El Costo Asintótico de la Clave en Group Anagrams: - Ordenar cada palabra cuesta O(K log K). Para palabras muy largas, usar una tupla o array de frecuencias de tamaño 26 ([u8; 26]) reduce el tiempo por palabra a O(K) lineal.

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

7. Puente a LeetCode y Práctica de Código#

1. LeetCode 1 — Two Sum (Easy): - Implementa la versión de una sola pasada con HashMap::with_capacity(nums.len()).
2. LeetCode 242 — Valid Anagram (Easy): - Resuelve comparando frecuencias con tabla o array de conteo.
3. LeetCode 49 — Group Anagrams (Medium): - Implementa la variante con clave ordenada y la variante con clave de frecuencia [u8; 26].

Navegación:

• ← Volver a Sesión 03: Memoria, Arrays y Strings
• Avanzar a Sesión 05: Técnica de Dos Punteros →