Sesión 35: Examen Teórico Global de Consolidación de 4 Semanas & Matriz de Seniority#

Navegación rápida:

← Sesión 34: Simulacro de Entrevista FAANG Onsite Completo
Sesión 36: Grokking Ch8 — Greedy, Set Cover e Interval Scheduling →
Glosario Maestro
Guía de Diagramas de Arquitectura
Tiempo estimado de estudio: 75-90 minutos.
Código fuente compilado y probado: practica-rust/dia_35.rs

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

Cerramos la primera gran etapa formativa del curso (Semanas 1 a 5) sintetizando los fundamentos físicos, matemáticos y arquitectónicos que gobiernan la computación eficiente. Consulta el Glosario Maestro y la Guía de Diagramas.

Contigüidad RAM vs Nodos Dispersos en Heap#

(a) En palabras simples (intuición): Casas pegadas en una misma calle vs casas dispersas en diferentes montañas. En la calle contigua, el cartero avanza de casa en casa caminando en línea recta a paso veloz; en las montañas, debe tomar un tren o un sendero diferente para llegar a cada casa, tardando 10 veces más.
(b) Definición técnica paso a paso: Los arreglos y rebanadas (&[T]) residen en direcciones contiguas de memoria RAM; el acceso al elemento $i$ es una operación aritmética pura $O(1)$ de la CPU ( $dir = base + i \times tamaño$ ). Las listas enlazadas y árboles asignan cada nodo en bloques dispersos del Heap, enlazados por punteros de 64 bits.
(c) Cómo funciona en Rust (memoria y tipos): Vec<T> garantiza contigüidad física y reasignación geométrica (duplicando capacidad); Box<Node> representa propiedad exclusiva de un bloque individual en el Heap.
(d) Error típico de Junior: Asumir que porque una lista enlazada tiene inserción teórica en $O(1)$ es más rápida que un Vec; en procesadores reales, la falta de localidad de caché hace que una lista enlazada sea frecuentemente entre 5 y 20 veces más lenta que un vector contiguo.

Localidad Espacial y Temporal de Caché (L1/L2/L3)#

(a) En palabras simples (intuición): Si vas a cocinar y necesitas sal, pimienta y ajo, no vas a la despensa tres veces separadas: traes la bandeja con los tres condimentos juntos en un solo viaje.
(b) Definición técnica paso a paso: Los procesadores modernos no leen bytes individuales de la memoria RAM principal; transfieren bloques completos contiguos llamados líneas de caché (típicamente de 64 bytes). Si el código lee arr[0], los elementos siguientes arr[1], arr[2], etc., ya se cargan automáticamente en la caché L1 ultrarrápida del chip.
(c) Cómo funciona en Rust (memoria y tipos): Las estructuras densas como Vec<T> o la Arena Indexing aprovechan al máximo la línea de caché.
(d) Error típico de Junior: Ignorar el hardware y evaluar el rendimiento de un algoritmo únicamente por su Big-O asintótico sin considerar la arquitectura de memoria.

Amortización Asintótica vs Latencia en Silicio#

(a) En palabras simples (intuición): Pagar la suscripción anual del gimnasio. El día que pagas te cuesta mucho dinero de golpe, pero al dividirlo entre los 365 días del año, el costo diario es prácticamente insignificante.
(b) Definición técnica paso a paso: Análisis de costo promedio garantizado a lo largo de una secuencia de $N$ operaciones. Una operación individual puede ser lenta y costosa (como el redimensionamiento y copia física de un Vec o el rehashing de un HashMap), pero como ocurre con frecuencia decreciente, el costo total dividido entre $N$ está acotado por una constante $O(1)$ .
(c) Cómo funciona en Rust (memoria y tipos): Vec::push es $O(1)$ amortizado; si se conoce de antemano el tamaño, usar Vec::with_capacity(n) elimina incluso los picos individuales de latencia.
(d) Error típico de Junior: Confundir $O(1)$ amortizado con $O(1)$ en el peor caso estricto (worst-case).

