Mercado Libre - Mutantes DNA

Dados da empresa e da vaga

Empresa: Mercado Libre (Mercado Livre / Mercado Pago)
Sede: Buenos Aires, Argentina (com grandes polos de engenharia em São Paulo, Florianópolis, Cidade do México, Bogotá e Santiago)
Perfil da vaga: Senior Software Engineer (Backend em Go / High-Throughput APIs)
Modelo de trabalho: Híbrido ou remoto
Faixa salarial estimada da vaga:
- Sênior: R$ 20.000 a R$ 32.000/mês (Brasil) / $55.000 a $85.000 USD/ano
- Tech Lead / Staff: R$ 32.000 a R$ 45.000+/mês / $85.000 a $120.000+ USD/ano + Bônus anual agressivo
Stack principal do time: Go, Java, Docker, Kubernetes, Apache Kafka, MySQL, Redis, AWS, Fury (plataforma interna de PaaS do Meli)

Contexto do desafio técnico

O desafio Mutantes (DNA) é o teste técnico take-home mais emblemático aplicado pelo Mercado Livre para contratação de desenvolvedores de backend e sistemas distribuídos.

O enunciado lúdico coloca o candidato a serviço do vilão Magneto, que planeja recrutar mutantes para combater os X-Men. O sistema deve receber sequências de DNA humano e determinar se o indivíduo é mutante ou humano comum.

O teste é dividido em três níveis cumulativos:

Nível 1 (Algoritmo puro): Um algoritmo de varredura bidimensional de alta performance.
Nível 2 (API REST em Go): Um serviço HTTP robusto e idiomático.
Nível 3 (Persistência e Estatísticas): Armazenamento em banco de dados e agregação em tempo real sob alta concorrência.

Especificação dos níveis

Nível 1: O algoritmo de detecção de DNA

Dada uma matriz quadrada de strings $N \times N$ representando uma sequência genética formada apenas pelas bases nitrogenadas A, T, C, G:

dna := []string{
    "ATGCGA",
    "CAGTGC",
    "TTATGT",
    "AGAAGG",
    "CCCCTA",
    "TCACTG",
}

Regra de identificação: Um indivíduo é considerado mutante se forem encontradas mais de uma sequência de quatro letras consecutivas iguais (AAAA, CCCC, TTTT ou GGGG).
As sequências de 4 letras podem estar alinhadas na horizontal, na vertical ou em qualquer uma das duas direções diagonais (diagonal principal e diagonal secundária).
Assinatura da função:
```
func IsMutant(dna []string) bool
```
Requisito crítico de performance: O algoritmo deve implementar early return. No instante em que a segunda sequência de quatro letras for identificada, o processamento deve ser interrompido imediatamente e retornar true, evitando varrer o restante da matriz.

Nível 2: A API REST em Go

Construir um servidor HTTP em Go expondo o endpoint:

Rota: POST /mutant
Cabeçalho: Content-Type: application/json

Corpo da requisição (JSON):

{
  "dna": [
    "ATGCGA",
    "CAGTGC",
    "TTATGT",
    "AGAAGG",
    "CCCCTA",
    "TCACTG"
  ]
}

Respostas HTTP exigidas pelo Mercado Livre:
- HTTP 200 OK: Quando o DNA for identificado como mutante.
- HTTP 403 Forbidden: Quando o DNA for identificado como humano (não mutante).
- HTTP 400 Bad Request: Para entradas inválidas (matriz não quadrada, caracteres diferentes de A, T, C, G ou JSON malformado).

Nível 3: Persistência e endpoint de estatísticas

O serviço deve registrar cada DNA analisado em um banco de dados (como PostgreSQL ou MySQL), garantindo que um mesmo DNA enviado repetidas vezes não seja duplicado na contagem geral (usando um hash criptográfico ou string indexada como chave primária/única).

Disponibilizar o endpoint:

Rota: GET /stats

Resposta HTTP (JSON):

{
  "count_mutant_dna": 40,
  "count_human_dna": 100,
  "ratio": 0.4
}

A taxa (ratio) é calculada dividindo a quantidade de mutantes pelo total de humanos: $$\text{ratio} = \frac{\text{count_mutant_dna}}{\text{count_human_dna}}$$ (Se a contagem de humanos for zero, o sistema deve tratar a divisão por zero sem disparar pânico, retornando zero ou a contagem direta).

Algoritmo otimizado em Go (Nível 1)

package mutant

func IsMutant(dna []string) bool {
	n := len(dna)
	if n < 4 {
		return false
	}

	sequencesFound := 0

	// Varredura por matriz
	for r := 0; r < n; r++ {
		for c := 0; c < n; c++ {
			char := dna[r][c]

			// 1. Horizontal (para a direita)
			if c+3 < n {
				if dna[r][c+1] == char && dna[r][c+2] == char && dna[r][c+3] == char {
					sequencesFound++
					if sequencesFound > 1 {
						return true
					}
				}
			}

			// 2. Vertical (para baixo)
			if r+3 < n {
				if dna[r+1][c] == char && dna[r+2][c] == char && dna[r+3][c] == char {
					sequencesFound++
					if sequencesFound > 1 {
						return true
					}
				}
			}

			// 3. Diagonal Principal (para baixo e direita)
			if r+3 < n && c+3 < n {
				if dna[r+1][c+1] == char && dna[r+2][c+2] == char && dna[r+3][c+3] == char {
					sequencesFound++
					if sequencesFound > 1 {
						return true
					}
				}
			}

			// 4. Diagonal Secundária (para baixo e esquerda)
			if r+3 < n && c-3 >= 0 {
				if dna[r+1][c-1] == char && dna[r+2][c-2] == char && dna[r+3][c-3] == char {
					sequencesFound++
					if sequencesFound > 1 {
						return true
					}
				}
			}
		}
	}

	return false
}

O que os avaliadores do Mercado Livre analisam

Eficiência algorítmica ($O(N^2)$ com corte rápido): Avaliam se o candidato não alocou fatias (slices) temporárias na memória durante a varredura e se aplicou early return imediato.
Cobertura de testes automatizados (> 80%): O Mercado Livre é extremamente rigoroso quanto à esteira de testes. É indispensável incluir:
- Matrizes mínimas ($4 \times 4$).
- Matrizes grandes ($1000 \times 1000$) para testar benchmarks de velocidade.
- Casos com apenas 1 sequência (que deve retornar false).
- Casos de erro: matrizes $N \times M$ não quadradas, caracteres inválidos como X ou Z.
Persistência leve e sem ORMs inflados: O Mercado Livre prefere o uso de bibliotecas de SQL enxutas (database/sql, sqlx ou pgx) em vez de ORMs pesados como GORM para esse tipo de serviço de alta vazão.
Resiliência a concorrência: Como o endpoint /mutant pode receber milhares de requisições por segundo em um cenário de Black Friday do e-commerce, o banco de dados deve usar transações leves ou upserts atômicos (ON CONFLICT DO NOTHING) para não bloquear a leitura de estatísticas.

Neste texto