Sesión 17: Cracking the Coding Interview (Capítulo 3, Parte 1) — Stacks, Queues y Three in One (CTCI 3.1)#

Navegación rápida:

• ← Sesión 16: Grokking Ch5 — Hash Tables Avanzadas y Rehashing
• Sesión 18: CTCI Ch3 — Stack Min y Set of Stacks →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_17.rs

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

Entramos al Capítulo 3 de CTCI, donde exploramos las dos estructuras lineales restringidas fundamentales del cómputo. Consulta el Glosario Maestro y la Guía de Diagramas.

Pila (Stack - Semántica LIFO)#

• (a) En palabras simples (intuición): Una pila de platos limpios en una cafetería. El último plato que colocas encima es el primero que alguien toma para servirse comida.
• (b) Definición técnica paso a paso: Tipo abstracto de datos (ADT) lineal con política de acceso LIFO (Last-In, First-Out). Solo admite inserciones (push) y extracciones (pop) en un único extremo denominado tope (top), ambas en tiempo estrictamente constante O(1).
• (c) Cómo funciona en Rust (memoria y tipos): La estructura natural es Vec<T>, donde vec.push(val) y vec.pop() -> Option<T> operan sobre el final contiguo en el Heap en O(1) amortizado sin mover elementos previos.
• (d) Error típico de Junior: Intentar buscar elementos arbitrarios dentro de la pila recorriéndola como si fuera una lista cualquiera, violando la abstracción LIFO.

Cola (Queue - Semántica FIFO)#

• (a) En palabras simples (intuición): La fila de clientes en una taquilla de cine. El primero que llega es el primero en ser atendido y comprar su boleto; los recién llegados se forman al final.
• (b) Definición técnica paso a paso: Tipo abstracto de datos lineal con política FIFO (First-In, First-Out). Los elementos entran exclusivamente por la parte trasera (tail / rear) mediante enqueue y salen exclusivamente por la parte delantera (head / front) mediante dequeue, ambas en tiempo O(1).
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa mediante std::collections::VecDeque<T> (un Ring Buffer de doble extremo). Usar Vec::remove(0) es un antipatrón grave porque desplaza todo el bloque de memoria en O(N).
• (d) Error típico de Junior: Usar un vector plano y extraer el primer elemento con vec.remove(0) en un bucle, degradando un algoritmo lineal a cuadrático O(N²).

Stack Overflow vs Stack Underflow#

• (a) En palabras simples (intuición): Overflow es intentar meter un plato más cuando la estantería ya topa con el techo (se rompe todo). Underflow es intentar tomar un plato cuando la repisa está completamente vacía (manotazo al aire).
• (b) Definición técnica paso a paso:
• Stack Overflow: Condición de error provocada al invocar push() sobre una pila que ha alcanzado su capacidad máxima física asignada en memoria.
• Stack Underflow: Condición de error provocada al invocar pop() o peek() sobre una pila vacía (size == 0).
• (c) Cómo funciona en Rust (memoria y tipos): Se maneja de forma idiomática mediante tipos Result<(), StackError> o retornando Option<T> (None ante Underflow) sin provocar caídas (panics) descontroladas.
• (d) Error típico de Junior: No validar si la pila está vacía antes de consultar el tope, provocando un pánico en tiempo de ejecución por índice fuera de límites.

Three in One (Partición de Memoria Contigua - CTCI 3.1)#

• (a) En palabras simples (intuición): Dividir un único cajón largo de herramientas con dos separadores de madera fijos para tener tres compartimentos independientes sin comprar tres cajones separados.
• (b) Definición técnica paso a paso: Técnica de optimización de memoria donde un único arreglo unidimensional contiguo de tamaño 3 × K se particiona en 3 pilas independientes de capacidad K, calculando sus topes mediante desplazamientos matemáticos en tiempo O(1).
• (c) Cómo funciona en Rust (memoria y tipos): Se almacena en un único Vec<Option<T>> contiguo en el Heap, gestionando los límites con un vector de tamaños sizes: Vec<usize>.
• (d) Error típico de Junior: Crear tres vectores separados (Vec<T>, Vec<T>, Vec<T>), fallando el requisito estricto de la entrevista de utilizar un único arreglo contiguo.

