Entrevistas de algoritmos: reconheça o padrão antes do código

ENTENDA A IDEIA

A ideia central

Uma entrevista entrega um enunciado novo, mas quase nunca exige um mecanismo novo. Pense em uma oficina com poucas ferramentas: a peça muda, porém a forma do corte indica qual ferramenta usar. Um array ordenado permite eliminar metades. Um intervalo contínuo sugere uma janela. Uma rede de conexões pede uma fronteira de exploração. Uma sequência de escolhas pede tentativa, retorno e restauração. O primeiro trabalho não é escrever código. O primeiro trabalho é descobrir a forma do problema.

ENTENDA A IDEIA

A ideia central

Use quatro perguntas para esclarecer o contrato. Qual é a entrada real, inclusive limites e possibilidade de vazio? Qual é a saída exata, inclusive desempates? A função pode modificar a entrada ou deve apenas emprestá-la? O que acontece com duplicatas, valores negativos e resultados ausentes? Essas perguntas evitam resolver uma versão imaginária do problema. Em Rust, elas também definem a assinatura: &[T] comunica leitura emprestada, &mut [T] comunica alteração no lugar e Vec<T> por valor comunica transferência de ownership. Ownership é a regra que atribui um dono a cada valor; uma função deve tomar posse somente quando precisa guardar ou consumir o dado.

ENTENDA A IDEIA

A ideia central

Depois, procure pistas de reconhecimento. “Ordenado”, “primeiro que satisfaz” e “menor valor possível” apontam para busca binária. “Subarray”, “substring”, “contíguo” e “no máximo” costumam apontar para janela deslizante ou prefixos. “Par em array ordenado” sugere dois ponteiros. “Menor número de passos sem pesos” sugere BFS. “Todas as combinações” sugere backtracking. A pista não prova a solução. Ela seleciona uma hipótese que você deve validar com um invariante.

Um invariante é uma afirmação que continua verdadeira antes e depois de cada passo. Declare-o antes da implementação. No programa desta aula, o invariante é: antes de processar value, o conjunto seen contém exatamente os valores em índices anteriores. Portanto, se o complemento já está em seen, ele vem de outro índice. Se não está, inserir value prepara o próximo passo. Essa frase explica a ordem “consultar e depois inserir”, prova que um elemento não forma par consigo mesmo e cobre duplicatas como [6, 6].

ENTENDA A IDEIA

A ideia central

Feche o método com testes pequenos que atacam a promessa. Use vazio para testar o estado inicial. Use singleton para testar o menor espaço não vazio. Use duplicatas para testar identidade de índices. Use empate quando a saída exige uma escolha estável. Use os limites numéricos para expor overflow. Faça também um teste que contradiz a sua primeira intuição. Um exemplo feliz mostra que o código pode funcionar; um caso de borda mostra se o raciocínio continua válido.

ENTENDA A IDEIA

A ideia central

Durante a conversa, separe solução, prova e implementação. Primeiro, apresente uma força bruta correta. Segundo, diga qual trabalho ela repete. Terceiro, proponha o estado que elimina a repetição. Por fim, derive os custos e escreva o código. Essa ordem evita o silêncio enquanto você procura a solução ideal. Ela também permite que o entrevistador corrija uma premissa antes de você investir em detalhes. Uma solução incompleta com raciocínio explícito oferece mais informação do que um bloco de código rápido sem contrato. Diga também quais premissas ainda precisam de confirmação.

ENTENDA A IDEIA

A ideia central

Use um exemplo mínimo como instrumento de prova. Para o par com soma, trace [6] e [6, 6]. O primeiro caso proíbe reutilizar o índice; o segundo exige aceitar valores duplicados em posições diferentes. Para uma busca de fronteira, trace zero, um e dois elementos. Para uma janela, trace o primeiro ponto em que a condição quebra. O objetivo não é simular uma entrada grande. O objetivo é escolher a menor entrada que diferencia duas implementações plausíveis.

CÓDIGO ANOTADO

Código anotado

