E166 - Algoritmos y Estructuras de Datos en entrevistas técnicas

Resumen

El episodio 166 de enCoders abre una serie sobre algoritmos y estructuras de datos en el contexto de entrevistas técnicas. Los conductores discuten si estas entrevistas siguen siendo relevantes en la era de GPT. Concluyen que importan sobre todo en empresas con muchos datos y que las entrevistas deberían acercarse al entorno real de trabajo: se puede usar ayuda, pero hay que saber explicar por qué funciona la solución. Luego repasan órdenes de complejidad (tiempo y espacio) y las estructuras fundamentales en Python: arreglos, strings, hash tables, pilas, colas, listas enlazadas y árboles. Mensajes clave: `join` es muchísimo más eficiente que `+=` para concatenar strings en bucle, la elección de la estructura afecta la eficiencia, y "todo es O(1) hasta que demuestre lo contrario". El tema de heaps y grafos queda para la siguiente sesión.

Capítulos

• 00:00
  IntroPresentación del episodio 166 como primero de una serie sobre algoritmos y estructuras de datos para entrevistas técnicas.
• 00:18
  Experiencia Personal con Entrevistas de ProgramaciónUn conductor cuenta que le fue mal en una entrevista de código por no usar GPT y por no conocer bien la sintaxis (por ejemplo, los decorators, en los que gastó una hora). Se anuncia que hoy se verán órdenes de complejidad y estructuras fundamentales.
• 01:50
  Importancia de Estructuras de Datos y AlgoritmosSe plantea que es un curso típico de universidad y que hoy no es esencial memorizarlo, porque las herramientas de IA lo recuperan en segundos. Proponen entrevistas más cercanas al entorno real, donde se pueda copiar pero se deba explicar. La importancia depende de la empresa: es mayor donde hay muchos datos y clientes. Algunas empresas permiten linter y formateador pero no IA para autocompletar.
• 09:20
  Órdenes de Complejidad ExplicadosSe presentan los órdenes constante, logarítmico, lineal, n log n, cuadrático, polinomiales, exponencial y factorial. Importa el orden de magnitud y no las constantes, aunque en la práctica una constante enorme puede volver impráctico un algoritmo. Se ejemplifica con la suma de una matriz de n×m (orden n·m) y con la complejidad en espacio, comparando lista de vecinos y matriz de adyacencia (n²) de un grafo.
• 19:31
  Entendiendo los Arreglos (Array)Los arreglos guardan elementos contiguos en memoria: acceso e inserción/eliminación al final son O(1), mientras que insertar o eliminar al medio o al inicio y buscar son O(n). Se explica la intuición de puntero con la memoria RAM y se muestra la dirección de memoria de un objeto en Python. Sobre la utilidad práctica, comentan que a muchos data scientists no les importa con pocos datos, pero sí con datos masivos, donde el escalado vertical (más RAM/CPU) cuesta mucho o es imposible. Ejemplos de sintaxis: `append`, `insert`, `pop`, y `arr[-1]` equivale a `arr[len-1]`.
• 33:29
  Cadenas de Texto y sus Operaciones (Strings)Los strings son como arreglos de caracteres. Buscar una subcadena cuesta O(n·m). En Python son inmutables, así que modificar una letra obliga a crear un string nuevo, y `list(string)` convierte a lista en O(n). La complejidad en espacio es O(n).
• 38:40
  join versus += enConcatenar con `+=` en bucle es cuadrático porque recrea el string cada vez, mientras que `join` (o `append` más `join`) es lineal. En el ejemplo de repetir "Python" 100000 veces, `+=` tarda casi un segundo y `join` unos 0,05 s, casi cuatro órdenes de magnitud de diferencia. Un conductor cuenta que pasó de unos 10 minutos a menos de un minuto al cambiar a `join`.
• 42:43
  MemesPausa de memes del Discord: un reporte optimizado de 10 minutos a 3 segundos al que se le agregó una barra de progreso falsa, y bromas sobre IA y consumo energético. También sale el chiste del algoritmo de ordenamiento `array.sort()`.
• 47:11
  Tiempo que demoran los proyectos en generalReflexión sobre un proyecto con plazo ajustado para diciembre que lleva aproximadamente seis semanas de trabajo efectivo, no seis meses. Recomiendan iterar rápido, tomar supuestos y obtener un primer resultado pronto, aunque reciba críticas.
• 50:01
  Hash tables (diccionarios en Python)Las hash tables guardan pares llave-valor y en Python son los diccionarios. Inserción, búsqueda y eliminación son O(1) y el espacio es O(n). Se muestra agregar llaves nuevas, iterar con `.items()` y contar frecuencias de palabras con un diccionario. Un conductor comenta que usa Polars por defecto en lugar de pandas en casi todos los casos.
• 56:04
  Pilas (Stacks)Las pilas siguen LIFO (analogía de una pila de libros y de un pote de arroz), con push, pop y peek en O(1) y espacio O(n). Un ejemplo de aplicación es el historial de commits de Git. Hay una clase `Stack` implementada sobre una lista y se menciona `deque` como alternativa. En el chat se discute la precisión decimal en cuentas financieras, si LeetCode sirve para entrevistas y si DFS usa LIFO (queda para la próxima sesión).
• 01:10:08
  Colas (Queues)`deque` es una cola de dos extremos y su `popleft` saca el primer elemento, lo que permite usar FIFO (analogía de la cola de supermercado). Una aplicación es la cola de procesos cuando no hay suficiente RAM o CPU. Un conductor la dibuja en Excalidraw para afianzar la intuición.
• 01:17:50
  Listas Enlazadas (Linked Lists)Es un grafo dirigido de nodos con punteros: insertar al inicio es O(1) y la inserción en otra posición, la búsqueda y la eliminación son O(n), con espacio O(n). Se muestra una implementación con nodo y cabeza usando `while` para recorrer, y se mencionan el `tail` y las listas doblemente enlazadas. Frente a los arreglos, insertar al inicio es más barato aquí, y la latencia y el costo importan en aplicaciones para usuarios.
• 01:25:55
  Árboles y Árboles de Búsqueda Binaria (Trees and Binary Search Trees)Los árboles son grafos con raíz y capas, y el más típico es el árbol binario. La búsqueda binaria se ilustra con depurar un código dividiendo el script a la mitad: 1024 líneas se reducen a una en 10 pasos, es decir O(log₂ n). El árbol binario de búsqueda (BST) permite buscar en tiempo logarítmico, con espacio O(n). Se anticipan heaps y grafos para la siguiente sesión.
• 01:34:04
  Conclusiones y Reflexiones FinalesReflexionan sobre la dificultad de visualizar árboles y grafos, y sobre abusar del escalado vertical solo cuando no hay impacto. También mencionan que conviene considerar operaciones de entrada/salida, que "todo es O(1) hasta que no lo es", y que es mejor partir con pseudocódigo y dibujos antes de escribir código. El material se subirá a un repositorio y se enlazará en la descripción.

Palabras clave