Pular para o conteúdo
Todas as aulas

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

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

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

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

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

  • 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

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

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

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

bytepatterns.com/cheatsheets/patterns — lá, cada linha leva a uma aula animada.