Guia rápido de reconhecimento de padrões
Associe 15 sinais comuns de problemas (vetor ordenado, necessidade de todas as combinações, maximização de valor com restrição etc.) aos padrões de algoritmos que os resolvem mais rapidamente.
Guia rápido de reconhecimento de padrões é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O jogo de reconhecimento de padrões em 60 segundos
Em uma entrevista real, você tem aproximadamente 60 segundos após ler um problema para identificar qual padrão algorítmico se aplica antes que o entrevistador espere que você comece a programar. Esta é a habilidade mais importante a desenvolver — não memorizar implementações, mas reconhecer qual ferramenta usar.
O reconhecimento de padrões vem do mapeamento de sinais dos problemas (palavras e restrições no enunciado) para famílias de algoritmos conhecidas. Depois que você identifica o padrão, a implementação se torna um exercício de preencher um modelo. Esta lição é uma folha de consulta rápida sistemática dos 15 sinais de problemas mais comuns e seus padrões correspondentes.
# 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)Sinais 1 a 3: padrões de vetores e cadeias de caracteres
Os sinais de problemas mais frequentes para vetores e cadeias de caracteres:
- Vetor ordenado + encontrar o alvo → Busca binária O(log n)
- Encontrar um par/trinca cuja soma seja o alvo → Dois ponteiros O(n) se estiver ordenado, tabela de dispersão O(n) se não estiver ordenado
- Maior/menor subvetor/subcadeia que satisfaz uma condição → Janela deslizante O(n)
- Soma máxima/mínima de um subvetor contíguo → Algoritmo de Kadane O(n)
- Detecção de duplicatas → Conjunto de dispersão O(n) ou sort O(n log n)
Se o vetor estiver ordenado, sempre considere primeiro a busca binária. Vetor não ordenado + soma alvo + O(n) = quase sempre uma tabela de dispersão para buscar o 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}')Sinais 4 a 6: padrões de árvores e grafos
Sinais de problemas de árvores e grafos e seus padrões:
- Percurso nível a nível / caminho mais curto em grafo não ponderado → BFS com fila de duas extremidades O(V+E)
- Explorar todos os caminhos / detecção de ciclos / ordem de DFS → DFS recursiva ou iterativa O(V+E)
- BST + propriedades do percurso em ordem (k-ésimo elemento, ordem classificada) → DFS em ordem O(n)
- Menor ancestral comum → Descida recursiva com rastreamento do caminho O(n)
- Componentes conexos / unir dois 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}')Sinais 7 a 9: sinais de programação dinâmica
Os sinais de DP são os mais difíceis de reconhecer. Procure estas palavras-chave:
- 'Número de maneiras de...' → DP de contagem (some as contagens dos subproblemas)
- 'Custo mínimo/máximo para alcançar...' → DP de otimização (escolha o mínimo/máximo dos subproblemas)
- 'Podemos alcançar...' (viabilidade) → DP booleana (OR dos subproblemas)
- Subproblema definido por dois índices de uma cadeia de caracteres → DP bidimensional (LCS, distância de edição)
- Escolher ou ignorar itens sob uma restrição de capacidade → DP da mochila
- Subestrutura ótima + subproblemas sobrepostos → Verifique a árvore de recursão em busca de chamadas 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}')Sinais 10 a 12: sinais de montículos, pilhas e estratégias gulosas
Sinais de problemas com montículos, pilhas monotônicas e estratégias gulosas:
- Elementos entre os K maiores / k-ésimo maior ou menor → Montículo (montículo mínimo para os K maiores, montículo máximo para o k-ésimo menor) O(n log k)
- Mediana em fluxo → Dois montículos (montículo máximo da metade menor + montículo mínimo da metade maior)
- Próximo elemento maior/menor → Pilha monotônica O(n)
- Maior área de retângulo / água retida → Pilha monotônica O(n)
- Escalonamento de intervalos / maximizar intervalos não sobrepostos → Estratégia gulosa (sort pelo horário de término)
# 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}')Sinais 13 a 15: retrocesso e manipulação de bits
Sinais de retrocesso e manipulação de bits:
- Gerar todos os subconjuntos / permutações / combinações → Retrocesso O(2^n ou n!)
- Satisfação de restrições (N rainhas, Sudoku) → Retrocesso com poda
- Encontrar um elemento ausente/único → XOR O(n), espaço O(1)
- Enumerar todos os subconjuntos de um conjunto pequeno (n ≤ 20) → Enumeração com máscara de bits 2^n
- Contar bits definidos / verificar potência de dois → Truques de bits (n & (n-1))
- DP de compressão de estados com conjunto pequeno → DP de 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álise de restrições: o que N informa
A restrição de tamanho da entrada n informa diretamente a complexidade de tempo aceitável — e, portanto, a família de algoritmos:
- n ≤ 20: O(2^n) ou O(n!) aceitável — DP de máscara de bits, retrocesso
- n ≤ 500: O(n³) aceitável — Floyd-Warshall, DP por força bruta
- n ≤ 5000: O(n²) aceitável — DP ingênua, ordenação quadrática
- n ≤ 10^6: O(n log n) necessário — ordenação por intercalação, montículo, busca binária
- n ≤ 10^8: O(n) necessário — dois ponteiros, janela deslizante, DP linear
Essa análise de restrições deve ser seu primeiro passo depois de ler o problema — antes de decidir por qualquer 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 → padrão: prática rápida
Pratique este mapeamento até que se torne automático. Leia cada descrição de problema e identifique o padrão antes de consultar a solução. A velocidade importa — em uma entrevista, você deve identificar o padrão em menos de 60 segundos:
- 'Dado um vetor ordenado, descubra se algum par de elementos soma K'
- 'Dada uma árvore, encontre o diâmetro (o caminho mais longo entre dois nós quaisquer)'
- 'Dadas n tarefas com período de recarga k, encontre o número mínimo de intervalos de CPU'
- 'Dada uma cadeia de caracteres, encontre a maior subcadeia palíndroma'
- 'Dado 1..n com um número ausente, encontre o número ausente'
# 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')Sinais de alerta: quando seu padrão falha
Até mesmo engenheiros experientes escolhem inicialmente o padrão errado. Reconheça estes sinais de que sua abordagem atual está errada e mude de estratégia:
- Seu O(n²) passa em testes pequenos, mas excede o limite de tempo com entradas grandes → você precisa de uma tabela de dispersão, busca binária ou estrutura monotônica
- Sua estratégia gulosa falha em um contraexemplo → tente DP
- Seu espaço de estados da DP é grande demais → procure uma prova gulosa ou uma definição de estado mais inteligente
- Seu BFS fornece uma resposta errada → verifique se você precisa de Dijkstra (ponderado) em vez de BFS (não ponderado)
- Você está obtendo exceções de ponteiro nulo → adicione casos-base e verificações para casos extremos 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}')Comunicando o reconhecimento de padrões em entrevistas
Em entrevistas, explicar em voz alta seu reconhecimento de padrões demonstra conhecimento e dá ao entrevistador a oportunidade de orientar você caso esteja seguindo o caminho errado. Use esta estrutura de roteiro:
- 'Estou observando que o vetor está ordenado, então estou pensando em busca binária...'
- 'O problema pede o subvetor máximo, que é um problema clássico do algoritmo de Kadane...'
- 'Precisamos de todos os subconjuntos possíveis, o que sugere retrocesso com uma árvore de recursão...'
- 'A restrição n ≤ 20 me informa que 2^n = 1M é aceitável, então a DP de máscara de bits pode funcionar...'
Depois de declarar o padrão, mencione a complexidade de tempo e espaço antes de escrever uma única linha de código. Isso mostra que você está pensando em eficiência antes da implementação.
# 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']
)Construindo seu vocabulário de reconhecimento de padrões
A maneira mais rápida de desenvolver o reconhecimento de padrões é resolver problemas em blocos temáticos — não aleatoriamente. Passe uma semana apenas com problemas de janela deslizante. Depois, problemas de dois ponteiros. Em seguida, problemas de DP. Resolver 20 problemas do mesmo tipo rapidamente desenvolve a intuição para reconhecer esse padrão de relance.
Depois de cada problema, escreva uma 'anotação de padrão' de uma linha: o sinal do problema e o padrão que ele desencadeou. Crie sua própria folha de consulta rápida. Depois de resolver 200 problemas em blocos temáticos, você reconhecerá cerca de 90% dos problemas de entrevistas em menos de 30 segundos — os 10% restantes exigem uma análise cuidadosa até mesmo de engenheiros experientes.
# 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"]}')Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: o reconhecimento de padrões mapeia sinais dos problemas para famílias de algoritmos — um vetor ordenado indica busca binária, 'todos os subconjuntos' indica retrocesso, 'custo mínimo' indica DP; a restrição n informa a complexidade aceitável: n ≤ 20 permite O(2^n), n ≤ 10^6 exige O(n log n) ou melhor; e explicar o padrão e a complexidade antes de programar demonstra conhecimento e permite que o entrevistador forneça orientação. A seguir, colocaremos o reconhecimento de padrões em prática com problemas simulados de entrevista cronometrados, de dificuldade fácil e média.
Perguntas Frequentes
A aula “Guia rápido de reconhecimento de padrões” é grátis?
Sim — o texto completo de “Guia rápido de reconhecimento de padrões” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Guia rápido de reconhecimento de padrões”?
Associe 15 sinais comuns de problemas (vetor ordenado, necessidade de todas as combinações, maximização de valor com restrição etc.) aos padrões de algoritmos que os resolvem mais rapidamente. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.
Quanto tempo leva a aula “Guia rápido de reconhecimento de padrões”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Guia rápido de reconhecimento de padrões
- Entrevista simulada cronometrada: problemas fáceis e médios
- Tratamento de casos extremos e comunicação com o entrevistador
- Resolução guiada de problemas difíceis: escada de palavras II e dicionário alienígena