Aritmética de Desplazamientos (Base Offset & Top Index Calculation)#

• (a) En palabras simples (intuición): En un edificio de departamentos idénticos, para saber en qué puerta vive el inquilino 2 del piso 3, multiplicas el número de piso por la cantidad de departamentos por piso y sumas el número de puerta.
• (b) Definición técnica paso a paso: Fórmula matemática que proyecta las coordenadas locales de una sub-pila en el espacio de memoria global:

• (c) Cómo funciona en Rust (memoria y tipos): Se ejecuta en registros enteros de la CPU en un solo ciclo de reloj sin bifurcaciones condicionales complejas.
• (d) Error típico de Junior: Cometer un error de off-by-one sumando o restando 1 incorrectamente, provocando que una pila sobrescriba la celda inicial de la siguiente sub-pila.

Buffer Circular (Ring Buffer - VecDeque en Rust)#

• (a) En palabras simples (intuición): Una calesita o rueda de feria. Cuando llegas al último asiento, el siguiente asiento libre vuelve a ser el primero del principio si ya se desocupó.
• (b) Definición técnica paso a paso: Arreglo de tamaño fijo cuyos extremos conceptuales están conectados. Utiliza aritmética modular (idx + 1) % capacity para hacer avanzar los punteros head y tail de modo que las inserciones y extracciones en ambos extremos ocurran en O(1) sin mover datos en la memoria RAM.
• (c) Cómo funciona en Rust (memoria y tipos): VecDeque<T> asigna un bloque contiguo en el Heap con punteros de índice head y tail. Cuando head o tail tocan el límite superior, envuelven (wrap around) al índice 0.
• (d) Error típico de Junior: Reimplementar una cola usando un vector plano y desplazando elementos manualmente con bucles.

Validador Sintáctico de Paréntesis (LeetCode 20)#

• (a) En palabras simples (intuición): Abrir y cerrar cajas de muñecas rusas. La última caja que abriste debe ser obligatoriamente la primera que cierres; no puedes cerrar la caja exterior si la caja interior sigue abierta.
• (b) Definición técnica paso a paso: Algoritmo clásico de análisis sintáctico (parsing) que utiliza una pila para validar el anidamiento jerárquico de símbolos delimitadores (), {}, [] en tiempo O(N) y espacio O(N).
• (c) Cómo funciona en Rust (memoria y tipos): Al encontrar un delimitador de apertura, se empuja a un Vec<char> el delimitador de cierre correspondiente. Al encontrar un cierre, se extrae el tope y se compara igualdad estricta.
• (d) Error típico de Junior: Usar un simple contador entero para validar cadenas con múltiples tipos de paréntesis, fallando ante secuencias inválidas como "([)]".

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

La Realidad del Silicio: La Pila de Hardware (RSP y Cache Lines)#

A nivel de microprocesador (arquitecturas x86_64 y ARM64), las pilas no son solo un concepto teórico; están grabadas físicamente en los transistores:

1. El registro RSP (Stack Pointer Register) guarda la dirección física del tope de la pila de ejecución.
2. La instrucción de máquina CALL empuja el contador de programa a la pila y salta a la función.
3. La instrucción RET extrae la dirección de retorno del tope y restaura la ejecución.
4. Localidad temporal y espacial: Debido a que una pila siempre trabaja en su extremo superior, las celdas del tope casi siempre residen calientes en la memoria caché L1 de la CPU (1 ciclo de latencia), logrando el rendimiento más rápido posible en cualquier computadora.

Por Qué pop(0) o shift() Destruye el Rendimiento (O(N))#

Cuando tienes un arreglo contiguo en RAM:

Dirección RAM: 0x1000  0x1004  0x1008  0x100C
Elemento:      [ 10  |  20  |  30  |  40  ]

Si llamas a pop(0):