O programa completo resolve a existência de um par com soma alvo. A força bruta testaria todos os pares. Aqui, cada valor pergunta por um único complemento entre os valores anteriores. O tipo i128 protege a aritmética: subtrair dois i64 diretamente pode estourar mesmo quando a resposta final do problema cabe em i64.

Rust 2021 · src/main.rs

use std::collections::HashSet;

// has_pair_sum procura dois índices distintos cuja soma é target.
fn has_pair_sum(values: &[i64], target: i64) -> bool {
    let mut seen = HashSet::with_capacity(values.len());

CÓDIGO ANOTADO

Código anotado

A função recebe &[i64], uma fatia emprestada. Ela não toma posse do Vec do chamador e não pode modificar os elementos. O conjunto é propriedade local da função porque ele representa estado temporário. with_capacity reserva espaço aproximado e reduz realocações, mas não altera a complexidade assintótica.

Rust 2021 · src/main.rs

    for &value in values {
        let wide_value = i128::from(value);
        let complement = i128::from(target) - wide_value;
        if seen.contains(&complement) {
            return true;
        }

CÓDIGO ANOTADO

Código anotado

A desestruturação for &value copia cada i64; esse tipo implementa Copy, então a fatia continua intacta. A consulta ocorre antes da inserção. No primeiro 6 de [6, 6], o conjunto está vazio. No segundo, o conjunto contém o primeiro 6, e a função encontra dois índices distintos.

Rust 2021 · src/main.rs

        seen.insert(wide_value);
    }
    false
}

CÓDIGO ANOTADO

Código anotado

O false só aparece depois que o espaço inteiro foi processado. Retornar falha dentro de um else após a primeira comparação seria o erro clássico da busca linear: o algoritmo confundiria “este elemento não serve” com “nenhum elemento serve”. O invariante impede essa conclusão antecipada.

Rust 2021 · src/main.rs

fn main() {
    let values = [3, 8, 5, 1];
    for target in [9, 14, 20] {
        println!("alvo {target}: {}", has_pair_sum(&values, target));
    }

CÓDIGO ANOTADO

Código anotado

O main mantém o array na pilha e empresta a mesma fatia para três consultas. Nenhuma chamada consome values. Essa escolha é importante em entrevistas: uma API emprestada permite novos testes sem clone e torna a ausência de mutação verificável pela assinatura.

A primeira lista produz true, true, false. O caso de limite produz true, pois i64::MAX + i64::MIN é -1. A soma matemática está correta. O algoritmo nunca executa uma soma em i64; ele calcula o complemento em i128, cuja faixa comporta qualquer diferença entre dois valores de i64.

Derive o custo pelo estado visitado e pelo dado armazenado. O loop visita cada um dos n elementos uma vez. Cada consulta e inserção no HashSet custa O(1) esperado, então o tempo esperado é O(n). O conjunto pode guardar todos os valores, logo o espaço auxiliar é O(n). A alternativa com dois loops usa O(1) de espaço, mas visita n(n-1)/2 pares: O(n²). A escolha é uma troca explícita de memória por tempo.

A garantia do mapa não vem do nome da estrutura. Um HashSet pode aparecer em uma solução O(n²) se o código reconstruir o conjunto dentro de outro loop. Uma busca binária pode virar O(n) se, depois de achar uma ocorrência, o código caminhar por todas as duplicatas. Derive sempre a complexidade do fluxo completo. Conte quantas vezes cada estado é visitado e qual coleção pode crescer com a entrada.

Também separe o espaço da resposta do espaço auxiliar. Se uma função precisa devolver um novo Vec com n elementos, a resposta já custa O(n); isso não significa que o algoritmo usou O(n) de memória auxiliar além do retorno. Em entrevistas, diga as duas medidas quando a distinção importa. Nesta função, o retorno é apenas um bool, então todo o HashSet conta como espaço auxiliar.

Rust 2021 · src/main.rs

    let boundary = [i64::MAX, i64::MIN];
    println!("limite -1: {}", has_pair_sum(&boundary, -1));
}

PASSO A PASSO

Mapa de reconhecimento de padrões

VISUALIZAÇÃOMapa de reconhecimento de padrões

