E190 - ADS - Parte 6: Otros patrones útiles en entrevistas

Resumen

En el episodio 190, sexta y última parte de la serie de algoritmos y estructuras de datos (ADS), se repasan patrones útiles para entrevistas técnicas que no se habían tratado: búsqueda binaria, algoritmo greedy, programación dinámica, dividir y conquistar, y recursión con backtracking. La búsqueda binaria se explica con el ejemplo de depurar un script de 1024 líneas: se necesitan 10 iteraciones (log₂ n) frente a las 1024 de una revisión lineal. El algoritmo greedy optimiza a corto plazo y solo es adecuado cuando el problema garantiza que eso lleva al óptimo global (por ejemplo, Jump Game); en el ejemplo del árbol de caminos falla. La programación dinámica se ilustra con Climbing Stairs, donde reciclar subproblemas convierte el cálculo en uno lineal y revela la serie de Fibonacci. Dividir y conquistar y backtracking se mencionan brevemente. Entre medio hay digresiones sobre memes de code review, los "goblins" de ChatGPT, multitasking, canales de comunicación en el trabajo y geometría diferencial. Se anuncia que el próximo episodio tratará de organización y comunicación en el trabajo.

Capítulos

• 00:00
  IntroPresentación del episodio 190 como última parte de la serie de algoritmos y estructuras de datos. Se anuncian los patrones a tratar: Binary Search, greedy, recursión y backtracking, dividir y conquistar, y programación dinámica, con un ejemplo de esta última.
• 01:23
  Búsqueda binaria para debugSirve para encontrar un elemento que se sabe que existe en un conjunto ordenado. Se ejemplifica con un script de 1024 líneas con un output incorrecto: se ejecuta la mitad del código, se descarta la parte sin inconsistencias y se repite.
• 04:33
  Logaritmos y complejidadSe reduce 1024 a 512, 256, 128… hasta 1, lo que da 10 iteraciones. Se deduce con n/2ˣ = 1 que x = log₂(n), es decir, complejidad logarítmica; se compara su gráfica con la lineal.
• 10:37
  Lineal vs logarítmicoRevisar línea por línea es O(n) y se explica por qué su gráfica es una recta. Se aclara que el orden de complejidad habla de escalabilidad y peor caso, no de rapidez en la práctica: con un n pequeño y fijo, un algoritmo peor puede ser más rápido. Se cuenta la pregunta de gerente del juego "mayor o menor" del 1 al 100, que en el fondo es búsqueda binaria.
• 20:01
  Dividir en tres y basesDividir en tres da log₃(n). Las curvas de distintas bases parten ambas de 1 y una base mayor crece más lento. Aun así dividir en dos es más simple, porque basta ejecutar un caso para descartar el otro; en tres habría que ejecutar dos tercios para descartar un tercio. Se menciona la ventaja de la GPU al ejecutar en paralelo.
• 26:25
  Algoritmo greedy explicadoGreedy ("avaro") toma en cada paso la opción que más optimiza en el momento, sin considerar el futuro. Se comparan las decisiones de la vida real, como cambiarse de trabajo por sueldo, con este enfoque.
• 30:29
  Ejemplo greedy y límitesEn un árbol de caminos, greedy obtiene un beneficio total de 22, mientras que otro camino llevaba a 3, 40, 70 y 100. Solo conviene si el problema garantiza que lo óptimo a corto plazo es consistente con lo óptimo a largo plazo; en ese caso es muy eficiente.
• 32:29
  Jump Game en LeetCodeSe presenta Jump Game (problema 55 de LeetCode): un arreglo indica cuánto se puede saltar desde cada índice y se pregunta si se llega al final. Se muestra un arreglo que sí llega y otro que se estanca en un cero.
• 35:05
  Greedy en la vida realSe debate que las personas optimizan de forma greedy por defecto, por ejemplo al salir a festejar en vez de estudiar. Se discute cómo cambia la situación al considerar el valor esperado y la incertidumbre.
• 37:00
  Aclarando el enunciadoSe corrige la lectura del enunciado: se parte fijo en el primer índice y cada valor es el salto máximo, por lo que se puede saltar menos. Se prueba con un ejemplo modificado en que un 2 permite sortear un cero.
• 37:53
  Greedy en saltosUn participante propone saltar siempre lo máximo y retroceder si uno se queda pegado. Se intuye que greedy resuelve el problema.
