Guia de entrevista para engenheiro de software

Estrutura: Busca pelo complemento

A abordagem de força bruta testa todos os pares, o que leva O(n^2). Uma abordagem melhor usa um hash map de valor para índice. Enquanto percorremos o array, para cada número x, o valor de que precisamos é alvo - x. Se esse complemento já existe no mapa, retornamos o índice atual e o índice armazenado. Caso contrário, guardamos x com o seu índice e seguimos em frente. A ideia central de corretude é que, quando processamos o índice i, o mapa contém exatamente os valores dos índices anteriores. Isso significa que, se existe um par válido que termina em i, vamos encontrá-lo na hora. Isso também evita usar o mesmo elemento duas vezes, porque só comparamos com elementos anteriores. A complexidade de tempo é O(n), porque cada valor é inserido e consultado uma vez. A complexidade de espaço é O(n) por causa do mapa. Os casos de borda incluem valores duplicados, números negativos, zero e a ausência de par válido, se o enunciado permitir esse caso.

Estrutura: Janela deslizante com o último índice visto

Use uma janela deslizante em que a janela sempre contenha apenas caracteres únicos. Mantenha um ponteiro left e um mapa de cada caractere para o seu índice mais recente. Avance right pela string. Se o caractere atual já apareceu dentro da janela atual, mova left para uma posição depois do índice anterior dele. Em seguida, atualize o índice do caractere e registre o maior tamanho de janela. O detalhe importante é que left só pode avançar. Se um caractere apareceu antes da janela atual, ele não deve encolher a janela. É por isso que a atualização é left = max(left, lastSeen[char] + 1). A complexidade de tempo é O(n), porque cada caractere é processado uma vez e o ponteiro left só anda para a frente. A complexidade de espaço é O(k), em que k é o tamanho do conjunto de caracteres. Os casos de borda incluem string vazia, todos os caracteres únicos, todos os caracteres repetidos e Unicode, se a linguagem tratar caracteres de forma diferente de bytes.

Estrutura: Chave canônica

Anagramas têm a mesma composição de caracteres. Crie uma chave canônica para cada palavra e agrupe as palavras por essa chave em um hash map. A chave mais direta são os caracteres da palavra ordenados. Por exemplo, “eat”, “tea” e “ate” viram todos “aet”. Se as strings forem curtas, ordenar cada palavra é simples e confiável. Se o alfabeto for fixo, só com letras minúsculas do inglês, e as strings forem longas, uma tupla com 26 contagens de frequência pode ser mais rápida, porque evita a ordenação O(k log k) por palavra. Com ordenação, a complexidade de tempo é O(n * k log k), em que n é o número de strings e k é o tamanho médio de cada string. Com contagem sobre um alfabeto fixo, pode chegar a O(n * k). A complexidade de espaço é O(n * k) para a saída mais as chaves. Os casos de borda incluem strings vazias, duplicatas, regras de maiúsculas e minúsculas e caracteres fora do alfabeto inglês.

Estrutura: Três ponteiros: previous, current e next

Use três ponteiros. previous começa como null e current começa na cabeça da lista. Para cada nó, guarde next = current.next, redirecione current.next para previous e então mova previous para current e current para next. Quando current virar null, previous é a nova cabeça. O invariante é que previous aponta para a parte já invertida e current aponta para o primeiro nó ainda não invertido. Guardar next antes de alterar current.next é essencial; caso contrário, você perde o resto da lista. A complexidade de tempo é O(n). A complexidade de espaço é O(1). Os casos de borda incluem lista vazia, um único nó e garantir que a cabeça original vire a cauda, com next apontando para null.

Estrutura: Restrições de intervalo

Um erro comum é verificar apenas se cada nó é maior que o filho da esquerda e menor que o filho da direita. Isso não basta, porque a subárvore inteira precisa respeitar as restrições impostas pelos ancestrais. Use DFS com limites inferior e superior (lower e upper). Para cada nó, verifique se lower < node.value < upper. O filho da esquerda recebe o mesmo limite inferior e o valor atual como limite superior. O filho da direita recebe o valor atual como limite inferior e o mesmo limite superior. Se algum nó violar o seu intervalo, retorne false. A complexidade de tempo é O(n), porque cada nó é visitado uma vez. A complexidade de espaço é O(h) pela profundidade da recursão, em que h é a altura da árvore. Os casos de borda incluem duplicatas, os limites mínimo e máximo de inteiros, árvore vazia e árvores desbalanceadas. Esclareça se duplicatas são permitidas e, se forem, de qual lado ficam.