Invariante Estructural y Topológica#

(a) En palabras simples (intuición): Una ley de la física que no puede romperse dentro de un universo. Por ejemplo: en una familia, un padre siempre nació antes que su hijo; si encuentras un registro donde el hijo nació antes que el padre, el árbol genealógico está corrupto.
(b) Definición técnica paso a paso: Condición lógica que debe mantenerse verdadera de forma inmutable antes y después de cada operación del algoritmo (ej. en un BST: todo nodo izquierdo $< raíz < nodo derecho$ ; en un Min-Heap: $padre \leq hijos$ ; en Topological Sort: el grado de entrada se reduce a 0 solo cuando todas las dependencias fueron resueltas).
(c) Cómo funciona en Rust (memoria y tipos): El sistema de tipos y la encapsulación de módulos aseguran que los invariantes no puedan ser vulnerados desde código externo.
(d) Error típico de Junior: Modificar el valor de un nodo o de un puntero directamente sin restaurar los invariantes de la estructura, corrompiendo el estado interno.

2. Desglose Conceptual y Matriz Heurística de Decisión#

Cuando te enfrentes a un problema desconocido en una entrevista técnica o en el diseño de un sistema real, utiliza este árbol de decisión mental para identificar el patrón algorítmico óptimo:

DIAGRAMA MERMAID

flowchart TD
    START["¿Qué estructura o relación describe el problema?"] --> CAT1["1. Secuencia Contigua (Arreglo o Cadena)"]
    START --> CAT2["2. Secuencia Enlazada (Punteros next/prev)"]
    START --> CAT3["3. Jerarquía (Árboles Binarios / BST)"]
    START --> CAT4["4. Redes y Dependencias (Grafos)"]

    CAT1 --> Q11{"¿Está ordenado y busca condición monótona?"}
    Q11 -->|Sí| BIN["Búsqueda Binaria O(log N)"]
    Q11 -->|No| Q12{"¿Busca pares, subcadenas o áreas extremas?"}
    Q12 -->|Subcadenas/Ventana| WIN["Sliding Window Dinámica O(N)"]
    Q12 -->|Pares/Convergencia| TP["Two Pointers O(N)"]
    Q12 -->|Siguiente menor/mayor| MONO["Monotonic Stack O(N)"]

    CAT2 --> Q21{"¿La cabeza puede mutar o eliminarse?"}
    Q21 -->|Sí| DUMMY["Centinela (Dummy Node)"]
    CAT2 --> Q22{"¿Detección de ciclos o punto medio?"}
    Q22 -->|Sí| RUNNER["Floyd Tortoise and Hare (2x vs 1x)"]

    CAT3 --> Q31{"¿Validar BST o ancestros?"}
    Q31 -->|Sí| BST["Límites (low, high) / LCA"]
    CAT3 --> Q32{"¿Altura, balance o caminos máximos?"}
    Q32 -->|Sí| POST["DFS Post-Order Bottom-Up O(N)"]

    CAT4 --> Q41{"¿Camino más corto no ponderado?"}
    Q41 -->|Sí| BFS["BFS con Cola FIFO O(V + E)"]
    CAT4 --> Q42{"¿Costos no negativos / Escalas?"}
    Q42 -->|Sin escalas| DIJK["Dijkstra con Min-Heap O((V+E) log V)"]
    Q42 -->|Con escalas/Negativos| BELL["Bellman-Ford O(K * E)"]
    CAT4 --> Q43{"¿Dependencias de tareas / DAG?"}
    Q43 -->|Sí| KAHN["Kahn Topological Sort O(V + E)"]

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

Cuadro Sinóptico de Memoria en Rust: Los 5 Pilares Fundamentales#

TEXT

PILAR 1: ARRAYS CONTIGUOS (Two Pointers)
STACK: [ left: usize, right: usize, target: i32 ]
HEAP:  [ 2, 7, 11, 15 ] (Memoria contigua densa, máxima localidad L1)