1 / 6

EXPERIMENTE

Pratique no seu computador

Antes de executar, preveja a quantidade de comparações das duas funções para um alvo ausente. A primeira testa todos os pares. A segunda consulta um conjunto uma vez por elemento. Depois, altere size de 8 para 16 e compare os contadores. O contador quadrático deve crescer de 28 para 120; o linear deve crescer de 8 para 16.

Faça três mudanças. Primeiro, use target = 1 e pare os loops quando houver resposta; compare o melhor caso com o pior caso. Segundo, troque a ordem da consulta e da inserção na versão com conjunto; explique por que [6] com alvo 12 passaria a responder true de forma incorreta. Terceiro, troque i128 por i64 e use target = i64::MIN com value = 1; em compilação de depuração, a subtração estoura. Preveja a mensagem antes de executar.

A pergunta final é: qual afirmação precisa continuar verdadeira no início de cada iteração? Escreva o invariante em uma frase. Se a frase não mencionar “índices anteriores”, ela ainda não explica por que os dois elementos são distintos.

Altere o código. Os controles mostram a execução disponível para este trecho.

Rust 2021 · Pratique no seu computador

use std::collections::HashSet;

fn main() {
    let size = 8_i64;
    let values: Vec<i64> = (0..size).collect();
    let target = -1_i64;

    let mut pair_checks = 0_u64;
    for left in 0..values.len() {
        for right in left + 1..values.len() {
            pair_checks += 1;
            let _ = i128::from(values[left]) + i128::from(values[right]) == i128::from(target);
        }
    }

    let mut seen = HashSet::new();
    let mut set_checks = 0_u64;
    for &value in &values {
        set_checks += 1;
        let complement = i128::from(target) - i128::from(value);
        let _ = seen.contains(&complement);
        seen.insert(i128::from(value));
    }

    println!("pares: {pair_checks}");
    println!("consultas: {set_checks}");
}

DESAFIO

Encontre a primeira ocorrência

Implemente linear_search, que devolve o índice da primeira ocorrência de target ou None quando o alvo não existe.

pub fn linear_search(values: &[i32], target: i32) -> Option<usize>

A entrada é uma fatia que pode estar vazia e pode conter duplicatas. A saída usa Option: Some(index) representa uma posição válida; None representa ausência. Para [4, 7, 1, 9] e alvo 1, devolva Some(2). Para [3, 3, 3] e alvo 3, devolva Some(0), não uma ocorrência qualquer.

Use uma única passagem. Não ordene, não aloque e não modifique a entrada. O caso com i32::MIN confirma que nenhum valor sentinela representa ausência; a ausência está no tipo Option.

Edite stub.rs. Os controles mostram a execução disponível para este exercício.

Rust 2021 · stub.rs

// linear_search devolve o índice da primeira ocorrência de target.
pub fn linear_search(values: &[i32], target: i32) -> Option<usize> {
    // implemente:
    let _ = (values, target);
    None
}

Arquivos, contrato, dicas e solução

Exercício 1

Encontre a primeira ocorrência

stub.rs

// linear_search devolve o índice da primeira ocorrência de target.
pub fn linear_search(values: &[i32], target: i32) -> Option<usize> {
    // implemente:
    let _ = (values, target);
    None
}

harness.rs

fn json_escape(value: &str) -> String {
    value
        .replace('\\', "\\\\")
        .replace('"', "\\\"")
        .replace('\n', "\\n")
}

fn print_result(case: usize, pass: bool, input: &str, want: &str, got: &str) {
    println!(
        "RESULT {{\"case\":{case},\"pass\":{pass},\"input\":\"{}\",\"want\":\"{}\",\"got\":\"{}\"}}",
        json_escape(input),
        json_escape(want),
        json_escape(got)
    );
}

