Sesión 34: Simulacro Completo de Entrevista FAANG Onsite (60 Minutos)#

Navegación rápida:

• ← Sesión 33: Evaluación — Grafos, BFS y Dijkstra
• Sesión 35: Examen Global de Consolidación Semanas 1 a 4 →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_34.rs

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

En esta sesión evaluamos la madurez técnica, disciplina arquitectónica y comunicación bajo presión simulando una ronda técnica real de nivel FAANG (Google, Meta, Amazon, Apple, Netflix). Consulta el Glosario Maestro y la Guía de Diagramas.

Política de Desalojo LRU (Least Recently Used)#

• (a) En palabras simples (intuición): El escritorio de tu oficina. Si la mesa se llena de papeles y necesitas poner una carpeta nueva, tomas el documento que lleva más tiempo sin que nadie lo toque ni lo lea y lo mandas al archivador general.
• (b) Definición técnica paso a paso: Estrategia de reemplazo de memoria caché que desaloja el elemento cuyo último acceso temporal (lectura o escritura) es el más antiguo en la historia del sistema. Exige registrar el orden cronológico de uso de cada clave en tiempo constante O(1).
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa combinando un HashMap<i32, usize> que asocia cada clave al índice de su nodo en una Arena vectorial Vec<Node>, permitiendo acceder y reordenar punteros dobles en O(1) sin asignaciones dinámicas repetitivas.
• (d) Error típico de Junior: Usar un vector simple o una lista simplemente enlazada; mover un elemento al frente toma O(N) tiempo lineal, violando el contrato de diseño de latencia ultra-baja.

Arena Indexing para Listas Doblemente Enlazadas en Safe Rust#

• (a) En palabras simples (intuición): Un hotel de habitaciones numeradas del 0 al 100. En lugar de que cada huésped tenga que memorizar la dirección postal del siguiente, en su puerta tiene un cartel que dice: "El siguiente es la habitación 4, el anterior es la habitación 2".
• (b) Definición técnica paso a paso: Patrón de diseño donde los nodos de una estructura enlazada residen contiguos dentro de un único vector plano Vec<Node>. Los punteros no son direcciones de memoria crudas ni referencias Rc<RefCell<Node>>, sino enteros escalares usize (Option<usize>).
• (c) Cómo funciona en Rust (memoria y tipos): Cumple al 100% las reglas de propiedad del Borrow Checker en Safe Rust: no requiere código inseguro (unsafe), evita fugas cíclicas de memoria y optimiza el uso de la línea de caché del procesador.
• (d) Error típico de Junior: Intentar implementar listas doblemente enlazadas con referencias prestadas cruzadas &'a mut Node, provocando un bloqueo total por incompatibilidad con el modelo de propiedad de Rust.

Nodos Centinela Permanentes (Dummy Head & Dummy Tail)#

• (a) En palabras simples (intuición): Dos sujetalibros fijos atornillados a los extremos de una repisa. Puedes poner y quitar libros entre ellos con total comodidad sin temer que el primer o el último libro se caigan al suelo por no tener apoyo.
• (b) Definición técnica paso a paso: Dos nodos ficticios situados en los extremos de la lista doblemente enlazada (head en el índice 0 y tail en el índice 1). Nunca contienen datos reales de usuario y garantizan que todo nodo útil siempre tenga un predecesor válido (prev) y un sucesor válido (next), reduciendo las operaciones de inserción y extracción a 4 asignaciones sin condicionales if.
• (c) Cómo funciona en Rust (memoria y tipos): Se inicializan al crear la caché: nodes[0].next = Some(1); nodes[1].prev = Some(0);.
• (d) Error típico de Junior: Manejar cabezas y colas opcionales que pueden ser None, llenando el código de validaciones defensivas propensas a errores de puntero nulo.

Orden Topológico en Grafos Acíclicos Dirigidos (DAG)#