PILAR 2: LINKED LISTS (Reconexión In-Place con .take())
STACK: [ prev: Option<Box>, curr: Option<Box> ]
HEAP:  (1) --------> (2) --------> (3) -> None
       (Cada nodo es un Box independiente en Heap, reconexión O(1) auxiliar)

PILAR 3: MONOTONIC STACK (Next Greater Element)
STACK: [ stack: Vec<usize> ]
HEAP:  Vec::with_capacity(N) -> [ idx_0, idx_2, ... ] (Pila de índices)

PILAR 4: BINARY SEARCH TREE (Validación con Límites Hereditarios)
STACK: [ validate(node, low: Option<i64>, high: Option<i64>) ]
HEAP:  TreeNode { val: 5, left: Box(3), right: Box(7) }

PILAR 5: GRAFOS Y BFS (Camino de Mínimos Saltos)
STACK: [ queue: VecDeque<(usize, dist)>, visited: Vec<bool> ]
HEAP:  adj: Vec<Vec<usize>> (Lista de adyacencia contigua plana)

4. Las 3 Trampas Clásicas en Entrevistas de Consolidación#

La Ilusión de Inmediatez (Comenzar a Codificar en los Primeros 60 Segundos): - Empezar a teclear sin dialogar con el entrevistador ni diagramar en papel. En FAANG, esto suele derivar en un "No Hire" por falta de comunicación. Dedica los primeros 5 a 10 minutos a formular preguntas de negocio, identificar restricciones y validar casos borde.
Confundir la Complejidad Espacial del Call Stack con Memoria Constante: - Afirmar que una función recursiva es $O(1)$ de memoria porque no declara arreglos auxiliares. Cada llamada recursiva crea un marco de activación físico en el Call Stack de la CPU, consumiendo $O(H)$ o $O(N)$ espacio.
No Reconocer las Condiciones de Aplicabilidad de los Algoritmos: - Aplicar Two Pointers en un arreglo no ordenado; aplicar Dijkstra en un grafo con pesos negativos; o asumir que una tabla hash siempre resuelve duplicados sin verificar colisiones.

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

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

RUST

//! Día 35: Examen Global de Consolidación de Semanas 1 a 4 en Rust.
use std::collections::VecDeque;

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
pub enum SeniorityLevel {
    Junior,
    MidLevel,
    Senior,
    Staff,
}

pub struct ExamEvaluator;

impl ExamEvaluator {
    pub fn evaluate_score(score: u32, passed_pillars: usize) -> SeniorityLevel {
        match score {
            90..=100 if passed_pillars == 5 => SeniorityLevel::Staff,
            80..=100 => SeniorityLevel::Senior,
            65..=79 => SeniorityLevel::MidLevel,
            _ => SeniorityLevel::Junior,
        }
    }
}

/// Pilar 1: Two Pointers sobre arreglo ordenado en O(N) tiempo y O(1) espacio.
pub fn two_sum_sorted(numbers: &[i32], target: i32) -> Option<(usize, usize)> {
    if numbers.len() < 2 { return None; }
    let mut left = 0;
    let mut right = numbers.len() - 1;

    while left < right {
        let sum = numbers[left] + numbers[right];
        if sum == target {
            return Some((left, right));
        } else if sum < target {
            left += 1;
        } else {
            right -= 1;
        }
    }
    None
}

/// Pilar 5: BFS para camino más corto en grafo no ponderado en O(V + E).
pub fn bfs_shortest_path(num_vertices: usize, edges: &[(usize, usize)], src: usize, dst: usize) -> Option<usize> {
    if src >= num_vertices || dst >= num_vertices { return None; }
    if src == dst { return Some(0); }

    let mut adj = vec![Vec::new(); num_vertices];
    for &(u, v) in edges {
        if u < num_vertices && v < num_vertices {
            adj[u].push(v);
            adj[v].push(u);
        }
    }

    let mut visited = vec![false; num_vertices];
    let mut queue = VecDeque::new();
    visited[src] = true;
    queue.push_back((src, 0usize));

    while let Some((curr, dist)) = queue.pop_front() {
        if curr == dst { return Some(dist); }
        for &neighbor in &adj[curr] {
            if !visited[neighbor] {
                visited[neighbor] = true;
                queue.push_back((neighbor, dist + 1));
            }
        }
    }
    None
}

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

