Saltar al contenido

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
  • 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
  • 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
  • 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

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
  • 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

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
  • 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
  • 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

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
  • 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

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
  • 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
  • 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
  • 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

  • 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
  • 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

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
  • 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
  • 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
  • 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

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

bytepatterns.com/cheatsheets/patterns: cada fila enlaza ahí a una lección animada.