E182 - ADS - Parte 3: Two Pointer y Sliding Window

Resumen

El episodio 182 de enCoders es la tercera parte de la serie de Algoritmos y Estructuras de Datos (ADS) y presenta dos técnicas para problemas tipo LeetCode: Two Pointers y Sliding Window. Se explican con dos problemas: Two Sum II (arreglo ordenado, suma objetivo) y el substring más largo sin caracteres repetidos. En Two Sum II se parte de una solución bruta O(n²) y se llega a una solución O(n) en tiempo y O(1) en espacio, usando el orden del arreglo para descartar muchas combinaciones a la vez. En Sliding Window se usa una ventana variable con un diccionario de índices de caracteres, también en O(n), frente a la solución bruta O(n²). Se insiste en los casos borde (vacío, negativos, cero), en hacer preguntas aclaratorias al entrevistador y en razonar la complejidad en tiempo y espacio. Hay un debate sobre la utilidad de LeetCode en entrevistas, especialmente para perfiles de data science. También se habla de cómo la IA complica las evaluaciones y de la utilidad de la universidad. Se adelanta que la cuarta sesión tratará DFS y BFS.

Capítulos

• 00:00
  IntroPresentación de la tercera parte de ADS. Las sesiones anteriores cubrieron estructuras básicas (listas, diccionarios) y estructuras de grafos (árboles binarios, heaps, grafos). Ahora empieza la parte de algoritmos, con unas cuatro técnicas, entre ellas Two Pointers y Sliding Window.
• 01:13
  Por qué importan en entrevistasEstos problemas aparecen en entrevistas técnicas de empresas como Google o Facebook que valoran la optimización de procesos. El presentador dice que nunca hace este tipo de preguntas, pero que es bueno saber formular respuestas a problemas nuevos.
• 02:58
  Patrón Two PointersSe usan dos punteros, por ejemplo uno al inicio y otro al final de la lista. Mover un puntero debe permitir descartar muchas combinaciones a la vez, no solo la actual. También se mencionan punteros con velocidades distintas.
• 05:33
  Casos de uso comunesSirve con arreglos y strings, normalmente ordenados. Aplicaciones: la familia de problemas Two Sum, validar palíndromos (por ejemplo "Ana") y remover duplicados.
• 07:41
  Problema Two Sum IIEs el problema 167 de LeetCode, de dificultad media: arreglo indexado desde 1 y ordenado de forma no decreciente. Hay que devolver los índices de dos números que suman el target. Existe exactamente una solución y no se puede usar el mismo elemento dos veces. Se dan ejemplos (2,7,15 con target 9) y se recomienda probar negativos y cero.
• 11:04
  Solución naive y complejidadSe plantea una solución con dos `for` anidados, que es O(n²). Se explica que sirve para no quedarse estancado en una entrevista. Se discute si preguntar al entrevistador por el tamaño de los datos. Se explican Big O en tiempo y en espacio.
• 17:44
  Optimización con ordenLos participantes proponen ideas propias (restar al target, recorrer solo hacia adelante). La solución es poner L al inicio y R al final. Si la suma es menor que el target, se avanza L. Si es mayor, se retrocede R. Cada movimiento descarta muchos pares gracias al orden, y la complejidad queda en O(n). También se aclara que se pueden usar funciones del lenguaje (sort, deque) si se conoce su complejidad.
• 33:25
  Implementación en PythonSe explica el código: `left=0`, `right=len-1`, `while left < right`. Se compara la suma con el target y se devuelven los índices +1, porque Python empieza en 0 y la respuesta en 1. La complejidad es O(n) en tiempo y O(1) en espacio.
• 38:10
  Más patrones de punterosVariante fast and slow: dos punteros que avanzan a ritmos distintos, útil por ejemplo en listas enlazadas donde no se puede retroceder. Se dice que hay unos 10 algoritmos típicos y que es cuestión de práctica.
