Sesión 10: Cracking the Coding Interview (Capítulo 2, Parte 1) — Runner Technique y Eliminación de Duplicados#

Navegación rápida:

• ← Sesión 09: Recursión y Call Stack
• Sesión 11: Delete Middle Node y Partition en Listas Enlazadas →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 55-70 minutos.
• Código fuente compilado y probado: practica-rust/dia_10.rs

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

La técnica del corredor (Runner Technique) es el equivalente en listas enlazadas a los dos punteros en arreglos. Consulta el Glosario Maestro.

Técnica del Corredor (Runner Technique / Fast & Slow Pointers)#

• (a) En palabras simples (intuición): Dos corredores en una pista de atletismo. O bien uno sale 5 metros antes que el otro (desfasados), o uno corre al doble de velocidad que el otro (2x vs 1x).
• (b) Definición técnica paso a paso: Patrón de diseño para estructuras de datos enlazadas donde dos punteros (fast y slow o p1 y p2) recorren la lista simultáneamente bajo reglas cinemáticas predeterminadas para detectar ciclos, encontrar el punto medio o localizar elementos a distancia k del final en una sola pasada.
• (c) Cómo funciona en Rust (memoria y tipos): Debido a las reglas de préstamo exclusivo (&mut), en Rust no puedes tener dos referencias mutables al mismo nodo. Se resuelve o bien usando referencias inmutables compartidas (&ListNode), o bien desenganchando con take(), o implementando la lista sobre un Arena (Vec<Node> con índices numéricos).
• (d) Error típico de Junior: Avanzar fast = fast.next.next sin verificar previamente si fast.next es nulo, provocando un error de desreferenciación nula (null pointer panic).

Corredores Desfasados por k Nodos (Kth to Last)#

• (a) En palabras simples (intuición): Atas dos personas con una cuerda rígida de exactamente k metros. Cuando la persona delantera llega a la pared del fondo, la persona trasera queda obligatoriamente detenida a k metros de la pared.
• (b) Definición técnica paso a paso: Algoritmo para resolver CTCI 2.2 / LeetCode 19 en O(N) tiempo y O(1) memoria. El puntero P₁ avanza k nodos en solitario. Luego, P₁ y P₂ avanzan al unísono de 1 en 1. Cuando P₁ alcanza el final (None), P₂ apunta exactamente al k-ésimo elemento contando desde el final.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa mediante referencias inmutables compartidas Option<&Box<ListNode>>. No requiere clonar nodos ni alojar datos en el Heap.
• (d) Error típico de Junior: Realizar dos pasadas completas (una para contar la longitud total N y otra para avanzar hasta N - k), cuando el patrón de corredores desfasados lo logra en una sola pasada de lectura.

Ownership en Rust vs Punteros Crudos en C/Python#

• (a) En palabras simples (intuición): En Python o C, diez personas distintas pueden tener una copia de la llave de la misma habitación del hotel. En Rust, hay una sola llave física única: para dársela a otro, debes soltarla tú.
• (b) Definición técnica paso a paso: En C y Python, los nodos son punteros crudos (Node* o referencias PyObject*) que permiten referencias cruzadas o cíclicas sin control del compilador. En Rust, Box<T> impone propiedad exclusiva única. Un nodo solo puede tener un único dueño. Por ende, estructuras como listas doblemente enlazadas o grafos requieren o bien tipos con conteo de referencias (Rc<RefCell<T>>), o bien un arreglo centralizado (Arena).
• (c) Cómo funciona en Rust (memoria y tipos): El modelo de Arena asigna todos los nodos en un Vec<ArenaNode>. Los "punteros" next y prev son simples índices enteros Option<usize>. Esto permite múltiples referencias y mutaciones seguras sin necesidad de unsafe.
• (d) Error típico de Junior: Intentar escribir una lista doblemente enlazada tradicional con Option<Box<ListNode>> en ambos sentidos, lo cual es rechazado por el compilador porque dos nodos se reclamarían como dueños mutuos.

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