Estrutura: Busca em largura por camadas de distância

Modele cada célula livre como um nó do grafo e cada movimento para cima, para baixo, para a esquerda ou para a direita como uma aresta de mesmo peso. Como todo movimento tem o mesmo custo, a BFS encontra o menor caminho. Comece pela célula de origem, coloque-a na fila com distância 0 e marque-a como visitada. Para cada célula retirada da fila, explore os vizinhos válidos e não visitados que estejam dentro dos limites e não sejam obstáculos. Na primeira vez que alcançamos o destino, a distância é mínima. A corretude vem do fato de a BFS processar os nós em ordem crescente de distância. Depois que uma célula é visitada, chegar a ela mais tarde não pode gerar um caminho mais curto em um grafo sem pesos. A complexidade de tempo é O(linhas * colunas), porque cada célula é visitada no máximo uma vez. A complexidade de espaço é O(linhas * colunas) para a fila e o conjunto de visitados. Os casos de borda incluem início ou fim bloqueados, origem igual ao destino, ausência de caminho e se movimentos na diagonal são permitidos.

Estrutura: Mapa de visitados do nó original para o nó clonado

Use um hash map que associa cada nó original ao seu clone. Durante a DFS ou a BFS, ao visitar um nó original, crie o clone dele se ainda não existir. Depois, clone cada vizinho de forma recursiva ou iterativa e adicione o vizinho clonado à lista de adjacência do nó clonado. O mapa de visitados resolve dois problemas: evita loops infinitos em grafos com ciclos e preserva as referências compartilhadas, para que o grafo clonado tenha a mesma topologia do original. A complexidade de tempo é O(V + E), em que V é o número de nós e E o de arestas. A complexidade de espaço é O(V) para o mapa e para a pilha ou fila da travessia, sem contar o grafo de saída. Os casos de borda incluem entrada nula, self-loops, grafos desconexos se o enunciado espera clonar só a partir de um nó inicial e vizinhos duplicados.

Estrutura: DP bottom-up sobre o valor

Defina dp[a] como o número mínimo de moedas necessário para formar o valor a. Inicialize dp[0] = 0 e todos os outros valores como infinito. Para cada valor de 1 até o alvo, teste todas as moedas. Se a - moeda não for negativo, dp[a] = min(dp[a], dp[a - moeda] + 1). No final, se dp[alvo] for infinito, retorne -1. A recorrência funciona porque a última moeda de uma solução ótima precisa ser um dos valores disponíveis. Se essa última moeda vale c, o valor restante é alvo - c, que também precisa ser resolvido de forma ótima. A complexidade de tempo é O(valor * número de moedas). A complexidade de espaço é O(valor). Os casos de borda incluem valor 0, valores impossíveis de formar, moeda de valor 1, valores de moeda duplicados e valores-alvo muito grandes.

Estrutura: DP pela posição final, depois otimização com busca binária

Uma solução de DP clara define dp[i] como o tamanho da maior subsequência crescente que termina no índice i. Para cada i, verifique todos os j anteriores. Se nums[j] < nums[i], então nums[i] pode estender a subsequência que termina em j, logo dp[i] = max(dp[i], dp[j] + 1). A resposta é max(dp). Isso leva tempo O(n^2) e espaço O(n). A abordagem otimizada em O(n log n) mantém um array tails, em que tails[length - 1] é o menor valor final possível de uma subsequência crescente com aquele tamanho. Para cada número, faça uma busca binária pelo primeiro elemento de tails maior ou igual a ele e substitua-o. O tamanho de tails é o tamanho da LIS. Na entrevista, é razoável apresentar primeiro a DP em O(n^2) se o tempo for curto e depois discutir a versão otimizada. Os casos de borda incluem duplicatas, arrays decrescentes, entrada vazia e se a subsequência precisa ser estritamente crescente.

