Sesión 18: Cracking the Coding Interview (Capítulo 3, Parte 2) — Stack Min (CTCI 3.2) y SetOfStacks (CTCI 3.3)#

Navegación rápida:

• ← Sesión 17: CTCI Ch3 — Stacks, Queues y Three in One
• Sesión 19: CTCI Ch3 — Queue via Stacks y Sort Stack →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_18.rs

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

En esta sesión profundizamos en el diseño de tipos abstractos de datos avanzados, donde decoramos el comportamiento básico de una pila para soportar consultas analíticas en tiempo constante O(1) y particionamiento físico de memoria. Consulta el Glosario Maestro y la Guía de Diagramas.

Invariante de Mínimo Histórico#

• (a) En palabras simples (intuición): Un registro contable que anota cuál era el récord del precio más bajo en cada día del pasado. Aunque el precio de hoy suba, el récord histórico no se pierde; y si el día del récord se borra, sabemos cuál era el récord anterior.
• (b) Definición técnica paso a paso: Propiedad estructural que garantiza que para cualquier estado o altura h de la pila, la consulta get_min() retorne el valor mínimo de todos los elementos presentes en el rango [0, h] en tiempo estrictamente constante O(1).
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa manteniendo sincronizado un segundo vector o almacenando tuplas con el mínimo acumulado en cada nivel de la pila.
• (d) Error típico de Junior: Usar una sola variable escalar min_val: i32; al desapilar el elemento mínimo, la estructura pierde el conocimiento del mínimo anterior y se ve obligada a recorrer toda la pila en O(N).

Pila Auxiliar de Mínimos (min_stack)#

• (a) En palabras simples (intuición): Una libreta de bolsillo donde solo anotas un número cuando alguien grita un nuevo récord más bajo. Si alguien grita un número más alto, no anotas nada.
• (b) Definición técnica paso a paso: Estructura de datos secundaria de tipo LIFO que almacena de forma monótonamente no creciente los valores mínimos observados. El tope de esta pila siempre refleja el mínimo global actual de la pila principal.
• (c) Cómo funciona en Rust (memoria y tipos): Un Vec<(i32, usize)> en el Heap que solo realiza push cuando el nuevo valor es menor o igual al tope actual, ahorrando asignaciones innecesarias de memoria.
• (d) Error típico de Junior: Usar la condición de inserción estricta val < min_stack.top(), olvidando que ante elementos mínimos duplicados (ej. insertar dos veces el número 3), el segundo no se registrará y el primer pop() corromperá el estado.

Optimización de Duplicados por Frecuencia ((min_val, count))#

• (a) En palabras simples (intuición): En vez de escribir la palabra "oferta" 500 veces seguidas en una lista, escribes "oferta (x500)" en una sola línea.
• (b) Definición técnica paso a paso: Técnica de compresión de memoria (run-length compression) donde cada entrada en la pila de mínimos es una tupla que contiene el valor mínimo y un contador entero de repeticiones continuas.
• (c) Cómo funciona en Rust (memoria y tipos): Se modela como (i32, usize). Si el nuevo elemento es igual al mínimo actual, simplemente se incrementa el contador con *count += 1 sin reservar un nuevo nodo en el vector.
• (d) Error típico de Junior: Asignar memoria para miles de nodos auxiliares redundantes cuando entran secuencias masivas de valores idénticos.

Set of Stacks (Capacidad Dinámica y Platos de Restaurante - CTCI 3.3)#

• (a) En palabras simples (intuición): La torre de platos en la cocina de un restaurante. Si apilas más de 10 platos en una sola torre, la torre se vuelve inestable y peligrosa; por tanto, cuando una torre llega a 10, abres una nueva torre al lado.
• (b) Definición técnica paso a paso: Estructura de datos compuesta que agrupa múltiples sub-pilas de capacidad fija C. Para el cliente exterior se comporta como una única pila unificada con semántica LIFO, pero internamente crea o destruye sub-pilas conforme los datos rebasan o descienden de la capacidad límite.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa como un vector de vectores (Vec<Vec<T>>) en el Heap, gestionando dinámicamente la creación de sub-arreglos y su recolección de memoria cuando quedan vacíos.
• (d) Error típico de Junior: Tratar la estructura como un único arreglo gigante sin encapsular el límite por sub-pila, o no liberar las sub-pilas vacías del vector principal.

Operación pop_at(index) con Rollover vs sin Rollover#