La Matemática de Kth to Last: Demostración Formal#

Sea una lista enlazada de longitud total N nodos:

El k-ésimo nodo contando desde el final (k = 1 es el último nodo) se encuentra en la posición absoluta desde el inicio:

El algoritmo de corredores desfasados opera de la siguiente manera:

1. Fase de Desfase: - P₁ avanza k pasos. - Posición de P₁: k. - Posición de P₂: $0$. - La distancia relativa entre ambos es exactamente Δ = k.
2. Fase de Avance Sincronizado: - Ambos punteros avanzan juntos 1 paso a la vez hasta que P₁ sale de la lista (alcanza la posición N). - ¿Cuántos pasos avanzan juntos?
   Pasos restantes para P₁ = N - k
   - Por lo tanto, P₂ también avanza exactamente N - k pasos desde su posición inicial $0$. - Posición final de P₂:
   Posición final = 0 + (N - k) = N - k

¡P₂ termina exactamente en el k-ésimo nodo desde el final! Todo el proceso requirió k + (N - k) = N pasos: Tiempo estrictamente lineal O(N) y memoria auxiliar constante O(1).

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

Flujo de Eliminación de Nodos Duplicados#

Consulta el gráfico vectorial de arquitectura:

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

flowchart LR
    N1["[1]"] --> N2["[2] (visto)"]
    N2 --> N3["[2] (¡DUPLICADO!)"]
    N3 --> N4["[3]"]
    N2 -.->|Bypass / Salto del nodo duplicado| N4

Visualización Cuadro por Cuadro de Memoria: Kth to Last (N = 5, k = 2)#

Lista en Heap: [10] -> [20] -> [30] -> [40] -> [50] -> None. Queremos el penúltimo (k = 2, valor 40).

PASO 1: DESFASAR P1 k POSICIONES (k = 2)
p1 avanza 1 paso: apunta a [20]
p1 avanza 2 pasos: apunta a [30]
p2 apunta al inicio: [10]

Distancia entre p1 y p2: 2 nodos.
[10] -> [20] -> [30] -> [40] -> [50] -> None
 ^               ^
 p2              p1

PASO 2: AVANCE SINCRONIZADO
Iteración 1:
- p1 avanza a [40]
- p2 avanza a [20]
[10] -> [20] -> [30] -> [40] -> [50] -> None
         ^               ^
         p2              p1

Iteración 2:
- p1 avanza a [50]
- p2 avanza a [30]
[10] -> [20] -> [30] -> [40] -> [50] -> None
                 ^               ^
                 p2              p1

Iteración 3:
- p1 avanza a None (fin de lista)
- p2 avanza a [40]
[10] -> [20] -> [30] -> [40] -> [50] -> None
                         ^               ^
                         p2              p1

p1 es None -> Termina el bucle.
p2 apunta a [40]. ¡Retorna Some(40)!

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

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

//! Implementación canónica del patrón Runner y eliminación de duplicados en Rust.
//! Compilable y verificable con `rustc --test`.

use std::collections::HashSet;

#[derive(Debug, PartialEq, Eq, Clone)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

/// CTCI 2.1: Elimina duplicados usando un HashSet en O(N) tiempo y O(N) espacio.
pub fn remove_dups_buffer(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut dummy = Box::new(ListNode { val: 0, next: head });
    let mut seen = HashSet::new();
    let mut curr = &mut dummy;

    while let Some(ref mut next_node) = curr.next {
        if seen.contains(&next_node.val) {
            curr.next = next_node.next.take();
        } else {
            seen.insert(next_node.val);
            curr = curr.next.as_mut().unwrap();
        }
    }

    dummy.next
}

/// CTCI 2.2: Kth to Last con técnica de dos punteros desfasados en O(N) tiempo y O(1) espacio.
pub fn kth_to_last_iterative(head: &Option<Box<ListNode>>, k: usize) -> Option<i32> {
    if k == 0 {
        return None;
    }

    let mut p1 = head.as_ref();

    for _ in 0..k {
        match p1 {
            Some(node) => p1 = node.next.as_ref(),
            None => return None,
        }
    }

    let mut p2 = head.as_ref();
    while let Some(node) = p1 {
        p1 = node.next.as_ref();
        p2 = p2.unwrap().next.as_ref();
    }

    p2.map(|node| node.val)
}

