E175 - Algoritmos y Estructuras de Datos - Parte 2: Estructuras de Datos de Grafos

Resumen

En esta segunda parte de la serie sobre algoritmos y estructuras de datos, Rodo presenta las estructuras basadas en grafos: grafos dirigidos y no dirigidos, matrices y listas de adyacencia, árboles, árboles binarios de búsqueda y heaps. El hilo conductor es que estas estructuras solo valen la pena cuando el problema escala o se repite muchas veces. Se explica por qué la búsqueda binaria y los heaps logran complejidad logarítmica, con ejemplos en código Python (clase `Node`, árbol de búsqueda binaria, módulo `heapq`). Se discute la relevancia de este tema en entrevistas técnicas, LeetCode y los patrones típicos de problemas. La conclusión práctica es empezar por la solución simple y optimizar solo si hace falta, y que lo más difícil es reconocer qué tipo de problema se tiene. El episodio cierra con una conversación sobre si conviene estudiar una carrera universitaria y sobre IA, matemáticas y AlphaGo.

Capítulos

• 00:00
  Introducción a Algoritmos de GrafosSe presenta el tema del día, los grafos, que se preguntan mucho en entrevistas técnicas para medir la capacidad de resolver problemas. Rodo aclara que a él no le gusta hacer estas preguntas, pero que tienen sentido en empresas grandes donde ahorrar una fracción de segundo importa.
• 00:18
  Entrevistas Técnicas y GrafosSe comenta que la IA responde bien a preguntas de optimización, pero no reemplaza entender cuánto demoran los algoritmos y cuánto espacio usan. Se explica la notación O grande: importan los órdenes de magnitud al crecer N, no si un proceso demora el doble.
• 03:52
  Recapitulación de Estructuras de DatosRepaso de la sesión anterior: strings, hash tables (diccionarios en Python), stacks (LIFO), colas (FIFO) y listas enlazadas, que pueden verse como un grafo.
• 05:06
  Entendiendo Grafos y sus RepresentacionesSe definen nodos y aristas, grafos dirigidos y no dirigidos, la matriz de adyacencia (con muchos ceros redundantes) y la lista de adyacencia, que suele ser más eficiente en espacio. Se cuenta un caso real: un problema de provisiones modelado como cadena de Markov, cuya solución era elevar una matriz. También se mencionan el uso de `join` en lugar de `+=` para strings y un proyecto de análisis de redes de clientes.
• 17:10
  Árboles Binarios y sus AplicacionesUn árbol es un grafo dirigido y acíclico (DAG) con raíz, hijos y hojas. Los DAG sirven para modelar pipelines y procesos con inicio y fin; se anticipan los algoritmos de recorrido (DFS) para una tercera sesión. Mati cuenta que programó un algoritmo de búsqueda sobre un árbol en una hackatón.
• 22:05
  Árboles de Búsqueda BinariaSe compara el crecimiento de O(n), O(log n), O(n log n), O(n²) y órdenes peores. Se explica la búsqueda binaria dividiendo por la mitad y por qué el logaritmo es en base 2. Se vincula con el árbol binario como modelo para decidir izquierda o derecha.
• 29:39
  Aplicaciones Prácticas y OptimizaciónEstas estructuras valen la pena cuando la operación se repite muchas veces sobre muchos datos; si el problema es pequeño y de una sola vez, es excesivo. Mati cuenta el ejemplo del problema de la arena en una grilla y recomienda partir con una solución bruta con `for`. Rodo recomienda dibujar el problema.
• 36:35
  Preguntas y Respuestas y Ejemplos del Mundo RealEjemplo buscando el 3 en un árbol de 7 nodos en dos iteraciones. Un árbol balanceado de 1024 nodos requiere a lo más 10 pasos (log₂ 1024). Se menciona que un árbol desbalanceado empeora esto y se relaciona con la elección de índices en bases de datos.
• 43:34
  MemesPausa de memes: roadmaps (no seguirlos al pie de la letra), la caída de preguntas en Stack Overflow, una IA que falla al salir de un laberinto, un Kubernetes con autoscaling para un side project y un meme de grafos reordenados. Se conversa también sobre platinar juegos y logros. Se comenta que casi todo puede modelarse como grafo, por ejemplo las evoluciones de Pokémon.
• 53:37
  Updates de trabajo, y juegoRodo cuenta que en su nuevo trabajo estudió GCP, que le parece más intuitivo que AWS, y que está en un equipo de plataforma. Un participante cuenta que sigue actualizando el juego que ya lanzó.
• 56:50
  Implementación de una clase de árbol binarioSe implementan en Python la clase de nodo (valor, hijo izquierdo y derecho vacíos) y el árbol binario con `insertar` (con un `_insertar_recursivo` privado) y `buscar` recursivo. Se muestra un ejemplo insertando 5, 3, 1 y 9 y consultando si contiene 7 o 10.
• 01:04:12
  Entrevistas técnicas y LeetcodeConsejos para entrevistas: dar un ejemplo simple y ejecutarlo mentalmente, revisar casos borde y mencionar mejoras posibles. Se recomienda LeetCode (más de 3.400 problemas) y practicar uno de cada tipo. Se mencionan patrones como two pointers, sliding window, DFS y BFS.
• 01:11:20
  Grafos genéricosLa complejidad en grafos puede depender de la cantidad de vértices y de aristas, y es común tener varios "n" en ciencia de datos, por ejemplo filas y columnas.
• 01:12:50
  HeapsUn min-heap mantiene que cada padre sea menor que sus hijos, lo que permite obtener el mínimo en O(1), e insertar y extraer en O(log n). Sirve para hallar los K elementos más grandes de un conjunto y en Python existe el módulo `heapq`. También se habla de la postura de las empresas frente al uso de IA en entrevistas.
• 01:18:37
  Importancia del título universitario en la industria del softwareAnte la pregunta de un espectador, Rodo dice que el título importa sobre todo en el primer trabajo y que la universidad forma la manera de estudiar y pensar. Cris prefiere emprender y aprender con la realidad, y Mati valora tener profesores para matemáticas. Se debate si la IA puede ser un buen tutor.
• 01:27:00
  Ejemplo de operaciones de heap implementadosCódigo con `heapq`: copiar la lista, `heapify`, `heappush`, `heappop` y acceder al mínimo con corchetes en O(1). Para un max-heap se pueden invertir los signos o usar las funciones de max-heap del módulo.
• 01:29:04
  CierreSe recomienda conocer los tipos de algoritmos clásicos y qué problemas resuelven; la tercera sesión tratará two pointers, sliding window y DFS/BFS. La conversación termina con la IA resolviendo problemas matemáticos abiertos y con el documental AlphaGo.

Palabras clave