Banco de perguntas de programação

Padrão: Dois ponteiros·Complexidade: Tempo O(n), espaço O(1)

Comece com ponteiros nas duas pontas do array ordenado. Se a soma for pequena demais, avance o ponteiro da esquerda; se for grande demais, recue o da direita. A ordenação garante que você nunca pula um par válido — é essa invariante que os entrevistadores querem ouvir você dizer em voz alta.

Padrão: Hash map / contagem·Complexidade: Tempo O(n), espaço O(1) para um alfabeto fixo

Conte a frequência de cada caractere da primeira string, decremente enquanto percorre a segunda e confira se todas as contagens voltam a zero. Mencione o follow-up antes que perguntem: com Unicode completo, um array fixo de 26 posições não funciona mais — use um hash map.

Padrão: Ponteiros lento e rápido de Floyd·Complexidade: Tempo O(n), espaço O(1)

Avance um ponteiro de um em um nó e outro de dois em dois; se eles se encontrarem, existe um ciclo. Esteja pronto para o follow-up clássico — encontrar a entrada do ciclo: volte um dos ponteiros para o início da lista e avance os dois de um em um até se encontrarem de novo.

Padrão: Votação de Boyer–Moore·Complexidade: Tempo O(n), espaço O(1)

Mantenha um candidato e um contador: incremente quando o elemento coincide, decremente quando não coincide e troque o candidato quando o contador chegar a zero. Como o elemento majoritário aparece mais de n/2 vezes, ele sempre sobrevive. Explicar POR QUE ele sobrevive é a entrevista.

Padrão: Uma passada com mínimo acumulado·Complexidade: Tempo O(n), espaço O(1)

Acompanhe o menor preço visto até agora e o melhor lucro se você vendesse hoje. Uma varredura, duas variáveis. É a menor instância da ideia de “carregar o melhor estado do prefixo”, que aparece depois no algoritmo de Kadane — mencionar essa conexão vale pontos.

Padrão: Ordenação + varredura linear·Complexidade: Tempo O(n log n), espaço O(n)

Ordene os intervalos pelo início e depois varra: se o intervalo atual começa depois que o último intervalo mesclado termina, adicione-o; caso contrário, estenda o fim do mesclado até o maior dos dois. A ordenação é que faz o trabalho de verdade — diga isso e acerte os casos-limite da comparação (intervalos que se tocam).

Padrão: Hash set + inícios de sequência·Complexidade: Tempo O(n), espaço O(n)

Coloque todos os números num conjunto; só comece a contar a partir dos números cujo antecessor não está no conjunto (inícios de sequência) e então avance. Cada elemento é visitado no máximo duas vezes, e é assim que você defende o O(n) contra a objeção “mas tem um loop aninhado”.

Padrão: Produtos de prefixo e de sufixo·Complexidade: Tempo O(n), espaço extra O(1) além da saída

Duas passadas sem divisão: primeiro preencha cada posição com o produto de tudo o que está à esquerda dela, depois varra a partir da direita multiplicando pelo produto de tudo o que está à direita. Respostas com divisão falham nos casos com zero — os entrevistadores costumam proibi-la explicitamente.

Padrão: Invariante com pilha auxiliar·Complexidade: O(1) por operação, espaço O(n)

Ao lado da pilha de valores, mantenha uma pilha de mínimos cujo topo é sempre o mínimo de tudo o que está abaixo — empilhe min(novo, topo atual) e desempilhe as duas juntas. Esta é uma pergunta de design: o que está sendo avaliado é a invariante, não a quantidade de código.

Padrão: Hash map + lista duplamente encadeada·Complexidade: O(1) por get/put, espaço O(capacidade)

Um hash map dá acesso O(1) aos nós de uma lista duplamente encadeada ordenada por uso recente; mova um nó para o início quando ele for acessado e remova do fim quando a capacidade estourar. Nós sentinela no início e no fim eliminam todos os casos-limite de checagem de null — mencione-os antes de começar a programar.

Padrão: Flood fill com BFS/DFS em grade·Complexidade: Tempo O(linhas × colunas)

Percorra a grade; cada célula de terra não visitada inicia um flood fill (DFS ou BFS) que marca a ilha inteira como visitada, e você conta os inícios. Explique a sua estratégia de marcação (afundar a ilha no próprio lugar ou usar um conjunto separado) e o risco de profundidade de recursão em grades enormes — esse é o sinal de senioridade.

Padrão: Ordenação topológica / detecção de ciclos·Complexidade: Tempo O(V + E)

Modele os pré-requisitos como um grafo direcionado; a pergunta “dá para concluir?” é exatamente “o grafo é acíclico?”. O algoritmo de Kahn (remover repetidamente os nós com grau de entrada zero) ou a DFS com três cores funcionam — escolha um e explique por que um nó que sobra significa um ciclo.

Padrão: BFS com retrato de cada nível·Complexidade: Tempo O(n), espaço O(largura)

BFS com uma fila, mas guarde o tamanho da fila no início de cada rodada para emitir uma lista por nível. Esse truque de guardar o tamanho é o núcleo reutilizável — o percurso em zigue-zague e a visão do lado direito são o mesmo loop com outra forma de coletar.