PYTHON

from typing import Dict, List, Optional, Tuple

def evaluate_student_answers(student_answers: Dict[int, str]) -> Dict[str, Any]:
    """Evalúa las respuestas del examen global y clasifica el nivel de seniority."""
    score = sum(4 for ans in student_answers.values() if len(ans.strip()) > 30)
    level = "Staff" if score >= 90 else "Senior" if score >= 80 else "Mid-Level" if score >= 65 else "Junior"
    return {"score": score, "level": level}

6. El Gran Examen Teórico: 25 Preguntas de Active Recall#

Bloque 1: Memoria Física, Hardware y Ejecución (Preguntas 1 a 5)#

Pregunta 1: ¿Por qué el acceso aleatorio a[i] en un arreglo contiguo es físicamente O(1) en memoria RAM?

Respuesta Técnica: Porque la CPU calcula la dirección de memoria exacta mediante una sola operación de aritmética de punteros en hardware: $Dirección = Base + (i \times tamaño_en_bytes)$ . Como la memoria RAM admite direccionamiento directo por bus sin recorrer elementos intermedios, el tiempo de acceso es independiente de $i$ y de $N$ .

Pregunta 2: ¿Qué diferencia física existe entre una lista de Python y un arreglo en C, un Vec<i32> en Rust o un TypedArray de V8?

Respuesta Técnica: Una list de Python almacena un arreglo contiguo de punteros de 64 bits hacia objetos PyObject dispersos en el Heap, requiriendo un salto de desreferenciación (pointer chasing) por cada elemento. Un Vec<i32> en Rust o un TypedArray en V8 almacena bytes binarios densos contiguos sin indirección ni boxing, permitiendo que la CPU cargue múltiples números enteros en una sola línea de caché.

Pregunta 3: ¿Qué compone un Stack Frame en el Call Stack de la CPU y por qué la recursión infinita produce un Stack Overflow?

Respuesta Técnica: Un Stack Frame contiene: (1) la dirección de retorno para el registro RIP/EIP, (2) los argumentos pasados a la función, (3) las variables locales asignadas en el marco, y (4) el puntero al marco anterior (RBP/EBP). Como el tamaño del Call Stack del hilo es finito (típicamente 1 a 8 MB), invocar llamadas recursivas sin condición de parada agota la memoria contigua asignada por el sistema operativo, disparando un fallo de página y la señal de aborto SIGSEGV.

Pregunta 4: ¿Cómo recolecta un motor moderno como V8 una estructura con referencias circulares huérfanas?

Respuesta Técnica: Mediante el algoritmo Mark-and-Sweep (Marcado y Barrido) desde las GC Roots (variables en el Call Stack actual, objetos globales del entorno). Aunque dos objetos se apunten mutuamente formando un ciclo cerrado, si la estructura no tiene ningún camino dirigido alcanzable desde las raíces del recolector, el GC nunca la marcará y será liberada en la fase de barrido.

Pregunta 5: ¿Por qué arr.shift() en JavaScript o list.pop(0) en Python es un antipatrón O(N) para implementar colas?

Respuesta Técnica: Porque al eliminar el elemento en el índice 0 de un arreglo contiguo, todos los $N-1$ elementos restantes deben desplazarse físicamente un casillero hacia la izquierda en la memoria RAM para preservar la contigüidad. Para colas $O(1)$ se debe usar un búfer circular o una estructura basada en nodos (VecDeque).

Bloque 2: Arrays, Strings, Two Pointers y Hash Tables (Preguntas 6 a 10)#

Pregunta 6: ¿Cómo se evita la degradación a O(N^2) al concatenar strings repetidamente dentro de un bucle?