• El elemento 10 es retirado.
• Para mantener la invariante de un arreglo contiguo (donde el índice i está en base + i * 4), la CPU debe invocar una operación de copia en bloque (memmove).
• El valor 20 debe copiarse a 0x1000, 30 a 0x1004, y 40 a 0x1008.
• Si el arreglo contiene 100,000 elementos, la CPU debe reescribir 99,999 enteros en memoria.
• Si ejecutas esto dentro de un bucle que procesa toda la cola, el costo total es:

¡Un algoritmo que debería tardar 2 milisegundos pasa a tardar 45 segundos! Por esto, una cola en producción siempre exige un Ring Buffer o una lista enlazada.

La Matemática de Three in One (CTCI 3.1)#

Queremos alojar K pilas de capacidad C en un único arreglo de tamaño K × C:

• Pila 0 ocupa las celdas físicas: [0, C - 1]
• Pila 1 ocupa las celdas físicas: [C, 2C - 1]
• Pila 2 ocupa las celdas físicas: [2C, 3C - 1]

Para cualquier pila s ∈ [0, K - 1]:

Si la pila s contiene actualmente m elementos (0 ≤ m ≤ C):

• Si m == 0: La pila está vacía (cualquier intento de pop o peek es Stack Underflow).
• Si m == C: La pila está llena (cualquier intento de push es Stack Overflow).
• La posición del elemento en el tope está exactamente en:

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

Diagramas de Arquitectura#

• Gráfico SVG vectorial: ![Visualización del Día 17 y Memoria en Rust](../diagrams/sesiones/dia_17.svg)
• Código fuente del diagrama: Fuente Mermaid

Partición de Memoria en Three in One#

flowchart LR
    subgraph Array["Un Único Arreglo Contiguo de 9 Celdas (Capacidad = 3)"]
        direction LR
        S0_0["[0] 10"] --- S0_1["[1] 20"] --- S0_2["[2] None"]
        S1_0["[3] 100"] --- S1_1["[4] None"] --- S1_2["[5] None"]
        S2_0["[6] 999"] --- S2_1["[7] None"] --- S2_2["[8] None"]
    end
    subgraph Stacks["Vistas Lógicas"]
        P0["Pila 0: [10, 20] (Top=1)"]
        P1["Pila 1: [100] (Top=3)"]
        P2["Pila 2: [999] (Top=6)"]
    end

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

MultiStack con 3 pilas y capacidad 2 por pila (total_cells = 6):

STACK                                            HEAP (Memoria Contigua de 6 Celdas)
+-------------------------------+               +----+----+----+----+----+----+
| FixedMultiStack               |               | 0  | 1  | 2  | 3  | 4  | 5  |
|   num_stacks: 3               |               |None|None|None|None|None|None|
|   stack_capacity: 2           |               +----+----+----+----+----+----+
|   values: Vec<Option<i32>> ---+--------------> [  Pila 0  ][  Pila 1  ][  Pila 2  ]
|   sizes: [0, 0, 0]            |
+-------------------------------+

Paso 1: push(0, 10)
- stack_num = 0, size = 0.
- Offset = 0 * 2 = 0. Nuevo size = 1.
- Top Index = 0 + 1 - 1 = 0.
- Heap[0] = Some(10), sizes = [1, 0, 0].

Paso 2: push(1, 99)
- stack_num = 1, size = 0.
- Offset = 1 * 2 = 2. Nuevo size = 1.
- Top Index = 2 + 1 - 1 = 2.
- Heap[2] = Some(99), sizes = [1, 1, 0].

Paso 3: push(0, 20)
- stack_num = 0, size = 1.
- Offset = 0 * 2 = 0. Nuevo size = 2.
- Top Index = 0 + 2 - 1 = 1.
- Heap[1] = Some(20), sizes = [2, 1, 0].

Paso 4: push(0, 30) -> ¡ERROR!
- sizes[0] es 2, que es igual a stack_capacity (2).
- Retorna Err(StackError::Overflow) sin alterar la memoria.