• 41:45
  MemesPausa de memes de la comunidad: robo de llaves de Gemini y su factura, un data scientist cuyo trabajo nadie revisa, revisión de código, pipes (R, batch), captchas y la película "El ciempiés humano" como analogía de lista enlazada.
• 46:43
  Depurando una solución fallidaUn participante pasó 19 de 24 tests con su propio enfoque. GPT le había advertido que la intersección podía meter duplicados. Más tarde logra pasar los 24.
• 47:59
  Soluciones en LeetCodeSe muestra la sección de soluciones de LeetCode, con la oficial y muchas de la comunidad, a veces con explicación. Algunas son de pago, pero la mayoría de los problemas son gratis.
• 49:26
  Comentarios de la semanaEl presentador prepara una presentación de proyectos para el máster que empieza al día siguiente, con 21 postulaciones. Se comentan herramientas para hacer presentaciones (GPT, Copilot).
• 50:54
  Anécdota de modelosUn participante cuenta que, al hacer pruebas de diagnóstico para programas de formación, el modelo (GPT 5.2) responde casi todo bien, incluso con gráficos y Excel, y no logra diseñar preguntas que lo hagan fallar.
• 52:28
  Evaluaciones y trampaDebate sobre cómo evaluar con la IA disponible. Las pruebas de alternativas ya no filtran. Se sospecha uso de IA por la convergencia de notas. Se propone la evaluación en vivo, ya que las presentaciones hechas con IA se delatan al preguntar.
• 59:05
  Universidad vs alternativasSe discute si la universidad sigue siendo un lugar para aprender, a raíz de un comentario atribuido al CEO de Palantir. Se sostiene que sí lo es, pero con costo y tiempo altos frente a otras alternativas, y que el título aún pesa como filtro y reputación.
• 01:02:33
  Patrón Sliding WindowDos punteros que se mueven juntos y forman una ventana, por ejemplo de largo fijo 3. Se usa con subarrays o substrings que cumplen una condición, como suma máxima o mínima.
• 01:04:26
  Substring sin repetidosSe plantea el problema del substring más largo sin caracteres repetidos, con ejemplos de respuesta 3, 1 y 3. Se aclara que un substring debe ser continuo.
• 01:06:15
  Ventana variableLa ventana crece con el puntero derecho. Si el nuevo carácter ya está en la ventana, el puntero izquierdo salta a una posición después de la repetición anterior. Se guarda el largo máximo y se discute el caso de borde del string vacío. Se aconseja practicar mucho para entrevistas con tiempo limitado.
• 01:14:04
  Implementacion y complejidadSe usa un diccionario con los índices de los caracteres, un `for` para el puntero derecho, y se actualiza el máximo en cada paso. La solución es O(n). La solución bruta revisa todos los substrings y es O(n²), con la sumatoria n(n+1)/2.
• 01:22:17
  LeetCode en entrevistasDebate sobre la utilidad de LeetCode. Se menciona un video de Primeagen que dice que es fácil pasar estas entrevistas porque te dicen qué estudiar. Se compara con ir al gimnasio. Se concluye que tiene sentido en empresas con sistemas que escalan, pero que no debería ser lo único que se evalúe.
• 01:26:05
  Optimización en datosEjemplo con SQL: hacer un full outer join con filtro es mucho más ineficiente que un left join. Se señala que la empresa paga, pero un costo alto puede afectar al empleado. Se menciona un proyecto de ahorro de costos en S3.
• 01:28:45
  Adelanto de la 4ta sesiónTwo pointers y sliding window suelen aparecer en la pregunta fácil de las entrevistas; la difícil suele ser de grafos. La próxima sesión tratará DFS (en profundidad) y BFS (en anchura), y BFS es mejor para distancias mínimas en grafos sin pesos. También se mencionan los regex básicos como conocimiento útil.
• 01:33:42
  CierreConclusiones: los problemas son entretenidos, pero no se usarían para perfiles de data science salvo en casos con grandes volúmenes de datos. Se compara con hacer jueguitos con el balón en el fútbol. El tema de la próxima semana aún no está confirmado.

Palabras clave