• (a) En palabras simples (intuición): El árbol de habilidades de un videojuego. No puedes aprender el hechizo "Tormenta de Fuego" sin haber dominado antes "Chispa" y "Bola de Fuego". El orden topológico es la lista ordenada de habilidades que respeta todas las dependencias sin contradecir ninguna regla.
• (b) Definición técnica paso a paso: Ordenamiento lineal de los vértices de un grafo dirigido G = (V, E) tal que para cada arista dirigida u → v, el vértice u aparece estrictamente antes que v en la secuencia. Solo existe si y solo si el grafo es estrictamente acíclico (DAG).
• (c) Cómo funciona en Rust (memoria y tipos): Algoritmo de Kahn basado en una cola FIFO VecDeque<usize> y un arreglo de enteros in_degrees: Vec<usize>.
• (d) Error típico de Junior: Invertir la orientación de las dependencias (tratar el prerrequisito como dependiente), generando un orden inverso.

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

Por Qué la Dupla HashMap + Doubly Linked List es la Única Estructura O(1) para LRU#

Analicemos los requisitos estrictos de un LRU Cache:

1. get(key) debe buscar un valor en tiempo constante O(1). - Para buscar en O(1), la única opción viable es una Tabla Hash.
2. Cada vez que se lee o escribe una clave, debe promoverse al estado de "más recientemente usada" (MRU) en O(1). - Si usáramos un arreglo continuo (Vec), mover un elemento arbitrario al frente requiere desplazar todos los demás elementos hacia la derecha, tomando tiempo lineal O(N). - En una lista simplemente enlazada, para desconectar un nodo necesitamos conocer su predecesor, lo que exige recorrer la lista desde el inicio en O(N).
3. Al saturar la capacidad, el elemento "menos recientemente usado" (LRU) debe identificarse y eliminarse en O(1). - Si no tenemos un enlace directo a la cola, encontrar el último nodo toma O(N).

La Síntesis Óptima:

• El Hash Map almacena key -> nodo_index en O(1).
• La Lista Doblemente Enlazada permite:
• Desconectar cualquier nodo en O(1) gracias a que conoce a su prev y a su next.
• Insertar cualquier nodo justo tras el centinela head en O(1).
• Extraer el nodo antes de tail (el LRU) en O(1) sin recorrer la lista.

Ambas estructuras trabajan en perfecta simbiosis: el Hash Map otorga el acceso instantáneo y la Lista Doble gobierna la cronología temporal.

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

Arquitectura de Memoria de LRU Cache (Arena + HashMap)#

flowchart LR
    MAP["HashMap<br/>key -> index"]
    HEAD["Centinela Head (0)"] <--> N1["Nodo 1 (key=3, val=30)<br/>MRU"]
    N1 <--> N2["Nodo 2 (key=1, val=10)"]
    N2 <--> TAIL["Centinela Tail (1)<br/>LRU"]
    MAP -.->|"key 3"| N1
    MAP -.->|"key 1"| N2

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

Ejecución de operaciones sobre LRUCache::new(2):

STACK                                            HEAP
+-------------------------------+               +--------------------------------------+
| Frame LRUCache                |               | nodes: Vec<Node>                     |
|   capacity: 2                 |               | [ 0: Head(next=1), 1: Tail(prev=0) ] |
|   map: HashMap<i32, usize> ---+-------------->+--------------------------------------+
|   free_slots: Vec<usize>      |               | map: { }                             |
+-------------------------------+               +--------------------------------------+

1. put(1, 10):
- Crea nodo en index 2 con key=1, val=10.
- attach_after_head(2):
  Head(0) <---> Node(2: key=1) <---> Tail(1)
- map: { 1: 2 }

2. put(2, 20):
- Crea nodo en index 3 con key=2, val=20.
- attach_after_head(3):
  Head(0) <---> Node(3: key=2) <---> Node(2: key=1) <---> Tail(1)
- map: { 1: 2, 2: 3 }

3. get(1):
- Busca 1 en map -> index 2.
- move_to_head(2):
  Head(0) <---> Node(2: key=1) <---> Node(3: key=2) <---> Tail(1)
- Retorna Some(10).

4. put(3, 30) -> ¡CAPACIDAD SUPERADA (3 > 2)!:
- Desaloja nodo antes de Tail: pop_tail() extrae index 3 (key 2).
- Elimina key 2 del map: map.remove(&2).
- free_slots.push(3) para reciclar memoria.
- Asigna nuevo nodo reutilizando slot 3 (key=3, val=30).
- attach_after_head(3):
  Head(0) <---> Node(3: key=3) <---> Node(2: key=1) <---> Tail(1)
- map: { 1: 2, 3: 3 }

4. Las 3 Trampas Clásicas en Entrevistas#