// -----------------------------------------------------------------------------
// Arena Indexing: Lista doblemente enlazada segura en Rust sin punteros crudos
// -----------------------------------------------------------------------------
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ArenaNode {
    pub val: i32,
    pub prev: Option<usize>,
    pub next: Option<usize>,
}

#[derive(Debug, Default, Clone, PartialEq, Eq)]
pub struct ArenaList {
    pub nodes: Vec<ArenaNode>,
    pub head: Option<usize>,
    pub tail: Option<usize>,
}

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

    pub fn insert_tail(&mut self, val: i32) -> usize {
        let new_idx = self.nodes.len();
        let new_node = ArenaNode {
            val,
            prev: self.tail,
            next: None,
        };
        self.nodes.push(new_node);

        if let Some(old_tail) = self.tail {
            self.nodes[old_tail].next = Some(new_idx);
        } else {
            self.head = Some(new_idx);
        }
        self.tail = Some(new_idx);
        new_idx
    }
}

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

    #[test]
    fn test_remove_dups() {
        let mut head = Some(Box::new(ListNode::new(1)));
        head.as_mut().unwrap().next = Some(Box::new(ListNode::new(2)));
        head.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(ListNode::new(1)));

        let cleaned = remove_dups_buffer(head);
        assert_eq!(cleaned.as_ref().unwrap().val, 1);
        assert_eq!(cleaned.as_ref().unwrap().next.as_ref().unwrap().val, 2);
        assert!(cleaned.as_ref().unwrap().next.as_ref().unwrap().next.is_none());
    }
}

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

def remove_dups_buffer(head):
    seen = set()
    dummy = ListNode(0, head)
    curr = dummy
    while curr.next:
        if curr.next.val in seen:
            curr.next = curr.next.next
        else:
            seen.add(curr.next.val)
            curr = curr.next
    return dummy.next

def kth_to_last_iterative(head, k):
    if not head or k <= 0:
        return None
    p1 = head
    for _ in range(k):
        if not p1:
            return None
        p1 = p1.next
    p2 = head
    while p1:
        p1 = p1.next
        p2 = p2.next
    return p2.val

5. Las 3 Trampas Clásicas en Entrevistas#

1. La Definición de k (0-Indexed vs 1-Indexed): - Pregunta siempre al entrevistador: "¿k = 1 representa el último nodo o el penúltimo?". En CTCI, k = 1 es el último nodo. Si asumes 0-indexed sin preguntar, tu código tendrá un error de desfase (off-by-one).
2. k Mayor que la Longitud de la Lista: - Si la lista tiene 3 nodos y piden k = 10, el bucle de desfase de P₁ llegará a None antes de completar k iteraciones. Debes retornar None de inmediato para evitar excepciones de puntero nulo.
3. No Avanzar el Puntero curr al Eliminar Nodos: - Cuando detectas un duplicado y ejecutas curr.next = curr.next.next, no debes avanzar curr, porque el nuevo curr.next que acaba de colocarse también podría ser un duplicado del mismo valor.

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

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

1. LeetCode 19 — Remove Nth Node From End of List (Medium): - Variante directa de CTCI 2.2 combinando corredores desfasados con un nodo centinela (dummy node).
2. LeetCode 83 — Remove Duplicates from Sorted List (Easy): - Eliminación in-place en lista ya ordenada en O(N) tiempo y O(1) espacio.
3. LeetCode 82 — Remove Duplicates from Sorted List II (Medium): - Elimina todos los nodos que tengan números duplicados, conservando solo elementos distintos.

Navegación:

• ← Volver a Sesión 09: Recursión y Call Stack
• Avanzar a Sesión 11: Delete Middle Node y Partition en Listas Enlazadas →