• 39:00
  Interpretando el enunciadoGreedy funciona si se asume que desde cada posición se puede llegar a cualquier punto hasta el máximo del salto. Se discute que esa condición no está del todo clara en el enunciado.
• 40:35
  Greedy en la vida realSe opina que greedy no suele llegar a soluciones tan malas. Se comenta que las empresas funcionan maximizando las ganancias del año o del trimestre, lo que genera deuda técnica en el largo plazo.
• 41:40
  Knapsack y límitesSe menciona el problema de la mochila con el ejemplo de una maleta de viaje con volumen limitado. Un enfoque greedy por razón beneficio/espacio no llega al óptimo, aunque tampoco es tan malo, según lo recuerda un participante.
• 45:02
  Memes de code reviewMeme sobre aprobar solicitudes de Claude Code. Se comenta que se revisan con más atención los comandos de terminal con `remove`; a un participante una herramienta le borró una carpeta, aunque tenía respaldo en git.
• 46:29
  GoblinsSe comenta el blog de OpenAI "Where the Goblins Came From": algunas versiones de ChatGPT usaban la palabra goblin de más. Se atribuye a una personalidad "nerd" que respondía 81 % más con esa palabra, y se intentó corregir con instrucciones en el prompt. Se especula sobre embeddings y sobre Sam Altman.
• 49:52
  Prompts y memoriaSe comenta que Claude se queja del system prompt por sus restricciones y contradicciones, y de su memoria. Se aclara que tiene un archivo de memoria, pero no una como la humana.
• 51:18
  Recursión vs iteraciónMeme sobre programación dinámica en entrevistas. Las soluciones iterativas suelen ser más difíciles que las recursivas, aunque la recursión es conceptualmente más difícil de entender al principio. Se menciona que todo algoritmo recursivo puede pasarse a iterativo.
• 56:13
  Multitasking y correoDebate sobre el multitasking: depende del tipo de tarea, es malo para trabajo que requiere concentración y aceptable para tareas mecánicas. Se propone revisar el correo dos veces al día.
• 01:02:01
  Teams vs WhatsAppDiscusión sobre canales oficiales de comunicación frente a WhatsApp: seguridad, riesgo de phishing y "madurez digital". Se advierte que enviar documentos por WhatsApp es una falla de seguridad. Se propone dedicar el siguiente stream a tips de organización.
• 01:07:21
  Programación dinámicaSe define como ahorrar trabajo reconociendo subproblemas que se repiten y reciclando sus soluciones. Se introduce el ejemplo Climbing Stairs, con pasos de uno o dos escalones.
• 01:11:33
  Árbol de caminosSe cuentan los caminos para 1, 2 y 3 escalones y se pasa a un árbol para entender el problema.
• 01:14:05
  Contar rutas al cincoSe cuentan las hojas del árbol que llegan al escalón cinco. En el audio se corrige el conteo, que termina siendo ocho caminos.
• 01:14:39
  Reciclar subproblemasLos subárboles repetidos se calculan una sola vez, lo que transforma el problema en uno lineal. Se debate con un ejemplo de asignación de presupuesto de marketing entre Google, TikTok y correo, reutilizando óptimos para presupuestos menores. También se menciona la posible garantía de óptimo global.
• 01:28:56
  Fibonacci y DPEn el último peldaño hay un camino, un peldaño antes hay uno, y cada peldaño anterior suma los dos siguientes (1, 1, 2, 3, 5, 8). La cantidad de caminos para n escalones es un número de la serie de Fibonacci.
• 01:31:01
  Divide y vencerásSe menciona Merge Sort como ejemplo de dividir, ordenar y juntar. Un participante relaciona la idea con branch and bound en programación entera, donde se descartan ramas usando cotas de la relajación del problema.
• 01:34:25
  Recursión y backtrackingEl backtracking consiste en explorar una rama, y si no se encuentra lo buscado, volver y probar otra, como en DFS. Puede implicar marcar y desmarcar elementos.
• 01:35:41
  Cierre y próximos temasReflexiones finales: greedy aplicado a optimización de hiperparámetros, geometría diferencial en gráficos 3D. Se anuncia que el próximo episodio será sobre organización y comunicación en el trabajo.

Palabras clave