Sesión 20: Cracking the Coding Interview (Capítulo 3, Parte 4) — Animal Shelter (CTCI 3.6)#

Navegación rápida:

• ← Sesión 19: CTCI Ch3 — Queue via Stacks y Sort Stack
• Sesión 21: Patrón Monotonic Stack y Consolidación Semana 3 →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_20.rs

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

El problema de diseño del refugio de animales es la prueba canónica de entrevistas para evaluar si un ingeniero sabe combinar requisitos de dominio del negocio con estructuras de datos eficientes de bajo nivel. Consulta el Glosario Maestro y la Guía de Diagramas.

Arquitectura de Colas Duales (Dual Queue System)#

• (a) En palabras simples (intuición): En una clínica veterinaria, tener dos salas de espera separadas: una para perros y otra para gatos. Así los perros no ladran a los gatos y el veterinario puede llamar directamente al perro más antiguo o al gato más antiguo sin tener que revisar a todos los pacientes mezclados.
• (b) Definición técnica paso a paso: Patrón de diseño donde los elementos de un dominio heterogéneo se segregan físicamente en colas FIFO independientes según su clasificación o tipo, eliminando el costo de filtrado secuencial O(N) en consultas específicas por categoría.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa con dos instancias de VecDeque<T> alojadas en el Heap: una para Dog y otra para Cat, operando ambas con push_back y pop_front en tiempo estrictamente constante O(1).
• (d) Error típico de Junior: Usar una sola cola mezclada y recorrerla con un bucle cuando se pide un animal de una especie específica.

Sello de Tiempo Lógico Monótono (Monotonic Logical Timestamp)#

• (a) En palabras simples (intuición): El ticket con número correlativo (ej. "Turno #104") que tomas de la máquina al entrar a un banco. Garantiza matemáticamente quién llegó antes sin importar el reloj de la pared.
• (b) Definición técnica paso a paso: Variable entera monotónicamente creciente (t₀ < t₁ < t₂) que se incrementa en una unidad con cada inserción en el sistema. Proporciona un orden total estricto (strict total order) entre elementos almacenados en colecciones disjuntas.
• (c) Cómo funciona en Rust (memoria y tipos): Un campo entero sin signo current_order: usize en la estructura AnimalShelter que se incrementa con self.current_order += 1 en cada llamada a enqueue.
• (d) Error típico de Junior: Usar el reloj físico del sistema operativo (SystemTime::now()). En pruebas automatizadas ultrarrápidas, múltiples llamadas a enqueue pueden ocurrir en el mismo nanosegundo, produciendo timestamps idénticos y perdiendo el desempate.

Arbitraje FIFO Global (dequeue_any)#

• (a) En palabras simples (intuición): El guardia del banco mira al primer cliente de la fila de ventanilla 1 y al primero de la ventanilla 2; quien tenga el número de turno más bajo pasa primero.
• (b) Definición técnica paso a paso: Proceso de selección en tiempo O(1) que inspecciona únicamente los elementos en el frente (front()) de ambas colas, compara sus timestamps lógicos y desencola el de menor valor numérico.
• (c) Cómo funciona en Rust (memoria y tipos): Se resuelve mediante coincidencia de patrones con tuplas match (self.dogs.front(), self.cats.front()), gestionando exhaustivamente todos los casos posibles (ambas colas llenas, solo perros, solo gatos, o refugio vacío) sin desempaquetados inseguros (unwraps).
• (d) Error típico de Junior: No contemplar el caso en que una de las dos colas esté vacía, provocando una excepción por índice nulo o pánico por unwrap.

Modelado por Enums vs Herencia en Rust#

• (a) En palabras simples (intuición): En vez de crear una jerarquía rígida de clases padre e hijo, crear una etiqueta que dice con precisión si la criatura adoptada es un Perro o un Gato y qué nombre tiene.
• (b) Definición técnica paso a paso: En lenguajes OOP como Java o C++, el problema suele modelarse con una clase base abstracta Animal y subclases Dog y Cat. En Rust idiomático, se prefieren tipos concretos simples combinados con un enum de retorno discriminado AdoptedAnimal { Dog(String), Cat(String) }, garantizando seguridad estática de tipos sin sobrecarga de despacho dinámico (vtable).
• (c) Cómo funciona en Rust (memoria y tipos): Los enums de Rust tienen tamaño fijo en la pila (el tamaño de la variante más grande más 1 byte de discriminador) y cero punteros indirectos a tablas de funciones virtuales.
• (d) Error típico de Junior: Intentar forzar punteros dinámicos con traits tipo Box<dyn Animal>, introduciendo complejidad innecesaria de punteros y pérdida de optimizaciones del compilador.

