Guía rápida de reconocimiento de patrones
Relacione 15 señales habituales de los problemas —array ordenado, necesidad de todas las combinaciones, maximizar un valor con una restricción, etc.— con los patrones algorítmicos que los resuelven más rápidamente.
Guía rápida de reconocimiento de patrones es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
El juego de reconocimiento de patrones de 60 segundos
En una entrevista real, dispone de aproximadamente 60 segundos después de leer un problema para identificar qué patrón algorítmico corresponde antes de que el entrevistador espere que empiece a programar. Esta es la habilidad más importante que debe desarrollar: no memorizar implementaciones, sino reconocer qué herramienta debe utilizar.
El reconocimiento de patrones consiste en relacionar las señales del problema (las palabras y restricciones del enunciado) con familias de algoritmos conocidas. Una vez identificado el patrón, la implementación se convierte en un ejercicio de completar una plantilla. Esta lección es una guía rápida y sistemática de las 15 señales de problemas más comunes y sus patrones correspondientes.
# The recognition process
recognition_steps = [
'1. Read the problem once fully (do not start coding)',
'2. Identify the data structure: array, string, tree, graph, matrix?',
'3. Identify the ask: find min/max, count ways, enumerate, detect cycle...?',
'4. Note the constraint: n<=20 (bitmask), sorted (binary search), DAG (topo sort)?',
'5. Map signal -> pattern',
'6. State the pattern and complexity to the interviewer before coding',
'7. Handle edge cases mentally before writing',
]
for step in recognition_steps:
print(step)Señales 1-3: patrones de arrays y cadenas
Las señales de problemas más frecuentes en arrays y cadenas son:
- Array ordenado + encontrar un objetivo → Búsqueda binaria O(log n)
- Encontrar un par o tripleta cuya suma sea el objetivo → Dos punteros O(n) si está ordenado, mapa hash O(n) si no está ordenado
- Subarray o subcadena más largo o más corto que cumpla una condición → Ventana deslizante O(n)
- Suma máxima o mínima de un subarray contiguo → Algoritmo de Kadane O(n)
- Detección de duplicados → Conjunto hash O(n) u ordenar O(n log n)
Si el array está ordenado, considere siempre primero la búsqueda binaria. Array sin ordenar + suma objetivo + O(n) = casi siempre un mapa hash para buscar el complemento.
# Quick recognition: array/string signals
signals = [
('Sorted array, find element', 'Binary search O(log n)'),
('Find two elements summing to K', 'Sort+two-ptr O(n log n) or hash O(n)'),
('Longest subarray with property P', 'Sliding window (variable size) O(n)'),
('Max sum contiguous subarray', 'Kadane algorithm O(n)'),
('Anagram/permutation check', 'Frequency map (Counter) O(n)'),
('Contains duplicate', 'Hash set O(n)'),
('Merge two sorted arrays/lists', 'Two pointers O(n+m)'),
('Rotate / shift array', 'Reverse trick O(n) in-place'),
('Next permutation', 'Find rightmost ascent + swap + reverse'),
('Maximum product subarray', 'Track max and min (handles negatives)'),
]
for signal, pattern in signals:
print(f'{signal:45s} => {pattern}')Señales 4-6: patrones de árboles y grafos
Estas son las señales de problemas de árboles y grafos y sus patrones:
- Recorrido nivel por nivel / camino más corto en un grafo no ponderado → BFS con deque O(V+E)
- Explorar todos los caminos / detectar ciclos / orden DFS → DFS recursivo o iterativo O(V+E)
- BST + propiedades del recorrido in-order (elemento k-ésimo, orden ordenado) → DFS in-order O(n)
- Ancestro común más bajo → Descenso recursivo con seguimiento del camino O(n)
- Componentes conexos / unir dos grupos → DSU O(n × alpha(n))
# Tree/graph signal recognition
tree_graph_signals = [
('Level-order / minimum depth / word ladder', 'BFS with deque'),
('All paths / path sum / all permutations tree', 'DFS recursive'),
('Cycle detection (undirected)', 'DFS with parent / DSU'),
('Cycle detection (directed) / course schedule', 'DFS three-color / Kahn topo sort'),
('Shortest path weighted graph', 'Dijkstra (non-neg) / Bellman-Ford (neg)'),
('All-pairs shortest path', 'Floyd-Warshall O(V^3)'),
('Topological order', 'Kahn BFS topo sort'),
('Min spanning tree', 'Kruskal (DSU) / Prim (heap)'),
('Dynamic connectivity / union-find', 'DSU path compression + union by rank'),
('Autocomplete / prefix search', 'Trie'),
('BST kth smallest / range sum', 'In-order DFS'),
]
for signal, pattern in tree_graph_signals:
print(f'{signal:50s} => {pattern}')Señales 7-9: señales de programación dinámica
Las señales de DP son las más difíciles de reconocer. Busque estas palabras clave:
- "Número de formas de..." → DP de conteo (sumar las cantidades de los subproblemas)
- "Coste mínimo o máximo para conseguir..." → DP de optimización (tomar el mínimo o máximo de los subproblemas)
- "¿Podemos conseguir...?" (factibilidad) → DP booleana (OR de los subproblemas)
- Subproblema definido por dos índices de una cadena → DP 2D (LCS, distancia de edición)
- Elegir u omitir elementos con una restricción de capacidad → DP de Knapsack
- Subestructura óptima + subproblemas solapados → Compruebe si el árbol de recursión contiene llamadas repetidas → DP
# DP signal recognition
dp_signals = [
('Number of ways to climb stairs / decode string', '1D DP (Fibonacci-like)'),
('Minimum cost to reach end / coin change', '1D DP (greedy fails)'),
('Longest increasing subsequence', '1D DP O(n^2) or patience sort O(n log n)'),
('Longest common subsequence of two strings', '2D DP O(mn)'),
('Edit distance between two strings', '2D DP O(mn) (LCS variant)'),
('Partition array into two equal subsets', '0/1 knapsack boolean DP'),
('Fill knapsack with max value under weight limit', '0/1 knapsack optimisation DP'),
('Burst balloons / matrix chain multiplication', 'Interval DP'),
('Palindrome partitioning minimum cuts', 'Interval DP + prefix palindrome'),
('Rob houses in circle', '1D DP × 2 (linear sub-problems)'),
]
for signal, pattern in dp_signals:
print(f'{signal:55s} => {pattern}')Señales 10-12: señales de heaps, pilas y greedy
Señales de problemas que utilizan heaps, pilas monótonas y greedy:
- Elementos Top-K / k-ésimo más grande o más pequeño → Heap (min-heap para los K elementos más grandes, max-heap para el k-ésimo más pequeño) O(n log k)
- Mediana en streaming → Dos heaps (max-heap de la mitad pequeña + min-heap de la mitad grande)
- Siguiente elemento mayor o menor → Pila monótona O(n)
- Rectángulo de mayor área / contener agua → Pila monótona O(n)
- Planificación de intervalos / maximizar los intervalos no solapados → Greedy (ordenar por hora de finalización)
# Heap / stack / greedy signals
heap_stack_greedy = [
('Top-K frequent elements', 'Min-heap size K: O(n log k)'),
('Kth largest in array', 'Max-heap pop K times: O(n + k log n)'),
('Streaming median', 'Two heaps (max + min): O(log n) per insert'),
('Merge K sorted lists', 'Min-heap of (val, list_idx): O(n log k)'),
('Next greater element', 'Monotonic decreasing stack: O(n)'),
('Largest rectangle in histogram', 'Monotonic increasing stack: O(n)'),
('Sliding window maximum', 'Monotonic decreasing deque: O(n)'),
('Trapping rain water', 'Two pointers OR monotonic stack: O(n)'),
('Jump game reachability / minimum jumps', 'Greedy range expansion: O(n)'),
('Merge overlapping intervals', 'Sort by start, linear scan: O(n log n)'),
('Gas station circular', 'Greedy: start from reset point: O(n)'),
('Task scheduler with cooldown', 'Greedy: sort by frequency: O(n log n)'),
]
for signal, pattern in heap_stack_greedy:
print(f'{signal:45s} => {pattern}')Señales 13-15: backtracking y manipulación de bits
Señales de problemas de backtracking y manipulación de bits:
- Generar todos los subconjuntos / permutaciones / combinaciones → Backtracking O(2^n o n!)
- Satisfacción de restricciones (N-reinas, Sudoku) → Backtracking con poda
- Encontrar un elemento ausente o único → XOR O(n), espacio O(1)
- Enumerar todos los subconjuntos de un conjunto pequeño (n ≤ 20) → Enumeración con máscara de bits 2^n
- Contar bits activados / comprobar si es una potencia de dos → Trucos de bits (n & (n-1))
- DP de compresión de estados con un conjunto pequeño → DP con máscara de bits O(2^n × n)
# Backtracking and bit signals
bt_bit_signals = [
('Generate all subsets of array', 'Backtracking O(n * 2^n) / bitmask'),
('Generate all permutations', 'Backtracking O(n * n!)'),
('Combination sum with target', 'Backtracking with pruning'),
('Word search in grid', 'Backtracking DFS on grid O(m*n*4^L)'),
('N-queens placement', 'Backtracking with column/diag sets'),
('Find single unique element (all others x2)', 'XOR all: O(n) O(1)'),
('Missing number in 0..n', 'XOR or sum formula: O(n) O(1)'),
('Count set bits in n', 'n &= n-1 loop or DP O(n)'),
('Check power of two', 'n > 0 and n & (n-1) == 0'),
('Travelling salesman (n<=20)', 'Bitmask DP O(2^n * n^2)'),
('Number with max XOR in array', 'Trie on binary representation'),
]
for signal, pattern in bt_bit_signals:
print(f'{signal:50s} => {pattern}')Análisis de restricciones: qué le indica N
La restricción sobre el tamaño de entrada n le indica directamente la complejidad temporal aceptable y, por tanto, la familia de algoritmos:
- n ≤ 20: O(2^n) u O(n!) son aceptables — DP con máscara de bits, backtracking
- n ≤ 500: O(n³) es aceptable — Floyd-Warshall, DP por fuerza bruta
- n ≤ 5000: O(n²) es aceptable — DP ingenua, ordenación cuadrática
- n ≤ 10^6: se necesita O(n log n) — merge sort, heap, búsqueda binaria
- n ≤ 10^8: se necesita O(n) — dos punteros, ventana deslizante, DP lineal
Este análisis de restricciones debe ser su primer paso después de leer el problema, antes de decidirse por cualquier algoritmo.
# Constraint -> acceptable complexity -> algorithm family
complexity_map = [
('n <= 20', 'O(2^n) or O(n!)', 'Bitmask DP, backtracking/permutations'),
('n <= 500', 'O(n^3)', 'Floyd-Warshall, cubic DP, brute force'),
('n <= 5000', 'O(n^2)', 'Quadratic DP, bubble/insertion sort'),
('n <= 100000', 'O(n log n)', 'Merge sort, heap, binary search, topo sort'),
('n <= 1000000', 'O(n)', 'Linear DP, two pointers, sliding window, hash'),
('n <= 10^8', 'O(n) tight', 'Only simplest O(n) — no large constants'),
('n <= 10^18', 'O(log n) or O(1)', 'Math / number theory, binary search on answer'),
]
print(f'{'Constraint':15s} {'Complexity':15s} {'Algorithm Family'}')
print('-'*70)
for constraint, complexity, algorithms in complexity_map:
print(f'{constraint:15s} {complexity:15s} {algorithms}')Problema → patrón: práctica rápida
Practique esta relación hasta que se vuelva automática. Lea cada descripción del problema e identifique el patrón antes de consultar la solución. La velocidad es importante: en una entrevista debería identificar el patrón en menos de 60 segundos:
- "Dado un array ordenado, determine si algún par de elementos suma K"
- "Dado un árbol, encuentre el diámetro (el camino más largo entre dos nodos cualesquiera)"
- "Dadas n tareas con un periodo de enfriamiento k, encuentre el número mínimo de intervalos de CPU"
- "Dada una cadena, encuentre la subcadena palindrómica más larga"
- "Dada la secuencia 1..n con un número ausente, encuentre el número que falta"
# Quick-fire pattern recognition answers
problems = [
('Sorted array: two elements sum to K',
'Two pointers (left from start, right from end): O(n)'),
('Tree diameter (longest path)',
'DFS returning (height, max_diameter) pair: O(n)'),
('Task scheduler with cooldown k',
'Greedy: (max_freq - 1)*(k+1) + count_of_max_freq: O(n log n)'),
('Longest palindromic substring',
'Expand around centre OR Manacher: O(n^2) or O(n)'),
('Missing number in 1..n',
'XOR all indices and values: O(n) O(1)'),
('Number of islands in binary grid',
'BFS/DFS flood fill counting connected components: O(m*n)'),
('Decode string like 3[a2[bc]] -> aaabcbcaabcbc',
'Stack to handle nested brackets: O(n)'),
('Valid parentheses [(){[]}]',
'Stack push open, pop+match on close: O(n)'),
]
for problem, solution in problems:
print(f'Q: {problem}\nA: {solution}\n')Señales de alerta: cuándo falla su patrón
Incluso los ingenieros con experiencia eligen inicialmente el patrón equivocado. Reconozca estas señales de que su enfoque actual no es correcto y cambie de estrategia:
- Su solución O(n²) supera las pruebas pequeñas, pero produce TLE con entradas grandes → necesita un mapa hash, búsqueda binaria o una estructura monótona
- Su enfoque greedy falla con un contraejemplo → pruebe con DP
- El espacio de estados de su DP es demasiado grande → busque una demostración greedy o una definición de estado más inteligente
- Su BFS produce una respuesta incorrecta → compruebe si necesita Dijkstra (ponderado) en lugar de BFS (no ponderado)
- Está obteniendo excepciones de puntero nulo → añada casos base y comprobaciones para casos límite antes de implementar
# Red flags and recovery strategies
red_flags = [
('TLE on large n', 'Check complexity; switch from O(n^2) to O(n log n) or O(n)'),
('WA with greedy', 'Find a counter-example; switch to DP or prove exchange arg'),
('DP table huge', 'State compression (bitmask/rolling array) or different state'),
('BFS gives wrong shortest path', 'Check if edges have weights; use Dijkstra instead'),
('Stack overflow in recursion', 'Add memoisation or convert to iterative with explicit stack'),
('Off-by-one in binary search', 'Use half-open intervals [lo, hi); verify with 2-element test'),
('DSU wrong answer', 'Check 0-indexed vs 1-indexed; check union direction'),
('Backtracking TLE', 'Add pruning conditions; ensure undo step is correct'),
]
print('Pattern | Recovery')
print('-'*70)
for flag, recovery in red_flags:
print(f'{flag:40s} => {recovery}')Cómo comunicar el reconocimiento de patrones en entrevistas
En las entrevistas, explicar en voz alta cómo reconoce el patrón demuestra experiencia y permite que el entrevistador le guíe si está siguiendo un camino equivocado. Utilice esta estructura:
- "Observo que el array está ordenado, así que estoy pensando en una búsqueda binaria..."
- "El problema pide el subarray máximo, que es un caso clásico del algoritmo de Kadane..."
- "Necesitamos todos los subconjuntos posibles, lo que sugiere backtracking con un árbol de recursión..."
- "La restricción n ≤ 20 me indica que 2^n = 1M es aceptable, así que podría funcionar una DP con máscara de bits..."
Después de indicar el patrón, mencione la complejidad temporal y espacial antes de escribir una sola línea de código. Esto demuestra que está pensando en la eficiencia antes de la implementación.
# Interview communication template
def communicate_approach(problem, pattern, time_complexity, space_complexity, edge_cases):
print(f'Problem: {problem}')
print(f'Pattern: {pattern}')
print(f'Time: {time_complexity}, Space: {space_complexity}')
print(f'Edge cases to handle: {", ".join(edge_cases)}')
print()
# Example communications
communicate_approach(
problem='Find longest substring without repeating characters',
pattern='Sliding window with a set tracking current window characters',
time_complexity='O(n)',
space_complexity='O(min(n, alphabet_size))',
edge_cases=['empty string', 'all same characters', 'all unique characters']
)
communicate_approach(
problem='Given sorted matrix, find if target exists',
pattern='Binary search or staircase search (top-right corner): eliminate row or column each step',
time_complexity='O(m + n)',
space_complexity='O(1)',
edge_cases=['empty matrix', 'single element', 'target at corners']
)Cómo desarrollar su vocabulario de reconocimiento de patrones
La forma más rápida de desarrollar el reconocimiento de patrones es resolver problemas en tandas temáticas, no al azar. Dedique una semana únicamente a problemas de ventana deslizante. Después, dedíquela a problemas de dos punteros. A continuación, a problemas de DP. Resolver rápidamente 20 problemas del mismo tipo desarrolla la intuición necesaria para reconocer ese patrón a primera vista.
Después de cada problema, escriba una "nota del patrón" de una sola línea: la señal del problema y el patrón que activó. Elabore su propia guía rápida. Después de resolver 200 problemas en tandas temáticas, reconocerá aproximadamente el 90 % de los problemas de entrevistas en menos de 30 segundos; el 10 % restante requiere un análisis cuidadoso incluso para ingenieros con experiencia.
# Personal pattern note template
pattern_notes = [
{'signal': 'sorted array + two sum', 'pattern': 'two pointers', 'example': 'LC 167 Two Sum II'},
{'signal': 'longest X without repeating', 'pattern': 'sliding window + set', 'example': 'LC 3 Longest Substring'},
{'signal': 'max sum subarray', 'pattern': 'Kadane', 'example': 'LC 53 Max Subarray'},
{'signal': 'permutations/subsets', 'pattern': 'backtracking', 'example': 'LC 46 Permutations'},
{'signal': 'tree path sum', 'pattern': 'DFS with accumulator', 'example': 'LC 112 Path Sum'},
{'signal': 'course schedule', 'pattern': 'Kahn topo sort', 'example': 'LC 207 Course Schedule'},
{'signal': 'top-K elements', 'pattern': 'min-heap size K', 'example': 'LC 215 Kth Largest'},
]
print(f'{'Signal':40s} {'Pattern':30s} {'Example'}')
print('-'*90)
for note in pattern_notes:
print(f'{note["signal"]:40s} {note["pattern"]:30s} {note["example"]}')Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido que el reconocimiento de patrones relaciona las señales de los problemas con familias de algoritmos: un array ordenado implica búsqueda binaria, "todos los subconjuntos" implica backtracking y "coste mínimo" implica DP, que la restricción n indica la complejidad aceptable: n ≤ 20 permite O(2^n), mientras que n ≤ 10^6 requiere O(n log n) o mejor, y que explicar el patrón y la complejidad antes de programar demuestra experiencia y permite recibir comentarios del entrevistador. A continuación, pondremos en práctica el reconocimiento de patrones con problemas de entrevistas simuladas cronometradas de dificultad fácil y media.
Preguntas frecuentes
¿La lección «Guía rápida de reconocimiento de patrones» es gratis?
Sí — el texto completo de «Guía rápida de reconocimiento de patrones» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Guía rápida de reconocimiento de patrones»?
Relacione 15 señales habituales de los problemas —array ordenado, necesidad de todas las combinaciones, maximizar un valor con una restricción, etc.— con los patrones algorítmicos que los resuelven m… Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «Guía rápida de reconocimiento de patrones»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Guía rápida de reconocimiento de patrones
- Entrevista simulada cronometrada: problemas fáciles y medios
- Gestión de casos límite y comunicación con el entrevistador
- Resolución guiada de problemas difíciles: Word Ladder II y Alien Dictionary