• (a) En palabras simples (intuición): Sacar un plato del medio de una torre intermedia:
• Sin Rollover: Dejas esa torre con un plato menos y continúas trabajando normalmente.
• Con Rollover: Trasladas un plato del fondo de la siguiente torre para llenar el espacio vacío y mantener todas las torres intermedias perfectamente llenas.
• (b) Definición técnica paso a paso:
• Sin Rollover: Desapila directamente de la sub-pila en el índice dado en tiempo O(1). Permite que existan sub-pilas con capacidad parcial en posiciones intermedias.
• Con Rollover (Cascada): Mantiene la invariante estricta de que todas las sub-pilas excepto la última están 100% llenas. Requiere rotar elementos entre sub-pilas en tiempo lineal O(N).
• (c) Cómo funciona en Rust (memoria y tipos): En Rust, la versión sin rollover realiza self.stacks[index].pop() en O(1), y si la sub-pila queda con longitud 0, la remueve del vector con self.stacks.remove(index).
• (d) Error típico de Junior: Prometer al entrevistador que pop_at con rollover opera en O(1); rotar elementos a través de múltiples sub-arreglos es físicamente una operación O(N).

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

La Falacia de la Variable Escalar min_val#

El error más común de un programador principiante al enfrentarse a LeetCode 155 es declarar:

struct BadMinStack {
    stack: Vec<i32>,
    min_val: i32,
}

Analicemos qué ocurre en la memoria física paso a paso:

1. Insertamos 5 → min_val = 5.
2. Insertamos 3 → min_val = 3.
3. Insertamos 7 → min_val = 3.

Hasta aquí todo parece funcionar en O(1). Pero ahora invocamos pop():

• Se retira el número 7. min_val sigue siendo 3.
• Invocamos pop() nuevamente: se retira el número 3.

En este instante preciso, el valor mínimo almacenado en min_val (el 3) acaba de salir de la estructura. ¿Cuál es el nuevo mínimo de los elementos que quedaron en la pila ([5])? La variable escalar min_val no tiene memoria histórica. No tiene forma física de saber qué número era el mínimo antes de que llegara el 3. La única alternativa sería recorrer todos los elementos restantes uno por uno con un bucle for, lo que cuesta O(N) tiempo, destruyendo la especificación de diseño de la entrevista.

Comparativa de Espacio: Tuplas por Nodo vs Pila Auxiliar Comprimida#

Existen dos arquitecturas canónicas correctas para resolver el problema:

El Enfoque B es netamente superior en entornos de producción y demuestra maestría de hardware y eficiencia de memoria ante el entrevistador.

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 18 y Memoria en Rust](../diagrams/sesiones/dia_18.svg)
• Código fuente del diagrama: Fuente Mermaid

Evolución de Estados en MinStack#

flowchart TD
    subgraph S1["Estado 1: push(5), push(3), push(7), push(3)"]
        A1["Pila Principal: [5, 3, 7, 3] (Top=3)"]
        B1["Pila Mínimos: [(5, 1), (3, 2)] (Min=3)"]
    end
    subgraph S2["Estado 2: pop() -> Retira 3"]
        A2["Pila Principal: [5, 3, 7] (Top=7)"]
        B2["Pila Mínimos: [(5, 1), (3, 1)] (Min=3)"]
    end
    subgraph S3["Estado 3: pop() -> Retira 7, pop() -> Retira 3"]
        A3["Pila Principal: [5] (Top=5)"]
        B3["Pila Mínimos: [(5, 1)] (Min=5)"]
    end
    S1 --> S2 --> S3

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

Estructura SetOfStacks con capacidad máxima 2 por sub-pila:

STACK                                            HEAP
+-------------------------------+               
| SetOfStacks                   |               
|   capacity: 2                 |               
|   stacks: Vec<Vec<i32>> ------+--------------> Vector Exterior (Punteros a sub-arreglos)
+-------------------------------+                +------------+------------+------------+
                                                 | [0] Ptr    | [1] Ptr    | [2] Ptr    |
                                                 +-----+------+-----+------+-----+------+
                                                       |            |            |
                                                       v            v            v
                                                  +----+----+  +----+----+  +----+----+
                                                  | 10 | 20 |  | 30 | 40 |  | 50 |    |
                                                  +----+----+  +----+----+  +----+----+
                                                  Sub-pila 0   Sub-pila 1   Sub-pila 2
                                                  (Llena: 2)   (Llena: 2)   (Parcial: 1)