Paso 5: pop(0)
- Top Index = 0 + 2 - 1 = 1.
- values[1].take() extrae el Some(20) y deja None.
- sizes[0] se decrementa a 1. Retorna Ok(20).

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

Implementación Canónica en Rust (practica-rust/dia_17.rs)#

//! Día 17: Stacks, Queues y Three in One (CTCI 3.1, LeetCode 20) en Rust.
//! Compilable y verificable con `rustc --test`.

#[derive(Debug, PartialEq, Eq)]
pub enum StackError {
    Overflow,
    Underflow,
    InvalidStackNum,
}

/// CTCI 3.1: Tres pilas independientes alojadas en un único buffer contiguo de memoria.
#[derive(Debug, Clone)]
pub struct FixedMultiStack<T> {
    num_stacks: usize,
    stack_capacity: usize,
    values: Vec<Option<T>>,
    sizes: Vec<usize>,
}

impl<T: Clone> FixedMultiStack<T> {
    pub fn new(num_stacks: usize, stack_capacity: usize) -> Self {
        assert!(num_stacks > 0 && stack_capacity > 0);
        let total_cells = num_stacks * stack_capacity;
        Self {
            num_stacks,
            stack_capacity,
            values: vec![None; total_cells],
            sizes: vec![0; num_stacks],
        }
    }

    fn index_of_top(&self, stack_num: usize) -> usize {
        let offset = stack_num * self.stack_capacity;
        offset + self.sizes[stack_num] - 1
    }

    pub fn push(&mut self, stack_num: usize, value: T) -> Result<(), StackError> {
        if stack_num >= self.num_stacks {
            return Err(StackError::InvalidStackNum);
        }
        if self.sizes[stack_num] >= self.stack_capacity {
            return Err(StackError::Overflow);
        }

        self.sizes[stack_num] += 1;
        let top_idx = self.index_of_top(stack_num);
        self.values[top_idx] = Some(value);
        Ok(())
    }

    pub fn pop(&mut self, stack_num: usize) -> Result<T, StackError> {
        if stack_num >= self.num_stacks {
            return Err(StackError::InvalidStackNum);
        }
        if self.sizes[stack_num] == 0 {
            return Err(StackError::Underflow);
        }

        let top_idx = self.index_of_top(stack_num);
        let val = self.values[top_idx].take().expect("Element must exist");
        self.sizes[stack_num] -= 1;
        Ok(val)
    }

    pub fn peek(&self, stack_num: usize) -> Result<&T, StackError> {
        if stack_num >= self.num_stacks {
            return Err(StackError::InvalidStackNum);
        }
        if self.sizes[stack_num] == 0 {
            return Err(StackError::Underflow);
        }

        let top_idx = self.index_of_top(stack_num);
        Ok(self.values[top_idx].as_ref().expect("Element must exist"))
    }

    pub fn is_empty(&self, stack_num: usize) -> Result<bool, StackError> {
        if stack_num >= self.num_stacks {
            return Err(StackError::InvalidStackNum);
        }
        Ok(self.sizes[stack_num] == 0)
    }
}

/// LeetCode 20: Validador de Paréntesis con Semántica LIFO.
pub fn is_valid_parentheses(s: &str) -> bool {
    let mut stack = Vec::new();

    for ch in s.chars() {
        match ch {
            '(' => stack.push(')'),
            '{' => stack.push('}'),
            '[' => stack.push(']'),
            ')' | '}' | ']' => {
                if stack.pop() != Some(ch) {
                    return false;
                }
            }
            _ => return false,
        }
    }

    stack.is_empty()
}

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

    #[test]
    fn test_three_in_one_basic() {
        let mut ms = FixedMultiStack::new(3, 2);
        assert_eq!(ms.push(0, 10), Ok(()));
        assert_eq!(ms.push(0, 20), Ok(()));
        assert_eq!(ms.push(0, 30), Err(StackError::Overflow));
        assert_eq!(ms.pop(0), Ok(20));
        assert_eq!(ms.pop(0), Ok(10));
        assert_eq!(ms.pop(0), Err(StackError::Underflow));
    }

    #[test]
    fn test_valid_parentheses() {
        assert!(is_valid_parentheses("()[]{}"));
        assert!(is_valid_parentheses("{[()]}"));
        assert!(!is_valid_parentheses("([)]"));
    }
}

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