fn main() {
    let cases: &[(&[i32], i32, &str, Option<usize>)] = &[
        (&[4, 7, 1, 9], 1, "values=[4,7,1,9], target=1", Some(2)),
        (&[4, 7, 1, 9], 5, "values=[4,7,1,9], target=5", None),
        (&[3, 3, 3], 3, "values=[3,3,3], target=3", Some(0)),
        (&[], 8, "values=[], target=8", None),
        (
            &[i32::MIN],
            i32::MIN,
            "values=[-2147483648], target=-2147483648",
            Some(0),
        ),
    ];
    for (index, &(values, target, input, want)) in cases.iter().enumerate() {
        let got = linear_search(values, target);
        print_result(
            index + 1,
            got == want,
            input,
            &format!("{want:?}"),
            &format!("{got:?}"),
        );
    }
}

cases.json

[
  {
    "case": 1,
    "input": "values=[4,7,1,9], target=1",
    "want": "Some(2)"
  },
  {
    "case": 2,
    "input": "values=[4,7,1,9], target=5",
    "want": "None"
  },
  {
    "case": 3,
    "input": "values=[3,3,3], target=3",
    "want": "Some(0)"
  },
  {
    "case": 4,
    "input": "values=[], target=8",
    "want": "None"
  },
  {
    "case": 5,
    "input": "values=[-2147483648], target=-2147483648",
    "want": "Some(0)"
  }
]

Casos e valores esperados

Caso	Entrada	Valor esperado
1	`values=[4,7,1,9], target=1`	`Some(2)`
2	`values=[4,7,1,9], target=5`	`None`
3	`values=[3,3,3], target=3`	`Some(0)`
4	`values=[], target=8`	`None`
5	`values=[-2147483648], target=-2147483648`	`Some(0)`

Execute com o Cargo local

Execute os comandos de preparação.
Copie os arquivos acima para os arquivos vazios com os mesmos nomes.
Execute a verificação de base. O stub deve mostrar o comportamento atual.

Comandos de preparação

cargo new --bin --edition 2024 entrevistas-01-mapa-de-padroes-exercicio-1
cd entrevistas-01-mapa-de-padroes-exercicio-1
touch stub.rs harness.rs cases.json
printf 'include!("../stub.rs");\ninclude!("../harness.rs");\n' > src/main.rs

Verificação de base — confirme o comportamento atual antes da mudança

cargo fmt --check
cargo run --bin entrevistas-01-mapa-de-padroes-exercicio-1
cargo clippy -- -D warnings

Abrir o Rust Playground (opcional)

Mostrar dicas

Percorra a fatia por referência e pare na primeira igualdade; o índice faz parte do resultado.
O método position de Iterator devolve Option<usize> e já preserva a primeira ocorrência.

Revelar solução

solution.rs

// linear_search devolve o índice da primeira ocorrência de target.
pub fn linear_search(values: &[i32], target: i32) -> Option<usize> {
    values.iter().position(|&value| value == target)
}

Uma passagem com position devolve a primeira ocorrência em O(n), não move a fatia e cobre a entrada vazia com None.

pub fn linear_search(values: &[i32], target: i32) -> Option<usize> {
    values.iter().position(|&value| value == target)
}

iter produz referências compartilhadas. O padrão |&value| copia cada i32, e position encerra a passagem na primeira igualdade. A função não toma ownership, não aloca e preserva o array do chamador. Para a fatia vazia, o iterador não produz itens e devolve None.

O tempo é O(n) no pior caso: o alvo está no fim ou não existe. O espaço auxiliar é O(1), pois o iterador mantém somente a posição atual. A alternativa manual com for (index, value) in values.iter().enumerate() tem os mesmos custos e também é correta. Ela pode ser preferível quando a comparação precisa de mais etapas.

A armadilha comum é devolver None no else da primeira comparação. Esse código decide que o alvo não existe depois de examinar somente a posição zero. Outra armadilha é usar um índice numérico especial, como usize::MAX, para ausência. Option<usize> torna os dois estados explícitos e força o chamador a tratar cada um.

DESAFIO

Detecte um par com soma alvo

Implemente has_pair_sum, que informa se existem dois índices distintos cujos valores somam target.

pub fn has_pair_sum(values: &[i64], target: i64) -> bool