Estrutura: Construir apenas prefixos válidos

Use backtracking com duas contagens: open (aberturas usadas) e close (fechamentos usados). Em cada passo, podemos adicionar um parêntese de abertura se open < n. Podemos adicionar um parêntese de fechamento se close < open. Essa segunda condição garante que todo prefixo continue válido, então nunca geramos strings inválidas que precisariam ser filtradas depois. Quando o tamanho da string atual chegar a 2n, adicione-a ao resultado. Assim exploramos apenas prefixos válidos e podamos cedo os estados impossíveis. O número de saídas válidas é o n-ésimo número de Catalan, então o tamanho da saída domina o tempo de execução. A complexidade de espaço inclui a profundidade de recursão O(n) mais a saída. Os casos de borda incluem n = 0 ou n = 1, dependendo de como o enunciado define o problema.

Estrutura: Requisitos -> API -> geração de IDs -> armazenamento -> caminho do redirecionamento -> escala

Requisitos: o usuário envia uma URL longa e recebe uma URL curta. Quando alguém acessa a URL curta, deve ser redirecionado rapidamente. Recursos opcionais incluem aliases personalizados, expiração, analytics, detecção de spam e contas de usuário. APIs principais: createShortUrl(longUrl, optionalAlias, expiration) e redirect(shortCode). Modelo de dados: shortCode, longUrl, userId, createdAt, expiresAt, status e metadados de analytics, se necessário. Para gerar os IDs, as opções incluem IDs auto-incrementais codificados em base62, códigos base62 aleatórios com verificação de colisão ou geração distribuída de IDs. O auto-incremento é simples, mas revela o volume de uso se não for ofuscado. IDs aleatórios são fáceis de distribuir, mas exigem tratamento de colisões. Em escala moderada, base62 aleatório com restrição de unicidade no banco é aceitável. O caminho de leitura é o que mais importa. O redirecionamento precisa ser rápido: buscar o shortCode no cache, recorrer ao banco se não estiver lá, validar expiração e status e então retornar HTTP 301 ou 302. Use 302 se analytics ou mudanças de destino forem importantes; use 301 para redirecionamentos permanentes, com cache mais agressivo no navegador. Escala: manter os códigos mais acessados em cache no Redis ou em cache de borda, fazer sharding por shortCode se necessário, gravar analytics de forma assíncrona por meio de uma fila, aplicar rate limit na criação e rodar verificações de spam e malware. Monitore a latência dos redirecionamentos, a taxa de acerto do cache, a taxa de erros, as denúncias de abuso e a saturação do banco de dados.

Estrutura: Usuários -> posts -> fanout -> ranqueamento -> leituras -> consistência

Esclareça o tipo de feed: feed social de quem você segue, feed de recomendações ou feed misto. Suponha um feed de quem você segue, em que usuários criam posts e os seguidores os veem ordenados por relevância ou por data. Objetos principais: usuários, relações de follow, posts, mídia, itens do feed, curtidas e comentários, e features de ranqueamento. As APIs incluem createPost, getFeed, followUser, unfollowUser e interactWithPost. Existem dois modelos comuns de geração de feed. O fanout-on-write empurra os novos posts para os feeds dos seguidores no momento em que o post é criado. Isso deixa as leituras rápidas, mas encarece as escritas para usuários com muitos seguidores. O fanout-on-read monta o feed na hora da requisição, buscando os posts de quem o usuário segue. Isso deixa as escritas baratas, mas as leituras mais lentas. Uma abordagem híbrida é comum: fanout-on-write para usuários normais e fanout-on-read ou tratamento especial para contas de celebridades. Arquitetura: o serviço de posts grava os posts, o serviço de grafo guarda as relações de follow, o serviço de feed mantém as timelines, o serviço de ranqueamento pontua os posts candidatos, o cache guarda os feeds mais acessados e a mídia vai para armazenamento de objetos e CDN. Use filas para o fanout assíncrono e para as atualizações de ranqueamento. Trade-offs: atualidade do feed versus qualidade do ranqueamento, consistência quando alguém segue ou deixa de seguir, tratamento de celebridades, invalidação de cache, spam, bloqueios de privacidade e backfill depois de falhas na fila. Monitore a latência de carregamento do feed, a atualidade, o atraso do fanout, o engajamento, a taxa de acerto do cache, os erros de ranqueamento e as denúncias de abuso.