Operación pop_at(1):
1. Accede directamente a stacks[1].
2. Llama a pop() sobre Sub-pila 1 -> Extrae 40.
3. Sub-pila 1 queda con [30] (longitud 1).
4. No queda vacía, por lo que el vector exterior no se altera.
Tiempo: O(1) estricto. Cero copias en memoria.

Operación pop_at(1) nuevamente:
1. Accede a stacks[1]. Extrae 30.
2. Sub-pila 1 queda vacía (len == 0).
3. stacks.remove(1) descarta el buffer vacío del Heap y compacta el vector exterior:
   Vector Exterior:
   +------------+------------+
   | [0] Ptr    | [1] Ptr    |
   +-----+------+-----+------+
         |            |
         v            v
    +----+----+  +----+----+
    | 10 | 20 |  | 50 |    |
    +----+----+  +----+----+

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

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

//! Día 18: Stack Min (CTCI 3.2, LeetCode 155) y Set of Stacks (CTCI 3.3) en Rust.
//! Compilable y verificable con `rustc --test`.

#[derive(Debug, PartialEq, Eq)]
pub enum StackError {
    EmptyStack,
    IndexOutOfBounds,
}

/// CTCI 3.2 / LeetCode 155: Pila con seguimiento del mínimo en tiempo O(1) constante.
#[derive(Debug, Default, Clone)]
pub struct MinStack {
    stack: Vec<i32>,
    min_stack: Vec<(i32, usize)>, // (valor_mínimo, frecuencia)
}

impl MinStack {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn push(&mut self, val: i32) {
        self.stack.push(val);
        match self.min_stack.last_mut() {
            Some((current_min, count)) => {
                if val < *current_min {
                    self.min_stack.push((val, 1));
                } else if val == *current_min {
                    *count += 1;
                }
            }
            None => {
                self.min_stack.push((val, 1));
            }
        }
    }

    pub fn pop(&mut self) -> Result<i32, StackError> {
        let val = self.stack.pop().ok_or(StackError::EmptyStack)?;
        if let Some((current_min, count)) = self.min_stack.last_mut() {
            if val == *current_min {
                *count -= 1;
                if *count == 0 {
                    self.min_stack.pop();
                }
            }
        }
        Ok(val)
    }

    pub fn top(&self) -> Result<i32, StackError> {
        self.stack.last().copied().ok_or(StackError::EmptyStack)
    }

    pub fn get_min(&self) -> Result<i32, StackError> {
        self.min_stack.last().map(|&(m, _)| m).ok_or(StackError::EmptyStack)
    }

    pub fn len(&self) -> usize { self.stack.len() }
    pub fn is_empty(&self) -> bool { self.stack.is_empty() }
}

/// CTCI 3.3: Set of Stacks (Conjunto de pilas de capacidad limitada).
#[derive(Debug, Clone)]
pub struct SetOfStacks<T> {
    stacks: Vec<Vec<T>>,
    capacity: usize,
}

impl<T: Clone> SetOfStacks<T> {
    pub fn new(capacity: usize) -> Self {
        assert!(capacity > 0);
        Self { stacks: Vec::new(), capacity }
    }

    pub fn push(&mut self, val: T) {
        if self.stacks.is_empty() || self.stacks.last().map_or(false, |s| s.len() >= self.capacity) {
            let mut new_stack = Vec::with_capacity(self.capacity);
            new_stack.push(val);
            self.stacks.push(new_stack);
        } else {
            self.stacks.last_mut().unwrap().push(val);
        }
    }

    pub fn pop(&mut self) -> Result<T, StackError> {
        if self.stacks.is_empty() { return Err(StackError::EmptyStack); }
        let val = self.stacks.last_mut().unwrap().pop().ok_or(StackError::EmptyStack)?;
        if self.stacks.last().map_or(false, |s| s.is_empty()) {
            self.stacks.pop();
        }
        Ok(val)
    }

    pub fn pop_at(&mut self, index: usize) -> Result<T, StackError> {
        if index >= self.stacks.len() { return Err(StackError::IndexOutOfBounds); }
        let val = self.stacks[index].pop().ok_or(StackError::EmptyStack)?;
        if self.stacks[index].is_empty() {
            self.stacks.remove(index);
        }
        Ok(val)
    }

