Banco de preguntas de programación

Patrón: Dos punteros·Complejidad: Tiempo O(n), espacio O(1)

Coloca un puntero en cada extremo del array ordenado. Si la suma se queda corta, avanza el puntero izquierdo; si se pasa, retrocede el derecho. Que el array esté ordenado garantiza que nunca te saltas un par válido: ese invariante es lo que los entrevistadores quieren que digas en voz alta.

Patrón: Tabla hash / conteo·Complejidad: Tiempo O(n), espacio O(1) con un alfabeto fijo

Cuenta la frecuencia de cada carácter de la primera cadena, réstala al recorrer la segunda y comprueba que todos los contadores vuelven a cero. Menciona la repregunta antes de que te la hagan: con Unicode completo, un array fijo de 26 posiciones ya no sirve, así que usa una tabla hash.

Patrón: Punteros lento y rápido de Floyd·Complejidad: Tiempo O(n), espacio O(1)

Avanza un puntero de un nodo en un nodo y otro de dos en dos; si alguna vez se encuentran, hay un ciclo. Prepárate para la repregunta clásica, encontrar la entrada del ciclo: vuelve a poner un puntero en la cabeza y avanza ambos de uno en uno hasta que se encuentren de nuevo.

Patrón: Votación de Boyer–Moore·Complejidad: Tiempo O(n), espacio O(1)

Mantén un candidato y un contador: suma uno si coincide, resta uno si no, y cambia de candidato cuando el contador llega a cero. Como el elemento mayoritario aparece más de n/2 veces, siempre sobrevive. Explicar POR QUÉ sobrevive es la entrevista.

Patrón: Una pasada con mínimo acumulado·Complejidad: Tiempo O(n), espacio O(1)

Lleva el precio mínimo visto hasta ahora y la mejor ganancia si vendieras hoy. Un recorrido, dos variables. Es el caso más pequeño de la idea de “arrastrar el mejor estado del prefijo” que luego aparece en el algoritmo de Kadane, y mencionar esa conexión suma puntos.

Patrón: Ordenar + barrido lineal·Complejidad: Tiempo O(n log n), espacio O(n)

Ordena los intervalos por su inicio y luego recórrelos: si el intervalo actual empieza después de que termine el último fusionado, añádelo; si no, extiende el final del fusionado hasta el máximo de ambos. El trabajo de verdad lo hace la ordenación: dilo, y resuelve bien los casos límite del comparador (intervalos que se tocan).

Patrón: Conjunto hash + inicios de secuencia·Complejidad: Tiempo O(n), espacio O(n)

Mete todos los números en un conjunto; empieza a contar solo desde los números cuyo predecesor no está (los inicios de secuencia) y avanza desde ahí. Cada elemento se visita como mucho dos veces, y así defiendes que es O(n) ante la objeción de “pero hay un bucle anidado”.

Patrón: Productos de prefijos y sufijos·Complejidad: Tiempo O(n), espacio extra O(1) sin contar la salida

Dos pasadas sin división: primero llena cada posición con el producto de todo lo que tiene a su izquierda y luego recorre desde la derecha multiplicando por el producto de todo lo que queda a su derecha. Las soluciones con división fallan en los casos con ceros, y los entrevistadores suelen prohibirla de forma explícita.

Patrón: Invariante con una pila auxiliar·Complejidad: O(1) por operación, espacio O(n)

Junto a la pila de valores, mantén una pila de mínimos cuya cima sea siempre el mínimo de todo lo que hay debajo: apila min(nuevo, cima actual) y desapila de ambas a la vez. Es una pregunta de diseño: lo que se evalúa es el invariante, no la cantidad de código.

Patrón: Tabla hash + lista doblemente enlazada·Complejidad: O(1) por get/put, espacio O(capacity)

Una tabla hash da acceso O(1) a los nodos de una lista doblemente enlazada ordenada por uso reciente; al acceder a un nodo, muévelo a la cabeza, y cuando se supere la capacidad, expulsa desde la cola. Los nodos centinela de cabeza y cola eliminan todos los casos límite de comprobar null: menciónalos antes de empezar a programar.

Patrón: Flood fill con BFS/DFS en cuadrícula·Complejidad: Tiempo O(rows × cols)

Recorre la cuadrícula; cada celda de tierra sin visitar inicia un relleno por inundación (flood fill, con DFS o BFS) que marca toda la isla como visitada, y cuentas esos inicios. Explica cómo marcas lo visitado (hundiendo la celda en la propia cuadrícula o con un conjunto aparte) y el riesgo de profundidad de recursión en cuadrículas enormes: esa es la señal de nivel senior.

Patrón: Orden topológico / detección de ciclos·Complejidad: Tiempo O(V + E)

Modela los prerrequisitos como un grafo dirigido: la pregunta “¿puedes terminar?” es exactamente “¿el grafo es acíclico?”. Sirven tanto el algoritmo de Kahn (eliminar repetidamente los nodos con grado de entrada cero) como un DFS con tres colores: elige uno y explica por qué un nodo que sobra significa que hay un ciclo.

Patrón: BFS con instantánea de cada nivel·Complejidad: Tiempo O(n), espacio O(width)

BFS con una cola, pero guarda la longitud de la cola al empezar cada ronda para emitir una lista por nivel. Ese truco de guardar la longitud es el núcleo reutilizable: el recorrido en zigzag y la vista lateral derecha son el mismo bucle con otro paso de recogida.