Respuesta Técnica: Como los strings son inmutables, usar s += c crea un nuevo string en el Heap y copia todos los caracteres acumulados en cada iteración ( $1 + 2 + \dots + N = O(N²)$ ). La solución es acumular los fragmentos en un vector dinámico (Vec<char> o Vec<String>) y unirlos al final en una única pasada con .collect::<String>() o ''.join(arr).

Pregunta 7: ¿Qué invariante matemático garantiza que en Container With Most Water (LC 11) siempre se deba descartar la pared más baja?

Respuesta Técnica: El área está delimitada por $(R - L) \times min(h[L], h[R])$ . Si $h[L] < h[R]$ , cualquier contenedor formado por $L$ con otra pared interna $R'$ tendrá un ancho menor ( $R' - L < R - L$ ) y su altura nunca podrá superar a $h[L]$ . Por tanto, es matemáticamente imposible que $L$ forme un área mayor con ninguna otra línea interna.

Pregunta 8: ¿Qué es el factor de carga (alpha = n/m) en una tabla hash y qué sucede en el Rehashing?

Respuesta Técnica: El factor de carga $α = n / m$ es la razón entre la cantidad de elementos insertados ( $n$ ) y el número total de buckets ( $m$ ). Cuando $α$ supera el umbral crítico (típicamente $0.7$), la probabilidad de colisiones se dispara. El Rehashing duplica el arreglo de buckets y recalcula la posición de cada clave existente para reequilibrar la distribución.

Pregunta 9: ¿Cómo resuelve una tabla hash con Open Addressing el problema de las eliminaciones sin romper las cadenas de sondeo?

Respuesta Técnica: Colocando un marcador de lápida (Tombstone o celda eliminada). Al buscar una clave, la sonda lineal continúa su recorrido a través de las lápidas sin detenerse; al insertar una clave nueva, la celda con lápida puede ser reutilizada como espacio disponible.

Pregunta 10: ¿Bajo qué condición estricta es aplicable la técnica de Two Pointers convergentes para encontrar una suma objetivo (Two Sum)?

Respuesta Técnica: El arreglo debe estar estrictamente ordenado de manera monótona. El orden garantiza que si la suma actual es menor que el objetivo, la única forma de incrementarla es avanzar el puntero izquierdo; si es mayor, la única forma de reducirla es retroceder el puntero derecho.

Bloque 3: Linked Lists y Recursión (Preguntas 11 a 15)#

Pregunta 11: ¿Cuál es la función arquitectónica indispensable del Dummy Node (Nodo Centinela)?

Respuesta Técnica: Proveer un predecesor invariable para la cabeza de la lista. Elimina los casos borde donde la cabeza original muta, se invierte, se elimina o la lista está inicialmente vacía, permitiendo que todo el código trate a todos los nodos con una lógica uniforme sin condicionales if.

Pregunta 12: ¿Por qué el algoritmo de Floyd (Liebre y Tortuga) garantiza colisión dentro del ciclo en a lo sumo C pasos?

Respuesta Técnica: Porque en cada iteración la liebre avanza 2 nodos y la tortuga avanza 1 nodo. La distancia relativa entre ambas disminuye exactamente en 1 nodo por iteración ( $Δ = 2 - 1 = 1$ ). Si el ciclo tiene longitud $C$ , la distancia relativa se reduce a cero en a lo sumo $C$ pasos desde que la tortuga ingresa al ciclo.

Pregunta 13: ¿Cómo se invierte una lista simplemente enlazada in-place en O(N) tiempo y O(1) memoria?

Respuesta Técnica: Utilizando tres referencias móviles (prev, curr, nxt). En cada paso: guardamos nxt = curr.next, reorientamos curr.next = prev, avanzamos prev = curr y avanzamos curr = nxt. Al finalizar, prev contiene la nueva cabeza.

Pregunta 14: ¿Por qué CTCI 2.3 (Delete Middle Node) no puede aplicarse si el nodo objetivo es el último nodo de la lista?