Encapsulación de Integridad de Invariantes#

• (a) En palabras simples (intuición): Los clientes no pueden ponerle el número a su propio turno al entrar al banco; la máquina expendedora de turnos es la única que tiene permiso de sellar el número correlativo.
• (b) Definición técnica paso a paso: Principio de diseño de software donde los campos críticos que garantizan la corrección matemática de la estructura (como el timestamp order) son estrictamente privados del módulo. La estructura asigna el valor atómicamente durante la inserción.
• (c) Cómo funciona en Rust (memoria y tipos): Los campos de la estructura no se declaran públicos (pub) y los métodos constructores externos no aceptan el orden como parámetro, impidiendo que el cliente corrompa el orden temporal.
• (d) Error típico de Junior: Permitir que el usuario pase el timestamp en el constructor Dog::new("Rex", order), abriendo la puerta a colisiones o falsificación de orden.

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

El Fracaso de la Cola Única: El Desastre del Filtrado O(N)#

Supongamos que un desarrollador junior decide almacenar todos los animales en una única cola FIFO:

Cola Única: [ Perro_1, Perro_2, Perro_3, Gato_1, Perro_4 ]

• Caso 1: dequeue_any(): Excelente. Basta con retirar el frente de la cola (Perro_1) en O(1).
• Caso 2: dequeue_cat(): ¡Aquí colapsa el diseño!

1. El cliente pide un gato. El frente de la cola es un perro.
2. Para llegar al primer gato (Gato_1), la máquina debe desencolar Perro_1, Perro_2 y Perro_3.
3. ¿Dónde guardamos esos perros mientras tanto? Debemos colocarlos en una estructura temporal.
4. Extraemos el gato deseado.
5. Ahora debemos re-insertar los perros en la cola principal. Si los insertamos al final, alteramos su orden de llegada relativo respecto a otros animales que lleguen después. Si intentamos volver a meterlos al frente, invertimos su orden a menos que usemos una estructura secundaria.
6. En el peor caso (un refugio con 10,000 perros y solo 1 gato al fondo), dequeue_cat() cuesta O(N) tiempo y cientos de movimientos de memoria física.

La Solución Canónica: Colas Duales con Timestamp Global#

Al mantener dos colas segregadas:

• Una cola de perros: dogs: VecDeque<Dog>
• Una cola de gatos: cats: VecDeque<Cat>
• Un contador global: current_order: usize

Analicemos las 4 operaciones fundamentales:

1. enqueue_dog(name): - Se incrementa current_order. - Se añade al final de dogs en O(1) estricto.
2. enqueue_cat(name): - Se incrementa current_order. - Se añade al final de cats en O(1) estricto.
3. dequeue_dog(): - Se extrae del frente de dogs en O(1) estricto.
4. dequeue_cat(): - Se extrae del frente de cats en O(1) estricto.
5. dequeue_any(): - Inspeccionamos dogs.front() y cats.front() sin extraer nada. - Si dog.order <= cat.order: extraemos del frente de dogs en O(1). - Si cat.order < dog.order: extraemos del frente de cats en O(1). - Si una de las dos colas está vacía, extraemos directamente de la otra en O(1).

¡Absolutamente todas las operaciones del sistema se ejecutan en O(1) tiempo estricto y sin mover ningún dato de una cola a otra!

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

Línea Temporal de Llegadas y Despacho Dual#

flowchart TD
    subgraph Llegadas["Llegadas con Timestamp Monótono"]
        A["t=1: Perro Rex"] --> B["t=2: Gato Mishi"]
        B --> C["t=3: Perro Bobby"]
        C --> D["t=4: Gato Luna"]
    end
    subgraph Colas["Almacenamiento Segregado en Ring Buffers"]
        DOGS["dogs: [ Rex(t=1), Bobby(t=3) ]"]
        CATS["cats: [ Mishi(t=2), Luna(t=4) ]"]
    end
    subgraph Arbitraje["Arbitraje dequeue_any()"]
        COMP{"¿Rex(t=1) <= Mishi(t=2)?"}
        COMP -- Sí (1 < 2) --> RET["Entrega Rex en O(1)"]
    end
    Llegadas --> Colas --> Arbitraje

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

