Voltar ao Blog
Coding Challenges3 de julho de 202412 min de leitura

Problema da Soma de Pares (Passo a Passo). Entrevistas Whiteboard

DR

Doug Ribeiro

12 min de leitura

Entrevistas whiteboard testam mais do que velocidade na resolução de problemas. Elas avaliam comunicação, clareza e pensamento estruturado. O método REACTO te dá um framework repetível: Repeat, Examples, Approach, Code, Test, Optimize. Os entrevistadores querem ouvir seu raciocínio em voz alta. Uma explicação limpa sem resposta final supera uma solução apressada sem explicação.

Repeat Examples Approach Code Test Optimize

O Problema Central

Dado um array de números e uma soma alvo, determine se quaisquer dois números no array somam ao alvo. Retorne um booleano.

  • Array [1, 2, 3, 9] com soma 8 → retorna false (nenhum par válido)
  • Array [1, 2, 4, 4] com soma 8 → retorna true (4 + 4 = 8)

R. Repita a Pergunta

Entrada: um array de inteiros e uma soma alvo. Saída: um booleano. True se quaisquer dois números somam ao alvo, false caso contrário.

Esclarecimentos para abordar em voz alta:

  • Retornar o par ou apenas um booleano? → Apenas booleano
  • Os números podem ser negativos ou desordenados? → Sim
  • O mesmo elemento pode ser usado duas vezes? → Não, devem ser dois índices distintos
  • E se o array estiver vazio ou tiver um único elemento? → Retorne false

E. Exemplos de Casos

Antes de tocar em código, percorra exemplos com o entrevistador. Confirme seu entendimento dos casos extremos. Array vazio, elemento único, duplicatas, negativos. É aqui que muitos candidatos perdem pontos por pular rápido demais.

  • [1, 2, 3, 9] alvo 8 → false
  • [1, 2, 4, 4] alvo 8 → true (4 + 4)
  • [-1, 5, 3] alvo 4 → true (-1 + 5)
  • [] alvo 5 → false
  • [5] alvo 5 → false (precisa de dois elementos distintos)

A. Abordagem

Força Bruta. O(n²)

Loops aninhados: para cada elemento, verifique todos os outros elementos. Simples de explicar mas não escala. Mencione isso primeiro. Os entrevistadores apreciam saber que você entende a solução ingênua antes de otimizar.

Otimizado. HashSet O(n)

Use um Set para rastrear números já vistos. Para cada elemento, calcule seu complemento (alvo menos o atual). Se o complemento já está no Set, um par válido existe. Caso contrário, armazene o número atual e continue. Uma passagem pelo array, lookup O(1) por passo.

C. Código

typescript 
function hasPairWithSum(arr: number[], sum: number): boolean {
  const seen = new Set<number>();

  for (const num of arr) {
    const complement = sum - num;

    if (seen.has(complement)) {
      return true;
    }

    seen.add(num);
  }

  return false;
}

console.log(hasPairWithSum([1, 2, 3, 9], 8));  // false
console.log(hasPairWithSum([1, 2, 4, 4], 8));  // true
console.log(hasPairWithSum([-1, 5, 3], 4));    // true

T. Teste Sua Solução

Percorra o algoritmo manualmente com [1, 2, 4, 4], sum=8:

  • num=1: complemento=7, não está em seen. Adiciona 1. seen={1}
  • num=2: complemento=6, não está em seen. Adiciona 2. seen={1,2}
  • num=4: complemento=4, não está em seen. Adiciona 4. seen={1,2,4}
  • num=4: complemento=4, ESTÁ em seen → retorna true

Agora teste um caso extremo: array vazio. O loop nunca executa, retorna false. Elemento único [5] com soma 10: uma iteração, complemento=5, seen está vazio, adiciona 5, loop termina, retorna false. Comportamento correto.

O. Otimize e Discuta Tradeoffs

