Data Structure & Algorithms
Introducción a las estructuras de datos y los algoritmos: representación, operaciones, restricciones, invariantes, correctitud, complejidad y trade-offs.
Las estructuras de datos definen cómo organizas información. Los algoritmos definen los pasos para consultarla, transformarla o tomar decisiones con ella.
No se estudian para memorizar soluciones de plataformas. Se estudian para aprender a traducir un problema en:
datos
→ operaciones
→ restricciones
→ representación
→ algoritmo
→ correctitud
→ complejidadUna buena solución no es solamente la que funciona con un ejemplo. Debe respetar el contrato, terminar, manejar casos límite y usar recursos adecuados para el tamaño esperado.
Una estructura de datos combina:
Ejemplos:
La misma información puede representarse de varias maneras. La representación correcta depende de las operaciones dominantes.
Un algoritmo es un procedimiento finito y preciso que transforma una entrada en una salida.
Debe tener:
function maximum(values: readonly number[]): number | undefined {
if (values.length === 0) return undefined;
let best = values[0];
for (let index = 1; index < values.length; index += 1) {
if (values[index] > best) {
best = values[index];
}
}
return best;
}Este algoritmo depende de una definición de orden sobre números, declara qué ocurre con la entrada vacía y recorre cada elemento una vez.
Ejemplo:
Problema:
Encontrar el valor máximo de una secuencia.
Instancia:
[4, 1, 9, 2]
Solución:
9Probar que el algoritmo funciona para esta instancia no demuestra que funcione para todas.
Antes de programar, escribe qué recibe y qué devuelve.
Ejemplo:
Dado un array de enteros y un objetivo, devuelve dos índices diferentes cuyos valores sumen el objetivo, o
nullsi no existen.
Ahora conocemos:
number[] y number;null;Todavía podrían faltar decisiones sobre duplicados, mutación, límites numéricos y si debe devolverse una o todas las parejas.
Las restricciones cambian qué soluciones son viables.
n ≤ 20 → enumeración exponencial puede ser posible
n ≤ 10³ → O(n²) puede encajar según constantes
n ≤ 10⁵ → normalmente necesitas O(n log n) u O(n)
n ≤ 10⁷ → memoria y pasadas completas ya importan muchoEstas son orientaciones, no reglas universales. El runtime, límite de tiempo, costo de operaciones y cantidad de casos también influyen.
Preguntas frecuentes:
Una invariante es una propiedad que debe mantenerse.
Ejemplos:
parent <= child;Pensar en invariantes ayuda a diseñar el algoritmo y demostrar que cada operación conserva una estructura válida.
¿Qué cosas existen?
En un sistema de rutas:
BFS con adjacency list cuesta O(V + E). Con matrix puede costar O(V²). La representación forma parte de la solución.
Requisito:
Atender solicitudes en el orden en que llegan.
const queue: Request[] = [];
queue.push(request);
const next = queue.shift();El comportamiento FIFO es correcto, pero shift() puede desplazar elementos y costar O(n).
head y tail.Una estructura puede ser semánticamente correcta y operativamente inadecuada.
No preguntes solamente “¿qué estructura es más rápida?”. Pregunta:
¿Qué operaciones realiza el sistema y con qué frecuencia?
Ejemplo:
| Necesidad | Estructura candidata | Costo relevante |
|---|---|---|
| Acceso frecuente por posición | Array | O(1) |
| Lookup por clave | Hash table | O(1) promedio |
| Claves ordenadas y rangos | BST balanceado | O(log n) |
| Extremo prioritario | Heap | Peek O(1), update O(log n) |
| Procesar niveles | Queue | Enqueue/dequeue O(1) |
| Regreso o nesting | Stack | Push/pop O(1) |
| Conectividad general | Graph | Depende de V, E y representación |
Una estructura optimiza algunas operaciones a cambio de otras.
Un Map puede reducir búsquedas repetidas de O(n) a O(1) promedio, pero usa memoria adicional.
Prefix sums gastan O(n) una vez para responder rangos en O(1).
Hash tables suelen ofrecer lookup promedio constante. Un BST balanceado ofrece O(log n) peor caso y mantiene orden.
Un algoritmo in-place reduce memoria, pero modifica la entrada y puede ser más difícil de verificar.
Counting sort puede superar n log n para enteros en un rango pequeño. No sirve como sorting universal.
Brute force explora la solución más directa.
No siempre es la versión que entregarás, pero permite:
Para encontrar una pareja con suma:
function pairBruteForce(
values: readonly number[],
target: number,
): [number, number] | null {
for (let left = 0; left < values.length; left += 1) {
for (let right = left + 1; right < values.length; right += 1) {
if (values[left] + values[right] === target) {
return [left, right];
}
}
}
return null;
}Tiempo O(n²), espacio O(1).
Observación: para cada valor buscamos repetidamente su complemento. Un Map puede conservar valores anteriores y reducir tiempo promedio a O(n) con O(n) memoria.
La optimización nace de entender el trabajo repetido.
Un patrón conecta una propiedad con una estrategia.
No memorices la asociación sin la propiedad. Binary search no funciona porque el enunciado “parece de búsqueda”; funciona cuando existe monotonicidad.
Una solución correcta debe:
Preguntas útiles:
Analiza la implementación real:
shift() puede cambiar el costo de una queue;slice() puede crear copias;Una frase completa define variables y supuestos:
Con adjacency list, BFS visita cada vértice y arista una vez: tiempo
O(V + E)y memoria adicionalO(V).
JavaScript ofrece estructuras integradas:
Array;Map;Set;No ofrece de forma estándar general una priority queue, deque o balanced BST. Para aprender puedes implementarlas. Para producción suele ser mejor una biblioteca madura o una representación más simple.
TypeScript ayuda a expresar contratos:
type Comparator<T> = (a: T, b: T) => number;
type WeightedEdge = {
to: number;
weight: number;
};Los tipos no prueban correctitud algorítmica. Pueden impedir estados inválidos, pero todavía debes analizar índices, invariantes y casos límite.
Además necesita:
Una implementación de Dijkstra para estudiar no es automáticamente un motor de rutas de producción.
El pseudocódigo expresa lógica sin detalles de un lenguaje.
for each item in input
update state
return resultAl traducirlo debes decidir:
Dos traducciones del mismo pseudocódigo pueden tener complejidades distintas.
Sigue el estado paso a paso:
entrada
→ variables iniciales
→ invariante
→ decisión
→ actualización
→ estado siguiente
→ terminaciónPara estructuras mutables, dibuja referencias:
head → A → B → C → nullPara recursión, dibuja frames o árbol de llamadas.
Para DP, define exactamente qué representa dp[state].
Para grafos, dibuja vértices, dirección y pesos.
Un caso límite no es algo extraño. Es una entrada válida en el borde del dominio.
Diseñarlos antes del código obliga a completar el contrato.
Aprenderás a representar problemas, demostrar correctitud, analizar complejidad y distinguir benchmarks de crecimiento asintótico.
Trabajarás acceso por índice, mutación, Unicode, prefix sums, two pointers, sliding window y algoritmos in-place.
Comprenderás nodos, referencias, sentinels, ciclos, LIFO, FIFO, deques y estructuras monotónicas.
Verás hash functions, collisions, load factor, rehashing, Map, Set, frecuencias y memoization.
Modelarás call stack, recurrence relations, divide and conquer y árboles de decisiones.
Compararás búsqueda lineal y binaria, algoritmos educativos, sorting eficiente, estabilidad y límites por comparación.
Estudiarás traversals, BST, balance, priority queues, tries y consultas de rango.
Aprenderás representación, BFS, DFS, ciclos, topological sort, shortest paths, MST y Union-Find.
Distinguirás decisiones locales demostrables de reutilización de subproblemas.
Conectarás propiedades con técnicas transferibles sin memorizar respuestas.
Practicarás lectura, comunicación, testing, correctitud y una ruta deliberada de estudio.
Para cada nota:
comprender la idea
→ dibujar un ejemplo
→ implementar sin copiar
→ explicar el invariante
→ analizar tiempo y espacio
→ modificar una condición
→ comparar otra estructura
→ resolver una varianteNo avances solo porque el código compila. Debes poder explicar:
Clasifica errores por causa:
Resolver cien ejercicios sin revisar causas puede reforzar hábitos. Resolver menos y reconstruir el razonamiento produce aprendizaje transferible.
No memorices:
O(1) para hashing sin calificativos;O(log n) para cualquier árbol;Memoriza modelos e invariantes después de comprenderlos.
Necesitas almacenar usuarios por id, hacer miles de búsquedas exactas y nunca consultar rangos ordenados. ¿Qué estructura considerarías primero y qué garantía debes aclarar?
Un Map o hash table, porque modela asociación por clave y ofrece lookup promedio cercano a O(1). Debes aclarar que no es una garantía de peor caso constante y que la igualdad de claves, memoria y comportamiento del runtime también forman parte del contrato.