1. Olvidar Remover la Clave del HashMap al Desalojar el Nodo LRU: - Extraer el nodo de la lista doblemente enlazada pero olvidar hacer map.remove(&evicted_key). El mapa acumulará referencias obsoletas a índices reciclados, causando corrupción de datos en operaciones futuras.
2. No Reconectar Punteros al Actualizar una Clave Existente: - Al invocar put(key, new_val) sobre una clave que ya existe en la caché, actualizar solo el valor numérico sin mover el nodo al frente (move_to_head). El elemento recién escrito quedará falsamente marcado como viejo y será desalojado prematuramente.
3. No Retornar Vector Vacío Ante Dependencias Cíclicas en Course Schedule: - Si existe un ciclo (0 -> 1 y 1 -> 0), el algoritmo de Kahn procesará 0 cursos porque ninguno tiene in-degree 0. Si el código retorna order sin verificar order.len() == num_courses, retornará un arreglo incompleto que induce a error.

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

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

//! Día 34: Simulacro Completo de Entrevista FAANG Onsite en Rust.
use std::collections::{HashMap, VecDeque};

#[derive(Debug, Clone)]
struct Node {
    key: i32,
    val: i32,
    prev: Option<usize>,
    next: Option<usize>,
}

pub struct LRUCache {
    capacity: usize,
    nodes: Vec<Node>,
    free_slots: Vec<usize>,
    map: HashMap<i32, usize>,
}

impl LRUCache {
    pub fn new(capacity: usize) -> Self {
        assert!(capacity > 0);
        let mut nodes = Vec::with_capacity(capacity + 2);
        nodes.push(Node { key: 0, val: 0, prev: None, next: Some(1) }); // Head (0)
        nodes.push(Node { key: 0, val: 0, prev: Some(0), next: None }); // Tail (1)

        Self {
            capacity,
            nodes,
            free_slots: Vec::with_capacity(capacity),
            map: HashMap::with_capacity(capacity),
        }
    }

    fn detach(&mut self, idx: usize) {
        let p = self.nodes[idx].prev.unwrap();
        let n = self.nodes[idx].next.unwrap();
        self.nodes[p].next = Some(n);
        self.nodes[n].prev = Some(p);
    }

    fn attach_after_head(&mut self, idx: usize) {
        let old_first = self.nodes[0].next.unwrap();
        self.nodes[idx].prev = Some(0);
        self.nodes[idx].next = Some(old_first);
        self.nodes[0].next = Some(idx);
        self.nodes[old_first].prev = Some(idx);
    }

    fn move_to_head(&mut self, idx: usize) {
        self.detach(idx);
        self.attach_after_head(idx);
    }

    fn pop_tail(&mut self) -> usize {
        let lru_idx = self.nodes[1].prev.unwrap();
        self.detach(lru_idx);
        lru_idx
    }

    pub fn get(&mut self, key: i32) -> Option<i32> {
        if let Some(&idx) = self.map.get(&key) {
            self.move_to_head(idx);
            Some(self.nodes[idx].val)
        } else {
            None
        }
    }

    pub fn put(&mut self, key: i32, val: i32) {
        if let Some(&idx) = self.map.get(&key) {
            self.nodes[idx].val = val;
            self.move_to_head(idx);
        } else {
            let idx = if let Some(free_idx) = self.free_slots.pop() {
                self.nodes[free_idx] = Node { key, val, prev: None, next: None };
                free_idx
            } else {
                let new_idx = self.nodes.len();
                self.nodes.push(Node { key, val, prev: None, next: None });
                new_idx
            };

            self.attach_after_head(idx);
            self.map.insert(key, idx);

            if self.map.len() > self.capacity {
                let evicted_idx = self.pop_tail();
                let evicted_key = self.nodes[evicted_idx].key;
                self.map.remove(&evicted_key);
                self.free_slots.push(evicted_idx);
            }
        }
    }
}