A solução com HashSet já é O(n) em tempo e O(n) em espaço. Se o entrevistador perguntar sobre reduzir espaço: um array ordenado com dois ponteiros alcança O(n log n) em tempo e O(1) em espaço adicional, mas só se a ordenação for in place. Array.prototype.sort no V8 é TimSort, que usa O(n) de memória auxiliar e muta o array que você passa, então ordenar uma cópia te devolve a O(n) em espaço. Qual é melhor depende das restrições. Se a entrada já está ordenada e memória é limitada, dois ponteiros vence.

typescript 
// Two-pointer approach (requires sorted input)
function hasPairWithSumSorted(arr: number[], sum: number): boolean {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const current = arr[left] + arr[right];
    if (current === sum) return true;
    if (current < sum) left++;
    else right--;
  }

  return false;
}

// Input must be sorted
console.log(hasPairWithSumSorted([1, 2, 3, 9], 8));  // false
console.log(hasPairWithSumSorted([1, 2, 4, 4], 8));  // true

Bônus: Dados em Streaming

Um entrevistador pode estender o problema: e se a entrada for um stream em vez de um array finito? Você pode aplicar a mesma lógica de HashSet usando um generator, mas com uma ressalva importante: se nenhum par existir no stream, a função nunca termina. Em uma entrevista, nomear essa limitação explicitamente demonstra maturidade.

typescript 
function hasPairWithSumStream(
  stream: Iterable<number>,
  sum: number,
  limit = 10_000  // guard against infinite streams with no solution
): boolean {
  const seen = new Set<number>();
  let count = 0;

  for (const num of stream) {
    if (count++ >= limit) return false;  // safety exit: false here means 'not found within limit'
    const complement = sum - num;
    if (seen.has(complement)) return true;
    seen.add(num);
  }

  return false;
}

// Example: finite generator
function* numberStream(values: number[]) {
  for (const v of values) yield v;
}

console.log(hasPairWithSumStream(numberStream([1, 2, 4, 4]), 8));  // true

Leia esse guard com atenção, porque ele muda o significado da função. Retornar false depois do limite diz 'nenhum par existe', quando tudo o que o código sabe é 'nenhum par nos primeiros 10.000 valores'. Isso é um falso negativo, e é a metade mais interessante do tradeoff. Se quem chama precisa distinguir os dois casos, retorne três estados em vez de um booleano: encontrado, não encontrado, limite atingido. Nomear o que a sua saída de segurança custa vale mais em uma entrevista do que o próprio guard.

Conceitos-Chave Para Dominar

Set. Armazena valores únicos com operações add e has em O(1) em média, e diga 'em média' em voz alta, porque o hashing degrada no pior caso. Mais eficiente que um array para verificações de pertencimento. A estrutura de dados central por trás dessa solução.

for...of. Itera sobre qualquer iterável (array, Set, saída de generator). Sem necessidade de gerenciamento de índice, funciona de forma limpa com generators.

Funções generator. Pausam e retomam execução usando yield. Retornam um iterador que produz valores sob demanda. Úteis para simular streams ou sequências lazy. O ponto-chave na entrevista: generators são lazy, mas se não há condição de terminação e o problema não tem solução, a iteração nunca para.

Em uma entrevista, a qualidade da sua explicação é tão valiosa quanto a corretude do seu código. Percorra o algoritmo passo a passo, teste sua própria solução em voz alta e nomeie os tradeoffs antes que o entrevistador pergunte.

Referências

JavaScriptTypeScriptCoding Challenges

Posts Relacionados

Coding Challenges8 min de leitura

A Técnica de Sliding Window: Um Padrão de Entrevista Whiteboard

O padrão sliding window cobre toda uma categoria de problemas de arrays e strings. Uma vez que ele faz sentido, você para de reinventar a solução e começa a aplicar um template.

Angular Development10 min de leitura

Utility Types do TypeScript Que Todo Desenvolvedor Angular Deveria Conhecer

Parei de escrever definições de tipo redundantes depois que comecei a realmente usar os utility types nativos. Aqui está como eles ficam em código Angular real.

Angular Development7 min de leitura

Debounce vs Throttle: A Diferença Que Vai Salvar Sua App Angular

Usar throttle em um input de busca e debounce em um handler de scroll são ambos bugs. Veja como nunca mais confundir os dois.