    pub fn num_stacks(&self) -> usize { self.stacks.len() }
}

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

    #[test]
    fn test_min_stack() {
        let mut ms = MinStack::new();
        ms.push(5);
        ms.push(3);
        ms.push(7);
        ms.push(3);
        assert_eq!(ms.get_min(), Ok(3));
        assert_eq!(ms.pop(), Ok(3));
        assert_eq!(ms.get_min(), Ok(3));
        assert_eq!(ms.pop(), Ok(7));
        assert_eq!(ms.pop(), Ok(3));
        assert_eq!(ms.get_min(), Ok(5));
    }

    #[test]
    fn test_set_of_stacks() {
        let mut set = SetOfStacks::new(2);
        set.push(10);
        set.push(20);
        set.push(30);
        assert_eq!(set.num_stacks(), 2);
        assert_eq!(set.pop_at(0), Ok(20));
        assert_eq!(set.pop(), Ok(30));
        assert_eq!(set.pop(), Ok(10));
        assert_eq!(set.num_stacks(), 0);
    }
}

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

from typing import List

class MinStack:
    """CTCI 3.2 / LC 155: Seguimiento del mínimo en O(1) tiempo con tuplas de frecuencia."""
    def __init__(self) -> None:
        self._stack: List[int] = []
        self._min_stack: List[List[int]] = []  # [min_val, count]

    def push(self, val: int) -> None:
        self._stack.append(val)
        if not self._min_stack or val < self._min_stack[-1][0]:
            self._min_stack.append([val, 1])
        elif val == self._min_stack[-1][0]:
            self._min_stack[-1][1] += 1

    def pop(self) -> int:
        if not self._stack:
            raise IndexError("pop from empty MinStack")
        val = self._stack.pop()
        if val == self._min_stack[-1][0]:
            self._min_stack[-1][1] -= 1
            if self._min_stack[-1][1] == 0:
                self._min_stack.pop()
        return val

    def top(self) -> int:
        if not self._stack:
            raise IndexError("top from empty MinStack")
        return self._stack[-1]

    def get_min(self) -> int:
        if not self._min_stack:
            raise IndexError("get_min from empty MinStack")
        return self._min_stack[-1][0]

5. Las 3 Trampas Clásicas en Entrevistas#

1. La Fuga del Mínimo Duplicado: - Si no usas un contador de frecuencia o condición <= al apilar en la auxiliar: al insertar 3 y luego otro 3, el segundo no se apilará. Al hacer un primer pop(), se desapilará el único 3 registrado, dejando la pila corrupta con un mínimo falso para el 3 restante.
2. Sub-pilas Fantasma en SetOfStacks: - Olvidar eliminar la sub-pila vacía cuando su último elemento es retirado mediante pop() o pop_at(). Dejar listas vacías [] dentro del vector principal provocará que métodos como peek() o llamadas posteriores fallen con desreferenciación nula o pánico por índice.
3. Manejo de Errores con Valores Mágicos: - Nunca retornes un número mágico como -1 si la pila está vacía. El número -1 puede ser un dato perfectamente válido insertado por el usuario. Emplea siempre Result<T, StackError> en Rust o una excepción de dominio clara en Python.

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

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

1. LeetCode 155 — Min Stack (Medium): - Implementación canónica de la pila con seguimiento del mínimo en O(1).
2. LeetCode 1172 — Dinner Plate Stacks (Hard): - Generalización avanzada de CTCI 3.3 (SetOfStacks) con gestión de índices mediante Heap de huecos disponibles.
3. LeetCode 716 — Max Stack (Hard): - Pila con seguimiento del máximo y soporte para popMax() en tiempo sub-lineal mediante Lista Doblemente Enlazada + TreeMap.

8. Tarea en Papel para Hoy#

Toma una hoja de papel y dibuja el estado en memoria de MinStack (pila principal y pila auxiliar comprimida) tras la siguiente secuencia:

1. push(10)
2. push(2)
3. push(5)
4. push(2)
5. push(1)
6. pop() (muestra cómo se restaura el mínimo a 2).
7. pop() (muestra cómo el contador de 2 se reduce de 2 a 1 sin desapilar de la auxiliar).

Navegación:

• ← Volver a Sesión 17: CTCI Ch3 — Stacks, Queues y Three in One
• Avanzar a Sesión 19: CTCI Ch3 — Queue via Stacks y Sort Stack →