Cheat sheet de padrões de entrevista
Os padrões de entrevista de programação que vale conhecer: quando usar cada um, os sinais no enunciado que os entregam, com aula e prática para cada.
Atualizado em 23 padrõesuma aula e prática para cadaPronta para imprimir — use a impressão do seu navegador
Leia primeiro o enunciado do problema e depois examine os sinais: as expressões abaixo são as que entregam um padrão (pattern). A linha de custo é o que o padrão normalmente alcança — o número para dizer em voz alta antes de começar a escrever código.
Arrays e strings
Dois ponteiros
Um array ordenado ou uma string em que um par, uma partição ou um palíndromo se decide pelas duas pontas.
Sinais
- array ordenado + encontrar um par / trio com soma alvo
- remover duplicatas ou mover itens in-place
- palíndromo, inverter ou comparar pelas duas pontas
Custo típico: O(n) de tempo, O(1) de espaço
- Aula
- Dois ponteiros · Arrays
- Prática
Janela deslizante
A resposta é um trecho contíguo, e aumentá-lo ou diminuí-lo em um elemento atualiza o estado de forma barata.
Sinais
- maior / menor substring ou subarray que…
- no máximo k distintos, sem repetição, soma ≥ alvo
- toda janela de tamanho k
Custo típico: O(n) de tempo, O(k) de espaço
- Aula
- Janela deslizante · Arrays
- Prática
Somas de prefixos
Muitas perguntas de soma de intervalo sobre o mesmo array, ou uma soma de subarray que precisa ser igual a k.
Sinais
- soma dos elementos entre i e j, pedida várias vezes
- contar subarrays com soma = k (negativos permitidos)
- produto de tudo exceto o próprio elemento
Custo típico: O(n) para montar, O(1) por consulta
- Aula
- Somas de prefixos · Arrays
- Prática
Buscas em hash map
Você vive perguntando “já vi isso antes?” ou “quantos destes existem?” dentro de um loop.
Sinais
- dois itens que somam / formam um par (entrada não ordenada)
- anagramas, frequências, primeiro único, duplicatas
- agrupar itens por uma chave canônica
Custo típico: O(n) de tempo, O(n) de espaço
- Aula
- Two Sum · Tabelas hash
- Prática
Busca binária
A entrada está ordenada — ou uma pergunta de sim/não sobre a resposta muda exatamente uma vez conforme a resposta cresce.
Sinais
- array ordenado (ou ordenado e rotacionado), O(log n) esperado
- primeira / última posição, posição de inserção
- capacidade / velocidade / dias mínimos tais que…
Custo típico: O(log n) por busca; O(Clog R) na resposta
- Aula
- Busca binária · Busca
- Prática
Listas encadeadas e pilhas
Ponteiros rápido e lento
Uma lista encadeada (ou uma função que leva cada valor ao próximo) em que você precisa de um ciclo, do meio ou do k-ésimo a partir do fim.
Sinais
- detectar um ciclo / onde o ciclo começa
- meio da lista em uma passada
- remover o n-ésimo nó a partir do fim
Custo típico: O(n) de tempo, O(1) de espaço
- Aula
- Ponteiros rápido e lento · Listas encadeadas
- Prática
Pilha monotônica
Para cada elemento, você precisa do próximo (ou do anterior) elemento maior ou menor.
Sinais
- próximo maior / próximo dia mais quente / próximo menor
- span, prédios visíveis, dias até…
- maior retângulo em um histograma
Custo típico: O(n) de tempo, O(n) de espaço
- Aula
- Pilha monotônica · Pilhas e filas
- Prática
Heaps
Top-k elementos
Você precisa dos k maiores, menores, mais próximos ou mais frequentes — não de uma ordenação completa.
Sinais
- k maiores / k menores / k-ésimo maior
- k pontos mais próximos, k mais frequentes
- um stream em que k continua pequeno
Custo típico: O(n log k) de tempo, O(k) de espaço
- Aula
- Top-k elementos · Heaps
- Prática
Dois heaps
Você precisa do meio de uma coleção que muda: um max-heap para a metade de baixo, um min-heap para a de cima.
Sinais
- mediana contínua de um stream
- mediana de cada janela
- escolher o melhor item que cabe no orçamento conforme ele cresce
Custo típico: O(log n) por inserção, O(1) por mediana
- Aula
- Dois heaps: mediana contínua · Dois heaps e k-way merge
- Prática
K-way merge
Várias listas ordenadas que você quer em uma única ordem, ou o k-ésimo item entre todas elas.
Sinais
- mesclar k listas / arrays ordenados
- k-ésimo menor em uma matriz ordenada
- menor intervalo que cobre um item de cada lista
Custo típico: O(N log k) de tempo, O(k) de espaço
- Aula
- K-way merge · Dois heaps e k-way merge
- Prática
Intervalos e algoritmos gulosos
Mesclar intervalos
Intervalos que podem se sobrepor: ordene pelo início e depois varra uma vez, comparando cada intervalo com o último mantido.
Sinais
- reuniões, reservas, intervalos de tempo, spans
- mesclar / inserir / contar intervalos sobrepostos
- mínimo de salas, máximo simultâneo
Custo típico: O(n log n) de tempo (a ordenação), O(n) de espaço
- Aula
- Merge Intervals · Intervalos
- Prática
Escolha gulosa
A melhor opção local nunca precisa ser desfeita — e você sabe justificar por quê (um argumento de troca).
Sinais
- número máximo de eventos sem sobreposição
- dá para chegar ao fim / menor número de saltos
- uma rota circular em que um total acumulado precisa ficar ≥ 0
Custo típico: Em geral O(n log n) para ordenar, depois O(n)
- Aula
- O que faz um algoritmo guloso funcionar · Algoritmos gulosos
- Prática
Grafos, grids e árvores
Busca em largura
Menos passos em um grafo ou grid sem pesos, ou qualquer coisa processada nível por nível.
Sinais
- menor caminho / mínimo de movimentos, todo passo custa o mesmo
- ordem por nível, mais próximo, espalhando minuto a minuto
- vários pontos de partida ao mesmo tempo (múltiplas origens)
Custo típico: O(V + E) de tempo, O(V) de espaço
- Aula
- Busca em largura · Grafos
- Prática
Busca em profundidade e flood fill
Explorar tudo o que é alcançável — contar regiões, copiar uma estrutura ou verificar uma propriedade em todos os caminhos.
Sinais
- número de ilhas / regiões conectadas
- preencher, pintar ou marcar uma área conectada
- somas e propriedades de caminhos da raiz até a folha
Custo típico: O(V + E) de tempo, O(V) de espaço
- Aula
- Busca em profundidade · Grafos
- Prática
Ordenação topológica
Tarefas com pré-requisitos: uma ordem que respeita todas as dependências, ou a prova de que ela não existe.
Sinais
- cursos / builds / tarefas com pré-requisitos
- dá para terminar tudo? (verificação de ciclo)
- uma ordem derivada de regras entre pares
Custo típico: O(V + E) de tempo, O(V) de espaço
- Aula
- Ordenação topológica · Grafos
- Prática
Union-find
Grupos que só se fundem, e perguntas repetidas do tipo “estes dois estão conectados?”.
Sinais
- número de províncias / círculos de amigos / componentes
- a aresta que fecha um ciclo (conexão redundante)
- mesclar contas ou itens que compartilham uma chave
Custo típico: O(α(n)) por operação, amortizado
- Aula
- O básico de conjuntos disjuntos · Union-Find
- Prática
Menores caminhos com pesos
As arestas têm custos diferentes: Dijkstra para pesos não negativos, Bellman–Ford quando podem ser negativos ou o número de saltos é limitado.
Sinais
- rota mais barata / mais rápida, atraso de rede
- no máximo k paradas
- pesos negativos ou detecção de ciclo negativo
Custo típico: O((V + E) log V) com Dijkstra, O(V·E) com Bellman–Ford
- Aula
- Algoritmo de Dijkstra · Grafos
- Prática
Trie
Muitas palavras e muitas perguntas sobre prefixos: autocompletar, “começa com”, busca de palavras em um tabuleiro.
Sinais
- começa com / prefixo / autocompletar
- encontrar todas as palavras do dicionário em um grid
- substituir palavras pela raiz mais curta
Custo típico: O(L) por palavra, O(total de caracteres) de espaço
- Aula
- O básico de tries · Tries
- Prática
Recursão e programação dinâmica
Backtracking
Você precisa listar todo arranjo válido, ou buscar um sob restrições: escolher, chamar recursivamente, desfazer a escolha.
Sinais
- todos os subconjuntos / permutações / combinações
- posicionar rainhas, preencher um sudoku, encontrar uma palavra
- n é pequeno (≤ ~20)
Custo típico: Exponencial: O(2n) para subconjuntos, O(n!) para ordens
- Aula
- A árvore de decisão · Backtracking
- Prática
Programação dinâmica 1D
A resposta na posição i depende de algumas respostas anteriores, e a recursão pura repete trabalho.
Sinais
- número de formas de chegar ao degrau n
- total máximo sem pegar dois vizinhos
- formas de decodificar, custo mínimo para subir
Custo típico: O(n) de tempo, O(1) com variáveis rotativas
- Aula
- Climbing Stairs · Programação dinâmica
- Prática
DP de mochila
Escolher itens sob uma capacidade ou para atingir um alvo, cada item uma vez (0/1) ou quantas vezes quiser (ilimitada).
Sinais
- menos moedas / número de formas de formar um valor
- dividir em duas metades de soma igual
- atribuir + / − para chegar a um alvo
Custo típico: O(n·W) de tempo, O(W) de espaço
- Aula
- Mochila 0/1 · Programação dinâmica
- Prática
DP 2D em strings e grids
Duas sequências comparadas prefixo a prefixo, ou um grid em que cada célula é construída a partir das vizinhas.
Sinais
- maior subsequência comum, distância de edição
- caminhos únicos / soma mínima de caminho em um grid
- subsequência palindrômica
Custo típico: O(m·n) de tempo, O(n) com uma linha
- Aula
- Maior subsequência comum · Programação dinâmica
- Prática
Bits
Truques com bits
Pares se cancelam, um conjunto cabe em um inteiro, ou a pergunta é sobre potências de dois.
Sinais
- todo número aparece duas vezes, exceto um
- número que falta em 0…n com O(1) de espaço
- potência de dois / contar bits 1 / todos os subconjuntos como máscaras
Custo típico: O(n) de tempo, O(1) de espaço
- Aula
- Truques com XOR · Manipulação de bits
- Prática
- O valor que faltaFácil
- Dois valores solitáriosMédio
bytepatterns.com/cheatsheets/patterns — lá, cada linha leva a uma aula animada.