Refugio tras encolar Rex, Mishi, Bobby, Luna:

STACK                                            HEAP
+-------------------------------+               +--------------------------------------+
| AnimalShelter                 |               | dogs: VecDeque<Dog> (Ring Buffer)    |
|   current_order: 4            |               | [ (Rex, t=1), (Bobby, t=3) ]         |
|   dogs: VecDeque<Dog> --------+-------------->| head: 0, tail: 2, cap: 4             |
|   cats: VecDeque<Cat> --------+------+        +--------------------------------------+
+-------------------------------+      |        +--------------------------------------+
                                       +------->| cats: VecDeque<Cat> (Ring Buffer)    |
                                                | [ (Mishi, t=2), (Luna, t=4) ]        |
                                                | head: 0, tail: 2, cap: 4             |
                                                +--------------------------------------+

Operación 1: dequeue_any()
- dogs.front() = &Rex(t=1)
- cats.front() = &Mishi(t=2)
- 1 <= 2 -> Elige perro.
- dogs.pop_front() -> Retorna Rex.
- El puntero head del Ring Buffer de perros avanza a 1 en O(1). Cero copias.

Operación 2: dequeue_cat()
- cats.pop_front() -> Retorna Mishi(t=2).
- El puntero head del Ring Buffer de gatos avanza a 1 en O(1).

Operación 3: dequeue_any()
- dogs.front() = &Bobby(t=3)
- cats.front() = &Luna(t=4)
- 3 <= 4 -> Retorna Bobby(t=3).

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

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

//! Día 20: Animal Shelter (CTCI 3.6) en Rust.
//! Compilable y verificable con `rustc --test`.

use std::collections::VecDeque;

#[derive(Debug, PartialEq, Eq, Clone)]
pub struct Dog {
    pub name: String,
    pub order: usize,
}

#[derive(Debug, PartialEq, Eq, Clone)]
pub struct Cat {
    pub name: String,
    pub order: usize,
}

#[derive(Debug, PartialEq, Eq, Clone)]
pub enum AdoptedAnimal {
    Dog(String),
    Cat(String),
}

/// CTCI 3.6: Refugio con colas FIFO duales y timestamps monotónicos en O(1).
#[derive(Debug, Default)]
pub struct AnimalShelter {
    dogs: VecDeque<Dog>,
    cats: VecDeque<Cat>,
    current_order: usize,
}

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

    pub fn enqueue_dog(&mut self, name: impl Into<String>) {
        self.current_order += 1;
        self.dogs.push_back(Dog {
            name: name.into(),
            order: self.current_order,
        });
    }

    pub fn enqueue_cat(&mut self, name: impl Into<String>) {
        self.current_order += 1;
        self.cats.push_back(Cat {
            name: name.into(),
            order: self.current_order,
        });
    }

    pub fn dequeue_any(&mut self) -> Option<AdoptedAnimal> {
        match (self.dogs.front(), self.cats.front()) {
            (Some(dog), Some(cat)) => {
                if dog.order <= cat.order {
                    self.dequeue_dog().map(AdoptedAnimal::Dog)
                } else {
                    self.dequeue_cat().map(AdoptedAnimal::Cat)
                }
            }
            (Some(_), None) => self.dequeue_dog().map(AdoptedAnimal::Dog),
            (None, Some(_)) => self.dequeue_cat().map(AdoptedAnimal::Cat),
            (None, None) => None,
        }
    }

    pub fn dequeue_dog(&mut self) -> Option<String> {
        self.dogs.pop_front().map(|d| d.name)
    }

    pub fn dequeue_cat(&mut self) -> Option<String> {
        self.cats.pop_front().map(|c| c.name)
    }

    pub fn is_empty(&self) -> bool {
        self.dogs.is_empty() && self.cats.is_empty()
    }

    pub fn total_animals(&self) -> usize {
        self.dogs.len() + self.cats.len()
    }
}

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

    #[test]
    fn test_animal_shelter_lifecycle() {
        let mut shelter = AnimalShelter::new();
        shelter.enqueue_dog("Rex");
        shelter.enqueue_cat("Mishi");
        shelter.enqueue_dog("Bobby");
        shelter.enqueue_cat("Luna");

        assert_eq!(shelter.dequeue_any(), Some(AdoptedAnimal::Dog("Rex".to_string())));
        assert_eq!(shelter.dequeue_cat(), Some("Mishi".to_string()));
        assert_eq!(shelter.dequeue_any(), Some(AdoptedAnimal::Dog("Bobby".to_string())));
        assert_eq!(shelter.dequeue_any(), Some(AdoptedAnimal::Cat("Luna".to_string())));
        assert_eq!(shelter.dequeue_any(), None);
    }
}

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