Respuesta Técnica: Porque la técnica copia el valor del siguiente nodo (node.val = node.next.val) y salta dicho nodo (node.next = node.next.next). Si el nodo es el último, no existe ningún nodo siguiente del cual copiar información ni al cual reconectar, siendo imposible desvincularlo sin acceso al nodo previo en una lista simplemente enlazada.

Pregunta 15: ¿Cómo se detecta el nodo exacto donde comienza un ciclo en una lista enlazada tras la colisión de Floyd?

Respuesta Técnica: Se reinicia un puntero al inicio de la lista (head) manteniendo el otro puntero en el punto de colisión. Se avanzan ambos punteros simultáneamente a velocidad 1x. El nodo exacto donde vuelven a encontrarse es la entrada física del ciclo (demostrado por $K = nC - M$ ).

Bloque 4: Stacks, Queues y Monotonic Stack (Preguntas 16 a 20)#

Pregunta 16: ¿Cuál es la diferencia fundamental entre una cola basada en listas enlazadas vs un arreglo circular (Ring Buffer)?

Respuesta Técnica: La lista enlazada asigna un nodo en el Heap por cada elemento, generando sobrecarga de punteros y dispersión de memoria. El Ring Buffer preasigna un arreglo contiguo continuo y manipula dos índices (head y tail) con aritmética modular (idx = (idx + 1) % capacity), garantizando $O(1)$ estricto, sin asignaciones intermedias y con excelente localidad de caché.

Pregunta 17: ¿Cómo garantiza una Pila Monótona resolver Next Greater Element en O(N) si tiene un bucle while interno?

Respuesta Técnica: Por análisis amortizado: cada índice entra a la pila una sola vez mediante push y sale de la pila a lo sumo una sola vez mediante pop. El número acumulado total de ejecuciones del bucle while a lo largo de todo el algoritmo está acotado por $N$ , dando una complejidad global $O(N)$ estricta.

Pregunta 18: ¿Por qué en Largest Rectangle in Histogram (LC 84) se necesita un centinela virtual de altura 0 al final?

Respuesta Técnica: Para forzar la extracción de todas las barras restantes que quedaron acumuladas en la pila cuando el histograma tiene tramos monótonamente crecientes. Al procesar altura 0, toda barra en la pila es estrictamente mayor que 0 y calcula su área máxima antes de terminar el algoritmo.

Pregunta 19: ¿Cómo se implementa una cola FIFO utilizando dos pilas LIFO (Stack Queue) con costo O(1) amortizado?

Respuesta Técnica: Se utilizan stack_in (para encolar con push) y stack_out (para desencolar con pop). Cuando se solicita un elemento y stack_out está vacío, se transfieren todos los elementos de stack_in a stack_out invirtiendo su orden. Cada elemento se transfiere exactamente una sola vez, logrando $O(1)$ amortizado por operación.

Pregunta 20: ¿Por qué MinStack logra get_min() en O(1) tiempo sin violar las restricciones de una pila?

Respuesta Técnica: Porque mantiene una pila auxiliar paralela de mínimos (o pares (valor, min_actual)). Cada vez que se inserta un valor $x$ , se almacena $min(x, min_anterior)$ . Al extraer un elemento, su mínimo asociado se descarta en sincronía, permitiendo leer el mínimo histórico en el tope en $O(1)$ sin recorrer la estructura.

Bloque 5: Árboles, BST, Grafos y Algoritmos de Camino Mínimo (Preguntas 21 a 25)#

Pregunta 21: ¿Por qué validar que node.left.val < node.val < node.right.val NO basta para validar un BST?

Respuesta Técnica: Porque la invariante de un BST es una propiedad global del subárbol completo: todos los descendientes en el subárbol izquierdo de un nodo $X$ deben ser menores que $X$ , no solo su hijo inmediato. Se debe propagar un rango abierto de validez $(low, high)$ hacia abajo en la recursión.

