Como passar em entrevistas de algoritmos: o mapa de padrões

Um range com retorno antecipado resolve. O ponto que separa uma implementação limpa de uma com bug é a posição do -1: ele só pode existir depois do loop, quando todas as posições já falharam.

func LinearSearch(values []int, target int) int {
	for index, value := range values {
		if value == target {
			return index
		}
	}
	return -1
}

Complexidade: O(n) tempo no pior caso — o alvo está no fim ou não está —, O(1) espaço. Para um slice nil ou vazio o range não executa nenhuma iteração e a função devolve -1 direto, sem caso especial.

A armadilha da alternativa: escrever if value == target { return index } else { return -1 } dentro do loop. Esse código compila e passa no teste em que o alvo está na posição 0 — e devolve -1 errado para qualquer outra posição, porque decide o fracasso olhando só o primeiro elemento. É o bug mais comum de quem está começando, e o motivo de os casos de teste incluírem o alvo no meio e no fim. A regra que você vai reutilizar a trilha inteira: só declare fracasso quando o espaço de busca acabar.

A pergunta que destrava o problema é “já vi este valor antes?” — e a estrutura de Go que responde isso em O(1) é um map usado como conjunto. Percorra uma vez; se o valor já está no conjunto, ele é a resposta; senão, registre e siga.

func FirstDuplicate(values []int) int {
	seen := make(map[int]bool, len(values))
	for _, value := range values {
		if seen[value] {
			return value
		}
		seen[value] = true
	}
	return -1
}

Complexidade: O(n) tempo e O(n) espaço — o conjunto pode guardar quase todos os valores no pior caso. Consultar uma chave ausente em um map devolve o zero value de bool (false), então não é preciso o idioma valor, ok := aqui; a aula 3 detalha quando ele é obrigatório.

A armadilha da alternativa: o par de loops aninhados — para cada i, procurar values[i] em values[i+1:] — tem dois problemas. O óbvio é o custo O(n²), que estoura o tempo em entradas grandes. O sutil é que ele calcula outra coisa: encontra o valor cuja primeira ocorrência vem mais cedo entre os repetidos, não o que repete mais cedo. Em [2 5 3 5 2] a versão aninhada devolve 2; a especificação pede 5. Força bruta que devolve a resposta errada com convicção é pior que força bruta lenta — e é por isso que reformular o problema (“primeira segunda-ocorrência”) antes de codar vale tanto quanto conhecer a estrutura de dados.

Reformule: para cada value, o parceiro necessário é exatamente target - value. Se esse complemento já passou pelo loop, o par existe. Um conjunto dos valores já vistos responde a consulta em O(1) — e a ordem das operações resolve o caso [6 6] de graça.

func HasPairSum(values []int, target int) bool {
	seen := make(map[int]bool, len(values))
	for _, value := range values {
		if seen[target-value] {
			return true
		}
		seen[value] = true
	}
	return false
}

Complexidade: O(n) tempo, O(n) espaço. A consulta acontece antes da inserção: quando o loop chega ao primeiro 6 de [6 6] com alvo 12, seen ainda está vazio e a consulta por 12-6=6 falha; o 6 entra no conjunto; no segundo 6, a consulta encontra o primeiro. Dois elementos distintos, mesmo valor — correto. Se você invertesse (inserir antes de consultar), o primeiro 6 encontraria a si mesmo e values=[6], target=12 devolveria true errado.

A armadilha da alternativa: além do loop duplo O(n²), existe uma alternativa genuinamente boa — ordenar e usar two pointers nas pontas, O(n log n) de tempo com O(1) de espaço extra. Ela é o tema da aula 12 (direções opostas), e em array já ordenado é a resposta ideal. Aqui, com array sem ordem, ordenar custa mais que a passada única com map e ainda destrói os índices originais — o que mataria a variação da pergunta que pede as posições do par, não só a existência. Saber as duas e justificar a escolha é exatamente o que o entrevistador quer ouvir.