from collections import deque
from typing import Optional

class Animal:
    def __init__(self, name: str) -> None:
        self.name = name
        self.order: int = 0

    def is_older_than(self, other: "Animal") -> bool:
        return self.order < other.order

class Dog(Animal): pass
class Cat(Animal): pass

class AnimalShelter:
    """CTCI 3.6: Refugio de Animales con colas FIFO duales y timestamps O(1)."""
    def __init__(self) -> None:
        self._dogs: deque[Dog] = deque()
        self._cats: deque[Cat] = deque()
        self._order: int = 0

    def enqueue(self, animal: Animal) -> None:
        self._order += 1
        animal.order = self._order
        if isinstance(animal, Dog):
            self._dogs.append(animal)
        elif isinstance(animal, Cat):
            self._cats.append(animal)
        else:
            raise TypeError("Especie no admitida")

    def dequeue_any(self) -> Optional[Animal]:
        if not self._dogs and not self._cats:
            return None
        if not self._dogs:
            return self.dequeue_cat()
        if not self._cats:
            return self.dequeue_dog()

        if self._dogs[0].is_older_than(self._cats[0]):
            return self.dequeue_dog()
        return self.dequeue_cat()

    def dequeue_dog(self) -> Optional[Dog]:
        return self._dogs.popleft() if self._dogs else None

    def dequeue_cat(self) -> Optional[Cat]:
        return self._cats.popleft() if self._cats else None

5. Las 3 Trampas Clásicas en Entrevistas#

1. La Colisión de Punteros Nulos (Null References): - Al comparar dogs.front() con cats.front(), no verificar si una de las colas está vacía provocará un fallo inmediato en tiempo de ejecución. El patrón match de Rust obliga matemáticamente a contemplar los 4 casos posibles en tiempo de compilación.
2. Confiar el Timestamp al Cliente: - Nunca permitas que el usuario defina o modifique el timestamp en el constructor. Debe ser inmutable y generado exclusivamente de forma interna y atómica por la estructura AnimalShelter.
3. Usar list.pop(0) en Python o Vec::remove(0) en Rust: - Destruye la complejidad temporal convirtiéndola en O(N) por cada adopción. Emplea siempre VecDeque en Rust o collections.deque 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 649 — Dota2 Senate (Medium): - Simulación idéntica de dos colas FIFO con índices de turno relativos para determinar qué bando domina la votación.
2. LeetCode 346 — Moving Average from Data Stream (Easy): - Manejo de ventanas deslizantes con cola circular FIFO en tiempo O(1).
3. LeetCode 933 — Number of Recent Calls (Easy): - Mantenimiento de eventos dentro de una ventana de tiempo estricta mediante cola FIFO con timestamps.

8. Tarea en Papel para Hoy#

Toma una hoja de papel y dibuja el estado de las colas _dogs y _cats tras la siguiente secuencia:

1. enqueue_cat("Kitten")
2. enqueue_dog("Fido")
3. enqueue_dog("Pluto")
4. enqueue_cat("Garfield")
5. dequeue_dog()
6. dequeue_any()
7. Anota junto a cada animal su orden t y explica por qué la llamada 6 entrega a "Kitten" y no a "Pluto".

Navegación:

• ← Volver a Sesión 19: CTCI Ch3 — Queue via Stacks y Sort Stack
• Avanzar a Sesión 21: Patrón Monotonic Stack y Consolidación Semana 3 →