from typing import Generic, List, Optional, TypeVar

T = TypeVar("T")

class FixedMultiStack(Generic[T]):
    """CTCI 3.1: 3 Pilas independientes en 1 solo arreglo contiguo."""
    def __init__(self, stack_capacity: int, num_stacks: int = 3) -> None:
        if stack_capacity <= 0:
            raise ValueError("stack_capacity debe ser mayor que 0")
        self._num_stacks = num_stacks
        self._capacity = stack_capacity
        self._values: List[Optional[T]] = [None] * (num_stacks * stack_capacity)
        self._sizes: List[int] = [0] * num_stacks

    def _index_of_top(self, stack_num: int) -> int:
        return (stack_num * self._capacity) + self._sizes[stack_num] - 1

    def push(self, stack_num: int, value: T) -> None:
        if self._sizes[stack_num] == self._capacity:
            raise IndexError("Stack Overflow")
        self._sizes[stack_num] += 1
        self._values[self._index_of_top(stack_num)] = value

    def pop(self, stack_num: int) -> T:
        if self._sizes[stack_num] == 0:
            raise IndexError("Stack Underflow")
        top_idx = self._index_of_top(stack_num)
        val = self._values[top_idx]
        self._values[top_idx] = None
        self._sizes[stack_num] -= 1
        return val  # type: ignore

    def peek(self, stack_num: int) -> T:
        if self._sizes[stack_num] == 0:
            raise IndexError("Stack Underflow")
        return self._values[self._index_of_top(stack_num)]  # type: ignore

5. Las 3 Trampas Clásicas en Entrevistas#

1. La Trampa de list.pop(0): - En una entrevista donde te piden implementar una cola, usar list.pop(0) en Python o arr.shift() en JavaScript es causal inmediata de rechazo técnico. Provoca una copia continua en memoria de costo O(N) por extracción. Emplea siempre collections.deque o una lista enlazada propia.
2. Stack Underflow y Punteros Negativos: - Invocar pop() o peek() sobre una pila vacía sin validar is_empty() intentará acceder a un índice negativo o desreferenciará un puntero nulo.
3. Falso Balanceo de Paréntesis por Conteo: - Contar aperturas y cierres con un entero (count++, count--) solo sirve si existe un único tipo de paréntesis (()). Si hay múltiples delimitadores (()[]{}), falla ante cadenas como "([)]" donde los conteos coinciden pero el orden LIFO de anidamiento está roto.

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

if stack.pop() != Some(ch) { return false; }

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

1. LeetCode 20 — Valid Parentheses (Easy): - Validador sintáctico fundamental con pila LIFO.
2. LeetCode 232 — Implement Queue using Stacks (Easy): - Implementación de semántica FIFO usando dos pilas LIFO (inbox y outbox).
3. LeetCode 225 — Implement Stack using Queues (Easy): - Simulación de pila LIFO con colas FIFO.
4. LeetCode 155 — Min Stack (Medium): - Introducción directa al tema de la Sesión 18.

8. Tarea en Papel para Hoy#

Toma una hoja de papel y dibuja un arreglo contiguo de longitud 6 para implementar 3 pilas (capacidad 2 por pila):

1. Traza manualmente la siguiente secuencia de operaciones: - push(0, 'A') - push(1, 'X') - push(2, 'Z') - push(0, 'B') - push(0, 'C') (observa cómo se detona el desbordamiento de la pila 0). - pop(1)
2. Anota junto a cada casilla del arreglo su índice absoluto en RAM y a qué sub-pila pertenece.

Navegación:

• ← Volver a Sesión 16: Grokking Ch5 — Hash Tables Avanzadas y Rehashing
• Avanzar a Sesión 18: CTCI Ch3 — Stack Min y Set of Stacks →