Estrutura: Conexões -> fluxo de mensagens -> persistência -> entrega -> confiabilidade

Requisitos: mensagens individuais e em grupo, entrega online, entrega offline, histórico de mensagens, confirmações de leitura, indicadores de digitação e notificações push. Esclareça se criptografia de ponta a ponta, anexos e sincronização entre vários dispositivos são necessários. Os clientes mantêm conexões WebSocket com um serviço de gateway. Quando um usuário envia uma mensagem, o gateway a autentica, atribui ou recebe uma chave de idempotência, grava a mensagem em armazenamento durável, publica um evento e a entrega aos destinatários online pelas conexões ativas deles. Usuários offline recebem notificações push e podem buscar o histórico depois. Modelo de dados: conversa, participante, mensagem, estado de entrega, estado de leitura e dispositivo ou sessão. O armazenamento precisa de leituras eficientes por conversa e por tempo. Um banco relacional funciona em escala moderada; em escala maior, usam-se bancos distribuídos. Anexos devem ir para armazenamento de objetos, não para o banco de mensagens. Pontos de confiabilidade: envios duplicados, entrega fora de ordem, reconexões, mensagens perdidas, fanout para grupos grandes e precisão do status de presença. Use chaves de idempotência, números de sequência monotonicamente crescentes por conversa, confirmações de recebimento (acks), lógica de retry e APIs de sincronização a partir da última mensagem vista. Monitore a latência de envio, a taxa de sucesso de entrega, o número de conexões WebSocket, a taxa de reconexão, o atraso das filas, as falhas de notificações push e os erros de escrita no armazenamento.

Estrutura: Validar -> delimitar -> mudanças recentes -> análise por dependência -> mitigar

Primeiro, valide o sinal. Verifique se o aumento de latência aparece em mais de um sistema de monitoramento e se afeta o p50, o p95, o p99 ou só um endpoint específico. Confirme se o problema é visível para o usuário. Depois, delimite o problema por endpoint, região, zona de disponibilidade, segmento de clientes, versão, host, dependência e tipo de requisição. Um aumento global sugere uma dependência compartilhada ou um deploy. Um aumento localizado aponta para uma rota, query, cliente ou zona de infraestrutura específica. Em seguida, analise as mudanças recentes: deploys, alterações de configuração, migrações de banco, picos de tráfego, feature flags, mudanças de cache ou incidentes em serviços downstream. Quebre a latência por spans de serviço usando traces. Verifique o tempo das queries no banco, a taxa de acerto do cache, o atraso das filas, CPU, memória, garbage collection, thread pools, connection pools e APIs externas. Se os usuários estão sendo afetados, a mitigação vem antes de encontrar a causa raiz perfeita. Faça rollback, desligue uma feature flag, aumente a capacidade, contorne uma dependência lenta ou aumente o TTL do cache, se for seguro. Depois da recuperação, documente a causa raiz, a falha de detecção e o plano de prevenção.

Estrutura: Casos unitários -> limites -> entradas inválidas -> invariantes

Eu começaria esclarecendo as regras: tipos de desconto, se os descontos são cumulativos, expiração, valor mínimo de compra, elegibilidade do usuário, arredondamento da moeda e se impostos ou frete entram no cálculo. Os testes unitários devem cobrir casos normais, casos de limite, entradas inválidas e interações entre as regras. Exemplos: sem desconto, desconto percentual, desconto fixo, desconto maior que o subtotal, valor mínimo atingido exatamente, valor logo abaixo do mínimo, desconto expirado, usuário não elegível, vários descontos se isso for permitido e arredondamento de centavos. Eu também testaria invariantes: o preço final nunca deve ser negativo, o desconto não deve passar do subtotal elegível, promoções expiradas não devem ser aplicadas e repetir o cálculo deve dar sempre o mesmo resultado. Se isso envolver pagamentos, eu adicionaria testes de integração com o serviço de preços e snapshot tests para as faturas geradas. Para ter segurança em produção, eu registraria nos logs as decisões de desconto com códigos de motivo, para que o suporte e a engenharia consigam diagnosticar reclamações de preço sem precisar adivinhar.