Pregunta 22: ¿Cómo logra la reconstrucción de un árbol binario desde Preorder e Inorder (LC 105) un tiempo estrictamente O(N)?

Respuesta Técnica: Precomputando una tabla hash de ${ valor: índice en Inorder }$ en $O(N)$ para consultar en $O(1)$ la posición de la raíz. Las llamadas recursivas reciben únicamente 4 límites enteros (pre_start, pre_end, in_start, in_end) sin copiar memoria física con slicing.

Pregunta 23: ¿Por qué BFS encuentra el camino de menor número de aristas en un grafo no ponderado mientras que DFS no puede garantizarlo?

Respuesta Técnica: Porque BFS explora los vértices de manera radial y concéntrica por capas de distancia uniforme $d = 0, 1, 2, \dots$ utilizando una cola FIFO. El primer instante en que el destino es alcanzado corresponde matemáticamente al camino con menor cantidad de aristas.

Pregunta 24: ¿Cómo detecta el Algoritmo de Kahn (Topological Sort) la presencia de una dependencia circular en un sistema de build?

Respuesta Técnica: El algoritmo solo encola nodos cuyo grado de entrada (in-degree) sea 0. Si existe un ciclo dirigido, los nodos pertenecientes al ciclo conservarán siempre un grado de entrada residual de al menos 1, por lo que nunca entrarán a la cola. Si al vaciarse la cola el total de nodos procesados es menor que $V$ , se confirma la existencia de un ciclo.

Pregunta 25: ¿Por qué Dijkstra asume pesos no negativos (

w \geq 0

) y qué algoritmo se utiliza si existen costos negativos?

Respuesta Técnica: Porque Dijkstra es un algoritmo voraz (greedy): asume que al extraer un nodo del Min-Heap, su distancia acumulada es definitiva. Si existieran pesos negativos, un camino posterior más largo en aristas podría reducir la distancia total, invalidando el estado óptimo. Para grafos con pesos negativos se utiliza Bellman-Ford ( $O(V \cdot E)$ ).

7. Matriz de Autoevaluación de Seniority#

Calcula tu puntuación honesta: 4 puntos por cada pregunta respondida con precisión técnica completa (Total: 100 puntos).

Nivel de Seniority	Rango de Puntos	Dominio Teórico y Arquitectónico	Comportamiento en la Pizarra / Editor
Junior (L3)	0 – 59 pts	Conoce las definiciones de estructuras pero confunde memoria física con abstracción. Confunde Big O temporal con espacial.	Empieza a tipear código de inmediato. Depende de IA o de ensayo y error para que los casos borde pasen.
Mid-Level (L4)	60 – 79 pts	Domina Big O asintótico, Hash Maps, BFS y DFS estándar. Duda en pilas monótonas y algoritmos de grafos avanzados.	Traza casos felices en papel pero suele olvidar casos borde (ciclos, negativos, nulos, overflow de recursión).
Senior (L5)	80 – 94 pts	Plena autonomía. Domina invariantes matemáticos, Monotonic Stack, Kahn, Dijkstra, Divide & Conquer y costos de memoria.	Protocolo Paper-First estricto: diagramas de memoria, tablas de variables y análisis de casos borde antes de codificar.
Staff / Principal (L6+)	95 – 100 pts	Capacidad pedagógica para mentorar y justificar formalmente correctitud algorítmica, localidad en caché L1/L2 y trade-offs.	Modela visualmente el problema en minutos. Sus trazas manuales detectan bugs antes de ejecutar el código.

8. Tarea en Papel para Hoy#

Completa la autoevaluación de las 25 preguntas en tu hoja de papel.
Ubica tu puntaje obtenido en la Matriz de Seniority.
Identifica tus 2 bloques temáticos más débiles y diseña una sesión de repaso de 30 minutos para consolidarlos definitivamente.

Navegación:

← Volver a Sesión 34: Simulacro de Entrevista FAANG Onsite Completo
Avanzar a Sesión 36: Grokking Ch8 — Greedy, Set Cover e Interval Scheduling →