A fatia pode estar vazia, pode conter negativos e pode conter valores repetidos. [6] com alvo 12 deve devolver false, pois um índice não pode ser usado duas vezes. [6, 6] deve devolver true. O par [i64::MAX, i64::MIN] com alvo -1 também deve devolver true sem overflow.

Faça uma única passagem esperada O(n). Use somente a biblioteca padrão. Não dependa da ordem de iteração do HashSet; o algoritmo precisa apenas consultar presença. Calcule complementos em um tipo largo.

Edite stub.rs. Os controles mostram a execução disponível para este exercício.

Rust 2021 · stub.rs

// has_pair_sum informa se dois índices distintos somam target.
pub fn has_pair_sum(values: &[i64], target: i64) -> bool {
    // implemente:
    let _ = (values, target);
    false
}

Arquivos, contrato, dicas e solução

Exercício 2

Detecte um par com soma alvo

stub.rs

// has_pair_sum informa se dois índices distintos somam target.
pub fn has_pair_sum(values: &[i64], target: i64) -> bool {
    // implemente:
    let _ = (values, target);
    false
}

harness.rs

fn json_escape(value: &str) -> String {
    value
        .replace('\\', "\\\\")
        .replace('"', "\\\"")
        .replace('\n', "\\n")
}

fn print_result(case: usize, pass: bool, input: &str, want: &str, got: &str) {
    println!(
        "RESULT {{\"case\":{case},\"pass\":{pass},\"input\":\"{}\",\"want\":\"{}\",\"got\":\"{}\"}}",
        json_escape(input),
        json_escape(want),
        json_escape(got)
    );
}

fn main() {
    let cases: &[(&[i64], i64, &str, bool)] = &[
        (&[3, 8, 5, 1], 9, "values=[3,8,5,1], target=9", true),
        (&[6], 12, "values=[6], target=12", false),
        (&[6, 6], 12, "values=[6,6], target=12", true),
        (&[], 0, "values=[], target=0", false),
        (&[-4, 10, 2], 6, "values=[-4,10,2], target=6", true),
        (
            &[i64::MAX, i64::MIN],
            -1,
            "values=[9223372036854775807,-9223372036854775808], target=-1",
            true,
        ),
    ];
    for (index, &(values, target, input, want)) in cases.iter().enumerate() {
        let got = has_pair_sum(values, target);
        print_result(
            index + 1,
            got == want,
            input,
            &want.to_string(),
            &got.to_string(),
        );
    }
}

cases.json

[
  {
    "case": 1,
    "input": "values=[3,8,5,1], target=9",
    "want": "true"
  },
  {
    "case": 2,
    "input": "values=[6], target=12",
    "want": "false"
  },
  {
    "case": 3,
    "input": "values=[6,6], target=12",
    "want": "true"
  },
  {
    "case": 4,
    "input": "values=[], target=0",
    "want": "false"
  },
  {
    "case": 5,
    "input": "values=[-4,10,2], target=6",
    "want": "true"
  },
  {
    "case": 6,
    "input": "values=[9223372036854775807,-9223372036854775808], target=-1",
    "want": "true"
  }
]

Casos e valores esperados

Caso	Entrada	Valor esperado
1	`values=[3,8,5,1], target=9`	`true`
2	`values=[6], target=12`	`false`
3	`values=[6,6], target=12`	`true`
4	`values=[], target=0`	`false`
5	`values=[-4,10,2], target=6`	`true`
6	`values=[9223372036854775807,-9223372036854775808], target=-1`	`true`

Execute com o Cargo local

Execute os comandos de preparação.
Copie os arquivos acima para os arquivos vazios com os mesmos nomes.
Execute a verificação de base. O stub deve mostrar o comportamento atual.

Comandos de preparação

cargo new --bin --edition 2024 entrevistas-01-mapa-de-padroes-exercicio-2
cd entrevistas-01-mapa-de-padroes-exercicio-2
touch stub.rs harness.rs cases.json
printf 'include!("../stub.rs");\ninclude!("../harness.rs");\n' > src/main.rs

Verificação de base — confirme o comportamento atual antes da mudança