Padrão: Propagação de limites / percurso em ordem·Complexidade: Tempo O(n), espaço O(altura)

Faça a recursão com uma janela permitida (mín., máx.) que se estreita a cada passo — ou faça um percurso em ordem e confira se ele é estritamente crescente. A armadilha clássica é comparar os filhos só com o pai; construa você mesmo o contraexemplo antes que o entrevistador faça isso.

Padrão: Mapeamento de hash nos dois sentidos (bijeção)·Complexidade: Tempo O(n), espaço O(n)

Mapeie os caracteres do padrão para as palavras E as palavras de volta para os caracteres — um sentido só aceita o padrão “ab” para “dog dog”. Conferir a bijeção nos dois sentidos é o truque inteiro; diga a palavra “bijeção” e trate o caso de tamanhos diferentes antes de programar.

Padrão: Detecção de ciclo numa sequência escondida·Complexidade: O(log n) por passo; espaço O(1) com Floyd

Substituir repetidamente um número pela soma dos quadrados dos seus dígitos ou chega a 1 ou entra num loop — então este é o Linked List Cycle disfarçado. Detecte o loop com um conjunto dos números já vistos, ou impressione com os ponteiros lento e rápido de Floyd para ter espaço O(1). Nomear a redução para detecção de ciclo é a jogada de quem é sênior.

Padrão: Guloso com obrigação de prova·Complexidade: Tempo O(n), espaço O(1)

Se o combustível total ≥ o custo total, existe uma resposta e ela é única. Varra uma vez acompanhando o tanque acumulado; sempre que ele ficar negativo, nenhum posto do trecho que falhou pode ser o ponto de partida — recomece a partir do próximo posto. A entrevista é a justificativa desse salto, não o loop em si.

Padrão: Guloso / camadas implícitas de BFS·Complexidade: Tempo O(n), espaço O(1)

Trate os índices alcançáveis com até k saltos como uma camada de BFS: acompanhe a borda direita da camada atual e o alcance mais distante visto; quando você passar da borda, incremente os saltos e estenda a borda até esse alcance mais distante. Enxergar isso como uma BFS sem fila explica POR QUE o guloso é ótimo aqui.

Padrão: Mesclagem linear em três fases·Complexidade: Tempo O(n), espaço O(n)

Emita os intervalos que terminam antes de o novo começar, depois absorva no novo cada intervalo que se sobrepõe a ele (menor início, maior fim) e, por fim, emita o resto. Como a entrada já vem ordenada, basta uma passada sem reordenar — compare com Merge Intervals se perguntarem por que este é mais fácil.

Padrão: Transformação da matriz no próprio lugar·Complexidade: Tempo O(n²), espaço O(1)

Girar 90° no sentido horário = transpor e depois inverter cada linha. Duas passadas limpas com espaço extra O(1) são melhores do que deduzir na mão a troca cíclica de quatro posições sob pressão — mas esteja pronto para explicar o mapeamento de coordenadas (i,j) → (j, n−1−i) se o entrevistador for além do truque.

Padrão: Marcação no próprio lugar com armazenamento emprestado·Complexidade: Tempo O(m×n), espaço O(1)

Use a primeira linha e a primeira coluna para guardar as marcações de quais linhas e colunas devem ser zeradas, com dois booleanos lembrando o estado delas próprias. Percorra a escada de espaço em voz alta — cópia O(mn) → conjuntos O(m+n) → armazenamento emprestado O(1) —, porque a própria escada é o que está sendo testado.

Padrão: Ordenação / baldes de contagem·Complexidade: O(n log n) com ordenação, O(n) com baldes

Ordene de forma decrescente e encontre o maior i em que citations[i] ≥ i+1 — ou dispense a ordenação com baldes de contagem limitados a n para ter O(n). Enuncie a definição com precisão antes de programar; a maioria das falhas neste problema vem de entender errado “h artigos com pelo menos h citações”, não do algoritmo.

Padrão: Ordenação topológica, com a ordem emitida·Complexidade: Tempo O(V + E)

O mesmo grafo do Course Schedule, mas agora o algoritmo de Kahn mostra o seu valor: a ordem em que os nós com grau de entrada zero saem da fila É uma ordem válida de disciplinas. Se a ordem emitida for menor do que o número de disciplinas, existe um ciclo — retorne vazio. Mencione a DFS em pós-ordem invertida como alternativa.

Padrão: Janela deslizante com contador de satisfação·Complexidade: Tempo O(n), espaço O(alfabeto)

Expanda a borda direita até a janela cobrir todos os caracteres exigidos (acompanhe um contador de “formados versus exigidos”, em vez de comparar o mapa inteiro a cada passo), depois contraia a borda esquerda até o mínimo enquanto a janela continua válida, registrando a melhor. A otimização do contador de formados é o que mantém o O(n) — explique-a explicitamente.

Padrão: Dois ponteiros sobre máximos acumulados·Complexidade: Tempo O(n), espaço O(1)

A água acima de cada barra é min(máx. à esquerda, máx. à direita) − altura. Dois ponteiros que avançam das duas pontas para o meio permitem resolver o lado que tem o menor máximo acumulado, porque o limite desse lado já é definitivo. Explique por que essa certeza se sustenta — é a pergunta inteira.