/// LeetCode 210: Algoritmo de Kahn para Course Schedule II en O(V + E).
pub fn find_order_kahn(
    num_courses: usize,
    prerequisites: &[(usize, usize)],
) -> Result<Vec<usize>, &'static str> {
    let mut adj = vec![Vec::new(); num_courses];
    let mut in_degrees = vec![0usize; num_courses];

    for &(dest, src) in prerequisites {
        if dest >= num_courses || src >= num_courses {
            return Err("Out of bounds");
        }
        adj[src].push(dest);
        in_degrees[dest] += 1;
    }

    let mut queue = VecDeque::new();
    for (i, &deg) in in_degrees.iter().enumerate() {
        if deg == 0 {
            queue.push_back(i);
        }
    }

    let mut order = Vec::with_capacity(num_courses);
    while let Some(curr) = queue.pop_front() {
        order.push(curr);
        for &neighbor in &adj[curr] {
            in_degrees[neighbor] -= 1;
            if in_degrees[neighbor] == 0 {
                queue.push_back(neighbor);
            }
        }
    }

    if order.len() == num_courses {
        Ok(order)
    } else {
        Err("Cycle detected")
    }
}

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

from collections import defaultdict, deque
from typing import Dict, List, Optional

class DLinkedNode:
    def __init__(self, key: int = 0, val: int = 0):
        self.key = key
        self.val = val
        self.prev: Optional["DLinkedNode"] = None
        self.next: Optional["DLinkedNode"] = None

class LRUCache:
    """LC 146: LRU Cache con Hash Map + Doubly Linked List en O(1) estricto."""
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache: Dict[int, DLinkedNode] = {}
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add_node(self, node: DLinkedNode) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node: DLinkedNode) -> None:
        p, n = node.prev, node.next
        p.next = n
        n.prev = p

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove_node(node)
        self._add_node(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove_node(node)
            self._add_node(node)
        else:
            new_node = DLinkedNode(key, value)
            self.cache[key] = new_node
            self._add_node(new_node)
            if len(self.cache) > self.capacity:
                tail_node = self.tail.prev
                self._remove_node(tail_node)
                del self.cache[tail_node.key]

def find_order_kahn(num_courses: int, prerequisites: List[List[int]]) -> List[int]:
    """LC 210: Course Schedule II vía Kahn en O(V + E)."""
    adj = defaultdict(list)
    in_degrees = [0] * num_courses

    for dest, src in prerequisites:
        adj[src].append(dest)
        in_degrees[dest] += 1

    queue = deque([i for i in range(num_courses) if in_degrees[i] == 0])
    order = []

    while queue:
        curr = queue.popleft()
        order.append(curr)
        for neighbor in adj[curr]:
            in_degrees[neighbor] -= 1
            if in_degrees[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == num_courses else []

6. Rúbrica Oficial de Calificación del Simulacro (100 Puntos)#

Baremos de Decisión:#

• ≥ 90 pts: Strong Hire (Senior / L5).
• 75 – 89 pts: Hire (Mid-Level / L4).
• 60 – 74 pts: Leaning Hire (Junior / L3).
• < 60 pts: No Hire (Requiere mayor disciplina Paper-First).

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

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

1. LeetCode 146 — LRU Cache (Medium): - Resuelve el problema aplicando Arena Indexing o centinelas limpios.
2. LeetCode 210 — Course Schedule II (Medium): - Implementa el algoritmo de Kahn con detección estricta de ciclos dirigidos.
3. LeetCode 207 — Course Schedule (Medium): - Variante diagnóstica que solo exige validar si es posible terminar todos los cursos (booleano).
4. LeetCode 460 — LFU Cache (Hard): - El escalón superior de diseño de cachés: mapeo de frecuencias y listas dobles concurrentes.

9. Tarea en Papel para Hoy (El Simulacro de 60 Minutos)#

Activa tu cronómetro por exactamente 60 minutos:

1. Toma 2 hojas en blanco.
2. En la Hoja 1: Escribe la especificación de LRU Cache, dibuja los centinelas y resuelve a mano la traza para capacidad 2 con las 5 operaciones descritas en la Sección 2.
3. En la Hoja 2: Modela el grafo de prerrequisitos de Course Schedule II para 4 cursos con ciclo (0 -> 1 -> 2 -> 0) y demuestra en una tabla de in-degrees por qué Kahn detecta la imposibilidad de graduarse.
4. Calcula tu puntuación con la rúbrica oficial de 100 puntos y diagnostica tus áreas de oportunidad.

Navegación:

• ← Volver a Sesión 33: Evaluación — Grafos, BFS y Dijkstra
• Avanzar a Sesión 35: Examen Global de Consolidación Semanas 1 a 4 →