Cheat sheet de patrones de entrevista
Los patrones clave de las entrevistas de programación: cuándo usar cada uno, las señales del enunciado que lo delatan y una lección y práctica para cada uno.
Actualizado el 23 patronesuna lección y práctica para cada unoSe imprime limpia: usa la impresión de tu navegador
Lee primero el enunciado y después revisa las señales: las frases de abajo son las que delatan un patrón. La línea de costo es lo que el patrón suele lograr: el número que conviene decir en voz alta antes de empezar a escribir código.
Arrays y strings
Dos punteros
Un array (arreglo) ordenado o un string (cadena) donde un par, una partición o un palíndromo se decide desde ambos extremos.
Señales
- array ordenado + encontrar un par / trío con una suma objetivo
- eliminar duplicados o mover elementos in-place
- palíndromo, invertir o comparar desde ambos extremos
Costo típico: O(n) de tiempo, O(1) de espacio
- Lección
- Dos punteros · Arrays
- Práctica
Ventana deslizante
La respuesta es un tramo contiguo, y agrandarlo o achicarlo en un elemento actualiza el estado con poco costo.
Señales
- substring o subarray más largo / más corto que…
- como mucho k distintos, sin repetidos, suma ≥ objetivo
- cada ventana de tamaño k
Costo típico: O(n) de tiempo, O(k) de espacio
- Lección
- Ventana deslizante · Arrays
- Práctica
Sumas de prefijos
Muchas preguntas de suma por rango sobre el mismo array, o una suma de subarray que debe ser igual a k.
Señales
- suma de los elementos entre i y j, pedida muchas veces
- contar subarrays con suma = k (se permiten negativos)
- producto de todos los elementos excepto el propio
Costo típico: O(n) para construir, O(1) por consulta
- Lección
- Sumas de prefijos · Arrays
- Práctica
Búsquedas en un hash map
Dentro de un bucle te preguntas una y otra vez “¿ya vi esto?” o “¿cuántos de estos hay?”.
Señales
- dos elementos que suman / forman pareja (entrada no ordenada)
- anagramas, frecuencias, primer no repetido, duplicados
- agrupar elementos por una clave canónica
Costo típico: O(n) de tiempo, O(n) de espacio
- Lección
- Two Sum · Tablas hash
- Práctica
Búsqueda binaria
La entrada está ordenada, o una pregunta de sí o no sobre la respuesta cambia exactamente una vez a medida que la respuesta crece.
Señales
- array ordenado (o ordenado y rotado), se espera O(log n)
- primera / última posición, posición de inserción
- capacidad / velocidad / días mínimos tal que…
Costo típico: O(log n) por búsqueda; O(Clog R) sobre la respuesta
- Lección
- Búsqueda binaria · Búsqueda
- Práctica
Listas enlazadas y pilas
Punteros rápido y lento
Una lista enlazada (o una función que lleva cada valor al siguiente) donde necesitas un ciclo, el medio o el k-ésimo desde el final.
Señales
- detectar un ciclo / dónde empieza el ciclo
- el medio de la lista en una sola pasada
- eliminar el n-ésimo nodo desde el final
Costo típico: O(n) de tiempo, O(1) de espacio
- Lección
- Punteros rápido y lento · Listas enlazadas
- Práctica
Pila monótona
Para cada elemento necesitas el siguiente (o el anterior) que sea mayor o menor.
Señales
- siguiente mayor / siguiente día más cálido / siguiente menor
- span de precios, edificios visibles, días hasta que…
- rectángulo más grande en un histograma
Costo típico: O(n) de tiempo, O(n) de espacio
- Lección
- Pila monótona · Pilas y colas
- Práctica
Heaps
Top-k elementos
Necesitas los k mayores, menores, más cercanos o más frecuentes, no un ordenamiento completo.
Señales
- k mayores / k menores / k-ésimo mayor
- k puntos más cercanos, k más frecuentes
- un stream donde k se mantiene pequeño
Costo típico: O(n log k) de tiempo, O(k) de espacio
- Lección
- Los top-k elementos · Heaps
- Práctica
Dos heaps
Necesitas el medio de una colección que cambia: un max-heap para la mitad inferior y un min-heap para la superior.
Señales
- mediana acumulada de un stream
- mediana de cada ventana
- elegir el mejor elemento que puedas pagar a medida que crece el presupuesto
Costo típico: O(log n) por inserción, O(1) por mediana
- Lección
- Dos heaps: mediana acumulada · Dos heaps y fusión de k listas
- Práctica
K-way merge
Tienes varias listas ordenadas y las quieres en un solo orden, o buscas el k-ésimo elemento entre todas.
Señales
- fusionar k listas / arrays ordenados
- k-ésimo menor en una matriz ordenada
- rango más pequeño que incluya un elemento de cada lista
Costo típico: O(N log k) de tiempo, O(k) de espacio
- Lección
- K-way merge · Dos heaps y fusión de k listas
- Práctica
Intervalos y greedy
Fusionar intervalos
Rangos que pueden solaparse: ordénalos por inicio y recórrelos una vez comparando cada rango con el último que guardaste.
Señales
- reuniones, reservas, rangos de tiempo, intervalos
- fusionar / insertar / contar intervalos solapados
- mínimo de salas, máximo de eventos simultáneos
Costo típico: O(n log n) de tiempo (por el ordenamiento), O(n) de espacio
- Lección
- Merge Intervals · Intervalos
- Práctica
Elección greedy
Elegir la mejor opción local nunca obliga a deshacer nada, y puedes justificar por qué (con un argumento de intercambio).
Señales
- cantidad máxima de eventos que no se solapan
- ¿puedes llegar al final? / mínimo de saltos
- una ruta circular donde un total acumulado debe mantenerse ≥ 0
Costo típico: Por lo general O(n log n) por el ordenamiento, y luego O(n)
- Lección
- ¿Qué hace que greedy funcione? · Algoritmos greedy
- Práctica
Grafos, cuadrículas y árboles
Búsqueda en anchura
La menor cantidad de pasos en un grafo o una cuadrícula sin pesos, o cualquier cosa que se procese nivel por nivel.
Señales
- camino más corto / mínimo de movimientos, todos los pasos cuestan lo mismo
- por niveles, el más cercano, se propaga minuto a minuto
- varios puntos de partida a la vez (multiorigen)
Costo típico: O(V + E) de tiempo, O(V) de espacio
- Lección
- Búsqueda en anchura · Grafos
- Práctica
Búsqueda en profundidad y flood fill
Explorar todo lo alcanzable: contar regiones, copiar una estructura o verificar una propiedad a lo largo de cada camino.
Señales
- número de islas / regiones conectadas
- rellenar, pintar o marcar un área conectada
- sumas y propiedades de caminos de la raíz a una hoja
Costo típico: O(V + E) de tiempo, O(V) de espacio
- Lección
- Búsqueda en profundidad · Grafos
- Práctica
Ordenamiento topológico
Tareas con prerrequisitos: un orden que respete cada dependencia, o la prueba de que no existe ninguno.
Señales
- cursos / builds / tareas con prerrequisitos
- ¿se pueden terminar todos? (detección de ciclos)
- un orden que se deduce de reglas entre pares
Costo típico: O(V + E) de tiempo, O(V) de espacio
- Lección
- Ordenamiento topológico · Grafos
- Práctica
Union-find
Grupos que solo se fusionan, y preguntas repetidas del tipo “¿están conectados estos dos?”.
Señales
- número de provincias / círculos de amigos / componentes
- la arista que cierra un ciclo (conexión redundante)
- fusionar cuentas o elementos que comparten una clave
Costo típico: O(α(n)) por operación, amortizado
- Lección
- Fundamentos de conjuntos disjuntos · Union-Find
- Práctica
Caminos más cortos con pesos
Las aristas tienen costos distintos: Dijkstra para pesos no negativos, Bellman–Ford cuando pueden ser negativos o el número de saltos está limitado.
Señales
- ruta más barata / más rápida, retardo de red
- como mucho k escalas
- pesos negativos o detección de ciclos negativos
Costo típico: O((V + E) log V) con Dijkstra, O(V·E) con Bellman–Ford
- Lección
- El algoritmo de Dijkstra · Grafos
- Práctica
Trie
Muchas palabras y muchas preguntas por prefijo: autocompletado, “empieza con”, búsqueda de palabras en un tablero.
Señales
- empieza con / prefijo / autocompletar
- encontrar todas las palabras del diccionario en una cuadrícula
- reemplazar palabras por su raíz más corta
Costo típico: O(L) por palabra, O(caracteres totales) de espacio
- Lección
- Fundamentos de tries · Tries
- Práctica
Recursión y programación dinámica
Backtracking
Tienes que listar cada combinación válida, o buscar una bajo restricciones: elegir, llamar recursivamente, deshacer la elección.
Señales
- todos los subconjuntos / permutaciones / combinaciones
- colocar reinas, resolver un sudoku, encontrar una palabra
- n es pequeño (≤ ~20)
Costo típico: Exponencial: O(2n) para subconjuntos, O(n!) para órdenes
- Lección
- El árbol de decisión · Backtracking
- Práctica
Programación dinámica 1D
La respuesta en la posición i depende de unas pocas respuestas anteriores, y la recursión simple repite trabajo.
Señales
- número de formas de llegar al escalón n
- total máximo sin tomar dos vecinos
- formas de decodificar, costo mínimo para subir
Costo típico: O(n) de tiempo, O(1) con variables que se van actualizando
- Lección
- Climbing Stairs · Programación dinámica
- Práctica
DP de mochila
Elegir elementos sin pasarte de una capacidad o para alcanzar un objetivo, cada uno una vez (0/1) o todas las veces que quieras (no acotada).
Señales
- mínimo de monedas / número de formas de formar un monto
- dividir en dos mitades de igual suma
- asignar + / − para llegar a un objetivo
Costo típico: O(n·W) de tiempo, O(W) de espacio
- Lección
- Mochila 0/1 · Programación dinámica
- Práctica
DP 2D en strings y cuadrículas
Dos secuencias comparadas prefijo a prefijo, o una cuadrícula donde cada celda se construye a partir de sus vecinas.
Señales
- subsecuencia común más larga, distancia de edición
- caminos únicos / suma mínima de un camino en una cuadrícula
- subsecuencia palindrómica
Costo típico: O(m·n) de tiempo, O(n) con una sola fila
- Lección
- Subsecuencia común más larga · Programación dinámica
- Práctica
Bits
Trucos con bits
Los pares se cancelan, un conjunto cabe en un entero o la pregunta es sobre potencias de dos.
Señales
- cada número aparece dos veces excepto uno
- número faltante en 0…n con O(1) de espacio
- potencia de dos / contar bits en 1 / todos los subconjuntos como máscaras
Costo típico: O(n) de tiempo, O(1) de espacio
- Lección
- Trucos con XOR · Manipulación de bits
- Práctica
- El valor que faltaFácil
- Dos valores solitariosMedia
bytepatterns.com/cheatsheets/patterns: cada fila enlaza ahí a una lección animada.