cargo fmt --check
cargo run --bin entrevistas-01-mapa-de-padroes-exercicio-2
cargo clippy -- -D warnings

Abrir o Rust Playground (opcional)

Mostrar dicas

Para cada valor, pergunte se o complemento já apareceu; consulte antes de inserir para não reutilizar o mesmo índice.
Use HashSet<i128> e calcule target - value em i128 para cobrir os limites de i64 sem overflow.

Revelar solução

solution.rs

use std::collections::HashSet;

// has_pair_sum informa se dois índices distintos somam target.
pub fn has_pair_sum(values: &[i64], target: i64) -> bool {
    let mut seen = HashSet::with_capacity(values.len());
    for &value in values {
        let wide_value = i128::from(value);
        let complement = i128::from(target) - wide_value;
        if seen.contains(&complement) {
            return true;
        }
        seen.insert(wide_value);
    }
    false
}

Um HashSet dos valores anteriores troca O(n²) por O(n) esperado; i128 mantém a subtração do complemento correta nos limites de i64.

use std::collections::HashSet;

pub fn has_pair_sum(values: &[i64], target: i64) -> bool {
    let mut seen = HashSet::with_capacity(values.len());
    for &value in values {
        let wide_value = i128::from(value);
        let complement = i128::from(target) - wide_value;
        if seen.contains(&complement) {
            return true;
        }
        seen.insert(wide_value);
    }
    false
}

O conjunto representa exatamente o prefixo já processado. Consultar antes de inserir garante índices distintos e trata duplicatas corretamente. O uso de i128 evita o overflow de target - value; qualquer i64 cabe sem perda em i128.

O algoritmo visita n valores. Com operações esperadas O(1) do HashSet, o tempo esperado é O(n). O espaço auxiliar é O(n) no pior caso. A força bruta visita todos os pares em O(n²) e usa O(1) de espaço; ela é uma alternativa válida quando a memória é muito limitada ou a entrada é minúscula. Ordenar e usar dois ponteiros custa O(n log n), exige uma cópia para preservar a entrada e pode destruir posições originais.

A armadilha aritmética é calcular o complemento em i64. Em Rust, overflow em depuração causa panic; em outras configurações, depender de aritmética modular resolveria outro problema. Tornar o domínio intermediário maior faz o código corresponder à soma matemática do contrato.

ENTENDA A IDEIA

A ideia central

Comece a assinatura por empréstimo. Use &[T] quando a função apenas lê uma sequência e &mut [T] quando ela modifica no lugar. Receber Vec<T> por valor toma ownership e impede o chamador de reutilizar a coleção sem um retorno ou um clone. Essa escolha deve vir do contrato, não do hábito.

Use iteradores quando eles expressam a operação completa, como position. Use um loop explícito quando o invariante depende de estado, como o conjunto de valores anteriores. Os dois estilos compilam para código eficiente. O critério é tornar a prova visível: a leitura deve mostrar quais estados existem, quando mudam e por que a resposta é correta.

RESUMO DA AULA

O que você leva desta aula

Esclareça entrada, saída, mutação, duplicatas, desempates e limites antes do código.
Reconheça pistas da forma: ordem, intervalo contínuo, pares, conexões ou escolhas.
Declare um invariante antes da implementação e use cada atualização para preservá-lo.
Derive o tempo pelos estados visitados e o espaço pelos dados armazenados.
Teste vazio, singleton, duplicatas, ausência e limites aritméticos quando a assinatura permitir.
A próxima aula, Big-O na prática, transforma essas contagens em uma análise precisa de tempo e espaço.

+175 XPpossíveis nesta aula

A ideia central

A ideia central

A ideia central

A ideia central

A ideia central

A ideia central

Código anotado

Código anotado

Código anotado

Código anotado

Código anotado

Mapa de reconhecimento de padrões

Pratique no seu computador

Encontre a primeira ocorrência

Casos e valores esperados

Execute com o Cargo local

Detecte um par com soma alvo

Casos e valores esperados

Execute com o Cargo local

A ideia central

O que você leva desta aula

Você transformou esta ideia em prática.