Patrón: Propagación de límites / inorden·Complejidad: Tiempo O(n), espacio O(height)

Usa recursión con una ventana permitida (min, max) que se estrecha en cada paso, o haz un recorrido inorden y comprueba que es estrictamente creciente. La trampa clásica es comparar cada hijo solo con su padre: construye tú el contraejemplo antes de que lo haga el entrevistador.

Patrón: Mapeo hash en ambos sentidos (biyección)·Complejidad: Tiempo O(n), espacio O(n)

Asigna cada carácter del patrón a una palabra Y cada palabra de vuelta a su carácter: en un solo sentido, el patrón “ab” aceptaría “dog dog”. Comprobar la biyección en ambos sentidos es todo el truco; di la palabra “biyección” y resuelve el caso de longitudes distintas antes de programar.

Patrón: Detección de ciclos en una secuencia oculta·Complejidad: O(log n) por paso; espacio O(1) con Floyd

Si sustituyes repetidamente un número por la suma de los cuadrados de sus dígitos, o llegas a 1 o entras en un bucle: es Linked List Cycle disfrazado. Detecta el bucle con un conjunto de vistos, o impresiona usando los punteros lento y rápido de Floyd para tener espacio O(1). Reconocer la reducción a la detección de ciclos es la jugada de nivel senior.

Patrón: Voraz (greedy) con obligación de demostrarlo·Complejidad: Tiempo O(n), espacio O(1)

Si la suma de gas ≥ la suma de cost, existe una respuesta y es única. Haz un solo recorrido llevando el depósito acumulado; cada vez que se vuelve negativo, ninguna estación del tramo fallido puede ser el punto de partida, así que vuelve a empezar desde la siguiente estación. La entrevista es justificar ese salto, no el bucle en sí.

Patrón: Voraz / capas de BFS implícitas·Complejidad: Tiempo O(n), espacio O(1)

Trata los índices alcanzables en k saltos como una capa de BFS: lleva el borde derecho de la capa actual y el alcance máximo visto; cuando pasas el borde, suma un salto y extiende el borde hasta ese alcance máximo. Plantearlo como un BFS sin cola explica POR QUÉ aquí el enfoque voraz es óptimo.

Patrón: Fusión lineal en tres fases·Complejidad: Tiempo O(n), espacio O(n)

Emite los intervalos que terminan antes de que empiece el nuevo, luego absorbe en el nuevo todos los que se solapan (inicio mínimo, final máximo) y después emite el resto. Como la entrada está ordenada, basta una pasada sin volver a ordenar: compáralo con Merge Intervals si te preguntan por qué este es más fácil.

Patrón: Transformación de la matriz in situ·Complejidad: Tiempo O(n²), espacio O(1)

Rotar 90° en sentido horario = transponer y luego invertir cada fila. Dos pasadas limpias con espacio extra O(1) son mejores que deducir a mano, bajo presión, el intercambio cíclico de cuatro posiciones, pero prepárate para explicar el mapeo de coordenadas (i,j) → (j, n−1−i) si el entrevistador va más allá del truco.

Patrón: Marcado in situ con almacenamiento prestado·Complejidad: Tiempo O(m×n), espacio O(1)

Usa la primera fila y la primera columna para anotar qué filas y columnas hay que llenar de ceros, con dos booleanos que recuerdan su propio estado. Recorre en voz alta la escalera de espacio, copia O(mn) → conjuntos O(m+n) → almacenamiento prestado O(1), porque lo que se evalúa es precisamente esa escalera.

Patrón: Ordenación / cubetas de conteo·Complejidad: O(n log n) ordenando, O(n) con cubetas

Ordena de mayor a menor y busca el mayor i tal que citations[i] ≥ i+1, o evita ordenar con cubetas de conteo limitadas a n para conseguir O(n). Enuncia la definición con precisión antes de programar: la mayoría de los fallos en este problema vienen de malinterpretar “h artículos con al menos h citas”, no del algoritmo.

Patrón: Orden topológico, emitiendo el orden·Complejidad: Tiempo O(V + E)

Es el mismo grafo que en Course Schedule, pero ahora el algoritmo de Kahn demuestra lo que vale: el orden en que los nodos con grado de entrada cero salen de la cola ES un orden válido de cursos. Si el orden emitido tiene menos elementos que cursos hay, existe un ciclo: devuelve una lista vacía. Menciona como alternativa el postorden de un DFS, invertido.

Patrón: Ventana deslizante con contador de requisitos cumplidos·Complejidad: Tiempo O(n), espacio O(alphabet)

Amplía el borde derecho hasta que la ventana cubra todos los caracteres requeridos (lleva un contador de “cumplidos frente a requeridos” en vez de comparar un mapa completo en cada paso) y luego contrae el borde izquierdo al mínimo mientras siga siendo válida, guardando la mejor. La optimización del contador es lo que la mantiene en O(n): menciónala expresamente.

Patrón: Dos punteros sobre máximos acumulados·Complejidad: Tiempo O(n), espacio O(1)

El agua sobre cada barra es min(max-left, max-right) − height. Dos punteros que avanzan hacia dentro desde ambos extremos te permiten resolver el lado con el máximo acumulado más bajo, porque el límite de ese lado ya es definitivo. Explica por qué se cumple esa certeza: es toda la pregunta.