Patrones de algoritmos en C# para entrevistas y concursos

Cinco patrones que no necesitan nada de memoria extra — dos enteros y el arreglo que te dieron. Dónde aplica cada uno, por qué es lineal, y la única línea del último que todo el mundo escribe al revés.

Los dos punteros se mueven en la misma dirección y la brecha entre ellos es la respuesta. Cuatro formas de ventana, más el truco de conteo que convierte «exactamente K» en una resta, porque «exactamente K» no se puede deslizar directamente.

Precalcula una vez y responde cada pregunta sobre un rango en tiempo constante — y el truco inverso que casi nadie enseña, que aplica una actualización a todo un rango escribiendo dos celdas.

Encontrar un valor en un arreglo ordenado es lo menos útil que hace la búsqueda binaria. El patrón que importa busca en un espacio de respuestas que nadie construyó, y no necesita un arreglo ordenado en absoluto.

Una pila que se niega a guardar cualquier cosa inútil responde “cuál es el siguiente elemento más grande” para todo un arreglo en una sola pasada — y la misma estructura mide el rectángulo más grande de un histograma.

Contar sin hacer dos búsquedas hash por elemento, el tamaño exacto de entrada donde Array.Sort deja de preservar el orden, y el heap que C# solo tuvo en .NET 6 — el que la mayoría del código viejo de concursos en C# todavía evita a mano.

La representación que usan casi todas las soluciones en C# es también la razón por la que exceden el límite de tiempo. Después, búsqueda en anchura, búsqueda en profundidad sin la pila de llamadas, y el orden que detecta un ciclo sin costo extra.

Los pesos rompen el BFS. Dijkstra lo arregla, el PriorityQueue de C# no tiene DecreaseKey así que insertas duplicados en su lugar, y cuando cada arista es 0 o 1 el heap resulta ser puro trabajo de más.

No la teoría, sino las cinco formas que se repiten una y otra vez, y la única dirección de bucle que convierte una de ellas, en silencio, en un problema completamente distinto.

La parte que solo te importa cuando una solución correcta ya excedió el límite de tiempo. Leer la entrada sin asignar memoria, el desbordamiento del que C# no te avisa, y por qué Console.WriteLine dentro de un bucle cuesta 400,000 escrituras.

C# no trae el tipo de nodo que estos problemas dan por hecho, y LinkedList no lo es. Cinco patrones — el medio en una pasada, la detección de ciclos de Floyd con su prueba, la inversión en el lugar, y la cabeza ficticia que borra tus casos especiales.

Tres órdenes recursivos que se diferencian por una sola línea, la versión iterativa que nadie logra reconstruir bajo presión, y por qué el recorrido por niveles necesita una variable local en vez de ingenio.

Casi todo problema de árboles es una sola pregunta: ¿esta cantidad viaja hacia abajo por el árbol o de vuelta hacia arriba? Sumas de caminos, el diámetro que nunca toca la raíz, ancestros, y la verificación de BST que todos escriben mal la primera vez.

Toda la familia depende de una sola decisión: ordenar por el inicio, u ordenar por el final. La fusión quiere una, el voraz de planificación quiere la otra, y el código se ve casi igual en los dos casos.

Una plantilla, cinco problemas. Elegir, explorar, deshacer la elección — y es el deshacer lo que la gente deja fuera, porque el código parece terminado sin eso.

XOR para aislar el valor que aparece una sola vez, la clase BitOperations que casi ningún código C# usa, y el desplazamiento que en silencio no hace nada porque el contador dio la vuelta.