Estrutura: Corretude -> manutenibilidade -> risco -> clareza

Eu reviso o código em camadas. Primeiro: ele resolve o problema proposto e mantém a corretude? Segundo: é fácil de manter, com nomes claros, limites bem definidos, sem complexidade desnecessária e com estilo consistente? Terceiro: qual é o risco, considerando migrações, concorrência, segurança, desempenho, compatibilidade com versões anteriores e observabilidade? Quarto: os testes cobrem bem o comportamento alterado? Um bom code review não é para mostrar superioridade. Ele deve melhorar o código sem travar o ritmo do time. Eu separo o que é bloqueante do que é sugestão. Um bug de corretude, um problema de segurança ou um risco de migração é bloqueante. Uma preferência de nome ou uma pequena refatoração pode não ser. Também procuro contexto que esteja faltando: comportamento de produto pouco claro, casos de borda sem teste, caminhos que falham em silêncio, tratamento de erros fraco e falta de métricas em mudanças arriscadas.

Estrutura: Contexto -> opções -> trade-offs -> decisão -> resultado

Escolha uma decisão com trade-offs reais: construir ou comprar, SQL ou NoSQL, monólito ou serviço, correção rápida ou refatoração mais profunda, consistência forte ou disponibilidade. Comece pelo contexto e pelas restrições e depois explique as opções que você considerou. Uma resposta forte deixa o trade-off bem claro. Por exemplo: “A opção A nos permitia entregar em uma semana, mas aumentava a carga operacional. A opção B levava três semanas, mas eliminava um gargalo de escala.” Em seguida, explique quais evidências guiaram a decisão: tráfego, prazo do cliente, histórico de incidentes, capacidade do time ou roadmap de longo prazo. Feche com o resultado e com o que você aprendeu. Se a decisão não foi perfeita, diga o que faria diferente. Os entrevistadores valorizam mais um julgamento maduro do que fingir que toda decisão era óbvia.

Estrutura: Incidente -> impacto -> resposta -> causa raiz -> prevenção

Use um incidente real, se possível. Comece pelo impacto no usuário: o que quebrou, quem foi afetado e qual foi a gravidade. Depois explique o seu papel na resposta: detecção, triagem, rollback, mitigação, comunicação ou análise de causa raiz. As melhores respostas mostram priorização com calma. Durante um incidente, restabelecer o serviço importa mais do que provar uma teoria. Mencione como você usou logs, métricas, traces, feature flags, rollbacks ou verificações de dependências. Depois da mitigação, explique a causa raiz e a prevenção. Uma boa prevenção pode incluir testes melhores, rollouts mais seguros, monitoramento, ajuste de alertas, runbooks, circuit breakers, backpressure ou salvaguardas em migrações. Evite culpar pessoas. Times fortes melhoram os sistemas para que o mesmo erro fique mais difícil de se repetir.

Estrutura: Objetivo comum -> restrições -> opções -> trade-offs -> decisão

Eu começo alinhando o objetivo do usuário e o objetivo de negócio. Muitas discordâncias não são, de fato, engenharia contra produto; são premissas diferentes. Eu explicaria a restrição técnica com clareza: complexidade, risco de confiabilidade, prazo, manutenibilidade, segurança ou desempenho. Depois eu proporia opções em vez de simplesmente dizer não. Por exemplo: lançar um MVP menor, usar temporariamente um fluxo manual, esconder a funcionalidade atrás de uma feature flag, sequenciar o trabalho técnico ou escolher um design mais simples que ainda resolva o problema central do usuário. Se o trade-off for sério, eu documento as opções, os riscos e a minha recomendação, para que a decisão seja transparente. O objetivo não é a engenharia ganhar a discussão. O objetivo é o time tomar uma decisão clara, de olhos abertos.