Algoritmos com Python, do zero ao nível de entrevista

1.1 O que é um algoritmo?

Um algoritmo é uma sequência finita, ordenada e não ambígua de passos que resolve um problema. Uma receita de bolo é um algoritmo; o cálculo de rota do GPS também. A diferença é o rigor: em computação, cada passo precisa ser executável por uma máquina, sem interpretação subjetiva.

Todo algoritmo tem três componentes:

• Entrada — os dados que o problema fornece (uma lista de números, um texto, um mapa).
• Processamento — as transformações aplicadas sobre a entrada.
• Saída — o resultado esperado (um número, verdadeiro/falso, uma lista ordenada).

1.2 Pseudocódigo: pensar antes de codar

Pseudocódigo é a descrição do algoritmo em linguagem quase natural. Exemplo — encontrar o maior número de uma lista:

ALGORITMO maior_numero
ENTRADA: lista de números L (não vazia)
SAÍDA: o maior valor de L

1. maior ← primeiro elemento de L
2. PARA cada elemento x de L, a partir do segundo:
3.     SE x > maior ENTÃO maior ← x
4. RETORNAR maior

Em Python, a tradução é quase direta:

def maior_numero(lista):
    maior = lista[0]
    for x in lista[1:]:
        if x > maior:
            maior = x
    return maior

print(maior_numero([3, 41, 7, 12]))  # 41

1.3 Os três pilares do controle de fluxo

Qualquer algoritmo, por mais complexo que seja, é construído com apenas três estruturas:

1.4 Rastreamento manual (trace)

Antes de rodar código, aprenda a simular na mão. Isso desenvolve o "computador mental" que você usará para depurar. Rastreie este algoritmo com n = 13:

def eh_primo(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:       # só testamos até a raiz quadrada
        if n % i == 0:
            return False
        i += 1
    return True

def acima_da_media(temps):
    media = sum(temps) / len(temps)
    contador = 0
    for t in temps:
        if t > media:
            contador += 1
    return contador
    # versão pythônica: sum(1 for t in temps if t > media)

for n in range(1, 101):
    saida = ""
    if n % 3 == 0: saida += "Fizz"
    if n % 5 == 0: saida += "Buzz"
    print(saida or n)

2.1 Tipos e operações que você precisa saber de cor

# Divisão inteira e módulo — a dupla mais usada em algoritmos
17 // 5   # 3  (quociente)
17 % 5    # 2  (resto)
divmod(17, 5)  # (3, 2)

# Potência e raiz
2 ** 10        # 1024
n ** 0.5       # raiz quadrada (ou math.isqrt(n) para inteiros)

# Troca de variáveis sem temporária
a, b = b, a

# Desempacotamento
primeiro, *meio, ultimo = [1, 2, 3, 4, 5]

2.2 Listas: a estrutura de trabalho

nums = [10, 20, 30, 40, 50]

nums[0]      # 10       — acesso por índice: O(1)
nums[-1]     # 50       — índices negativos contam do fim
nums[1:4]    # [20,30,40] — fatia (slice): [início:fim)
nums[::-1]   # lista invertida
nums.append(60)     # insere no fim: O(1) amortizado
nums.pop()          # remove do fim: O(1)
nums.insert(0, 5)   # insere no início: O(n) — CUIDADO
30 in nums          # busca linear: O(n)
len(nums)           # O(1)

2.3 Compreensões e funções de alta ordem

quadrados = [x*x for x in range(10)]
pares     = [x for x in nums if x % 2 == 0]
matriz    = [[0]*3 for _ in range(3)]   # NUNCA use [[0]*3]*3 (referências!)

# enumerate e zip: índice + valor, e iteração paralela
for i, v in enumerate(nums):
    print(i, v)
for nome, nota in zip(nomes, notas):
    print(nome, nota)

# ordenar com chave
palavras.sort(key=len)
alunos.sort(key=lambda a: (-a["nota"], a["nome"]))  # nota desc, nome asc

2.4 Dicionários e conjuntos: busca O(1)

São implementados como tabelas hash e serão sua arma secreta a partir do Módulo 4.

freq = {}
for ch in "banana":
    freq[ch] = freq.get(ch, 0) + 1   # {'b':1,'a':3,'n':2}

from collections import Counter, defaultdict
Counter("banana")            # mesma coisa, pronta
grafo = defaultdict(list)    # dict que cria listas sob demanda
grafo["A"].append("B")

vistos = set()
vistos.add(10)
10 in vistos                 # O(1) — vs O(n) em lista

2.5 Strings: imutáveis e cheias de métodos

s = "Aprender Algoritmos"
s.lower(), s.upper(), s.strip()
s.split(" ")            # ['Aprender', 'Algoritmos']
"-".join(["a","b","c"]) # 'a-b-c'
s.count("r"), s.find("Alg"), s.replace("A", "@")

# Strings são imutáveis: concatenar em laço é O(n²).
# Certo: acumular em lista e juntar no fim.
partes = []
for w in palavras:
    partes.append(w.upper())
resultado = " ".join(partes)

2.6 Funções, escopo e o módulo padrão do competidor

import math, heapq, bisect, itertools
from collections import deque, Counter, defaultdict
from functools import lru_cache

math.inf        # infinito — ótimo valor inicial para "menor até agora"
math.gcd(12,18) # 6
deque()         # fila O(1) nas duas pontas (Módulo 4)
heapq           # fila de prioridade (Módulo 7)
bisect          # busca binária pronta (Módulo 6)
lru_cache       # memoização automática (Módulo 9)

from collections import Counter

def mais_frequente(frase):
    contagem = Counter(frase.lower().split())
    return contagem.most_common(1)[0][0]

# Solução 1: ordenação — O(n log n)
def anagrama_sort(a, b):
    return sorted(a) == sorted(b)

# Solução 2: contagem — O(n), preferida em entrevista
from collections import Counter
def anagrama_count(a, b):
    return Counter(a) == Counter(b)

3.1 A pergunta central: "e se a entrada crescer?"

Big-O descreve como o tempo (ou memória) cresce em função do tamanho da entrada n, ignorando constantes e termos menores. Não interessa se o algoritmo leva 2n ou 50n passos — ambos são O(n), porque crescem linearmente.

Para sentir a diferença na prática, com n = 1.000.000 (um milhão) e 10⁸ operações por segundo:

3.2 Como calcular na prática

def exemplo(lista):                 # n = len(lista)
    total = 0                       # O(1)
    for x in lista:                 # executa n vezes
        total += x                  #   O(1) por vez  → O(n)
    for i in range(len(lista)):     # n vezes
        for j in range(len(lista)): #   n vezes cada
            print(i, j)             #     → O(n²)
    return total
# Total: O(1) + O(n) + O(n²) = O(n²)  ← domina o maior termo

Regras de bolso:

• Laços consecutivos somam: O(n) + O(n) = O(n).
• Laços aninhados multiplicam: O(n) × O(n) = O(n²).
• Dividir o problema pela metade a cada passo gera O(log n).
• Dividir + processar tudo em cada nível gera O(n log n) — a assinatura do Merge Sort.

3.3 Melhor caso, pior caso e caso médio

Busca linear numa lista de n itens: melhor caso O(1) (item na primeira posição), pior caso O(n) (item no fim ou ausente). Por convenção, Big-O em entrevista refere-se ao pior caso, salvo indicação contrária. Também existe o custo amortizado: list.append ocasionalmente realoca o array inteiro (O(n)), mas na média de muitas operações custa O(1).

3.4 Complexidade de espaço

# O(1) de espaço extra: só variáveis escalares
def soma(lista):
    s = 0
    for x in lista: s += x
    return s

# O(n) de espaço extra: cria estrutura proporcional à entrada
def dobrados(lista):
    return [2*x for x in lista]

3.5 Complexidade das operações nativas do Python

* custo médio/amortizado.

def misterio(n):
    total = 0
    i = 1
    while i < n:
        for j in range(n):
            total += 1
        i *= 2
    return total

# Força bruta: O(n²) tempo, O(1) espaço
def two_sum_bruto(nums, alvo):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == alvo:
                return [i, j]

# Hash map: O(n) tempo, O(n) espaço — a resposta esperada
def two_sum(nums, alvo):
    vistos = {}                     # valor -> índice
    for i, x in enumerate(nums):
        falta = alvo - x
        if falta in vistos:
            return [vistos[falta], i]
        vistos[x] = i

4.1 Pilha (Stack) — LIFO

Último a entrar, primeiro a sair. Em Python, uma lista com append/pop é uma pilha perfeita. Usos: desfazer/refazer, validação de parênteses, avaliação de expressões, DFS, call stack.

def parenteses_validos(s):
    pares = {')': '(', ']': '[', '}': '{'}
    pilha = []
    for ch in s:
        if ch in "([{":
            pilha.append(ch)
        elif ch in pares:
            if not pilha or pilha.pop() != pares[ch]:
                return False
    return not pilha

parenteses_validos("{[()()]}")  # True — O(n) tempo, O(n) espaço

Pilha monotônica (padrão avançado de entrevista)

Mantém a pilha sempre crescente ou decrescente, removendo elementos que quebram a ordem. Resolve em O(n) problemas do tipo "próximo elemento maior", que na força bruta custam O(n²).

def proximo_maior(nums):
    """Para cada posição, o próximo valor à direita que é maior (ou -1)."""
    resp = [-1] * len(nums)
    pilha = []                        # guarda índices, valores decrescentes
    for i, x in enumerate(nums):
        while pilha and nums[pilha[-1]] < x:
            resp[pilha.pop()] = x     # x é o "próximo maior" deles
        pilha.append(i)
    return resp

proximo_maior([2, 1, 5, 3, 6])  # [5, 5, 6, 6, -1]

4.2 Fila (Queue) — FIFO

Primeiro a entrar, primeiro a sair. Usos: BFS, filas de processamento, buffers. Em Python use collections.deque — remover do início de uma list custa O(n).

from collections import deque
fila = deque()
fila.append("A")        # entra no fim      O(1)
fila.append("B")
fila.popleft()          # sai do início     O(1) → "A"

4.3 Lista ligada (Linked List)

Nós encadeados por referências. Python não tem uma nativa, mas ela é presença garantida em entrevistas porque testa manipulação de ponteiros.

class No:
    def __init__(self, valor, prox=None):
        self.valor = valor
        self.prox = prox

def inverter(cabeca):
    """Inverte a lista in-place — clássico absoluto. O(n)/O(1)."""
    anterior = None
    atual = cabeca
    while atual:
        seguinte = atual.prox      # guarda o resto
        atual.prox = anterior      # inverte o ponteiro
        anterior = atual           # avança 'anterior'
        atual = seguinte           # avança 'atual'
    return anterior                # nova cabeça

Técnica dos dois ponteiros: lento e rápido

def tem_ciclo(cabeca):
    """Algoritmo de Floyd (lebre e tartaruga). O(n)/O(1)."""
    lento = rapido = cabeca
    while rapido and rapido.prox:
        lento = lento.prox
        rapido = rapido.prox.prox
        if lento is rapido:
            return True
    return False

def no_do_meio(cabeca):
    lento = rapido = cabeca
    while rapido and rapido.prox:
        lento = lento.prox
        rapido = rapido.prox.prox
    return lento   # quando o rápido chega ao fim, o lento está no meio

4.4 Tabela hash por dentro

O dict aplica uma função de hash à chave para calcular a posição no array interno — por isso a busca é O(1) em média. Colisões (duas chaves na mesma posição) são resolvidas internamente; quando a tabela enche, ela é redimensionada. Consequências práticas:

• Chaves precisam ser imutáveis/"hasheáveis": str, int, tuple sim; list não.
• No pior caso (colisões maliciosas) a busca degrada para O(n) — raro, mas cai em entrevista teórica.

4.5 Guia de decisão rápida

class FilaComPilhas:
    def __init__(self):
        self.entrada = []
        self.saida = []

    def enfileirar(self, x):
        self.entrada.append(x)          # O(1)

    def desenfileirar(self):
        if not self.saida:              # transfere só quando esvazia
            while self.entrada:
                self.saida.append(self.entrada.pop())
        return self.saida.pop()         # O(1) amortizado

def navegar(acoes):
    pilha = []
    for a in acoes:
        if a == "back":
            if len(pilha) > 1:
                pilha.pop()
        else:
            pilha.append(a)
    return pilha[-1] if pilha else None
# ["google.com","wiki.org","back","python.org"] → "python.org"

5.1 Anatomia de uma função recursiva

Toda recursão correta tem dois componentes obrigatórios:

1. Caso base — a condição de parada, resolvida sem recursão.
2. Passo recursivo — a chamada sobre um problema estritamente menor.

def fatorial(n):
    if n <= 1:                 # caso base
        return 1
    return n * fatorial(n-1)   # passo: reduz n em 1

def soma_digitos(n):
    if n < 10:
        return n
    return n % 10 + soma_digitos(n // 10)

Mentalize a pilha de chamadas: fatorial(4) empilha 4→3→2→1 e então desempilha multiplicando. Profundidade da pilha = uso de memória O(n). Python limita a recursão (~1000 níveis por padrão); para entradas grandes, converta para iteração ou aumente com sys.setrecursionlimit.

5.2 O salto de fé (leap of faith)

O segredo para projetar recursão: assuma que a chamada menor já funciona e pergunte apenas "como combino esse resultado para resolver o problema atual?". Não tente simular todos os níveis de cabeça.

def inverter_string(s):
    if len(s) <= 1:
        return s
    # fé: inverter_string(s[1:]) devolve o resto invertido
    return inverter_string(s[1:]) + s[0]

5.3 Recursões múltiplas e a explosão exponencial

def fib(n):                      # duas chamadas por nível
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)   # O(2^n) — fib(40) já trava

A árvore de chamadas recalcula os mesmos subproblemas milhares de vezes. Guardar resultados (memoização) derruba para O(n) — esse é o gancho para o Módulo 9.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_rapido(n):
    if n < 2: return n
    return fib_rapido(n-1) + fib_rapido(n-2)   # O(n)

5.4 Divisão e conquista

Padrão: dividir a entrada em partes, conquistar cada parte recursivamente, combinar os resultados. É a base do Merge Sort, Quick Sort e da busca binária. Exemplo — potência rápida:

def potencia(base, exp):
    """base^exp em O(log exp) em vez de O(exp)."""
    if exp == 0:
        return 1
    metade = potencia(base, exp // 2)
    if exp % 2 == 0:
        return metade * metade
    return metade * metade * base

potencia(2, 100)  # 40 chamadas em vez de 100

def eh_palindromo(s):
    if len(s) <= 1:
        return True
    return s[0] == s[-1] and eh_palindromo(s[1:-1])

def hanoi(n, origem, destino, auxiliar):
    if n == 1:
        print(f"disco 1: {origem} → {destino}")
        return
    hanoi(n-1, origem, auxiliar, destino)
    print(f"disco {n}: {origem} → {destino}")
    hanoi(n-1, auxiliar, destino, origem)

hanoi(3, "A", "C", "B")

6.1 Busca binária: O(log n) que decide vagas

Pré-requisito: a coleção deve estar ordenada. A cada passo, descartamos metade do espaço de busca.

def busca_binaria(lista, alvo):
    esq, dir = 0, len(lista) - 1
    while esq <= dir:
        meio = (esq + dir) // 2
        if lista[meio] == alvo:
            return meio
        if lista[meio] < alvo:
            esq = meio + 1
        else:
            dir = meio - 1
    return -1                      # não encontrado

Variações essenciais: limites e "busca na resposta"

import bisect
nums = [1, 3, 3, 3, 7, 9]
bisect.bisect_left(nums, 3)   # 1 — primeira posição do 3
bisect.bisect_right(nums, 3)  # 4 — posição após o último 3
# ocorrências de 3 = right - left = 3

Busca binária na resposta: quando a pergunta é "qual o menor X que satisfaz a condição?" e a condição é monotônica, procure X por busca binária mesmo sem lista nenhuma. Exemplo real (Koko comendo bananas / capacidade de navio):

def capacidade_minima(pesos, dias):
    """Menor capacidade diária para despachar todos os pesos em 'dias'."""
    def cabe(cap):
        d, atual = 1, 0
        for p in pesos:
            if atual + p > cap:
                d += 1
                atual = 0
            atual += p
        return d <= dias

    esq, dir = max(pesos), sum(pesos)
    while esq < dir:
        meio = (esq + dir) // 2
        if cabe(meio):
            dir = meio          # serve → tenta menor
        else:
            esq = meio + 1      # não serve → precisa de mais
    return esq                  # O(n log(soma))

6.2 Ordenações quadráticas: simples e didáticas

def bubble_sort(a):                  # O(n²) — compara vizinhos
    n = len(a)
    for i in range(n):
        trocou = False
        for j in range(n - 1 - i):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
                trocou = True
        if not trocou:               # já ordenado: melhor caso O(n)
            break

def insertion_sort(a):               # O(n²), mas O(n) se quase ordenado
    for i in range(1, len(a)):
        chave = a[i]
        j = i - 1
        while j >= 0 and a[j] > chave:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = chave

6.3 Merge Sort — O(n log n) garantido e estável

def merge_sort(a):
    if len(a) <= 1:
        return a
    meio = len(a) // 2
    esq = merge_sort(a[:meio])
    dir = merge_sort(a[meio:])
    return intercalar(esq, dir)

def intercalar(esq, dir):
    res, i, j = [], 0, 0
    while i < len(esq) and j < len(dir):
        if esq[i] <= dir[j]:         # <= preserva estabilidade
            res.append(esq[i]); i += 1
        else:
            res.append(dir[j]); j += 1
    res.extend(esq[i:]); res.extend(dir[j:])
    return res

Estável = itens iguais mantêm a ordem original (crucial para ordenar por múltiplos critérios em cadeia). Custo de espaço: O(n).

6.4 Quick Sort — O(n log n) médio, in-place

import random

def quick_sort(a, esq=0, dir=None):
    if dir is None:
        dir = len(a) - 1
    if esq >= dir:
        return
    p = particionar(a, esq, dir)
    quick_sort(a, esq, p - 1)
    quick_sort(a, p + 1, dir)

def particionar(a, esq, dir):
    r = random.randint(esq, dir)       # pivô aleatório evita o pior caso
    a[r], a[dir] = a[dir], a[r]
    pivo, i = a[dir], esq
    for j in range(esq, dir):
        if a[j] < pivo:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[dir] = a[dir], a[i]
    return i

Pior caso O(n²) acontece com pivôs sempre ruins (lista já ordenada + pivô fixo); pivô aleatório torna isso improvável. Derivado importante: Quickselect encontra o k-ésimo menor em O(n) médio, seguindo só um lado da partição.

6.5 Ordenações lineares e o Timsort do Python

Counting Sort ordena inteiros num intervalo pequeno k em O(n + k), contando ocorrências — fura o limite teórico O(n log n) porque não compara elementos. O sorted() do Python usa Timsort (híbrido de merge + insertion), estável, O(n log n) no pior caso e O(n) para dados quase ordenados. Em produção, use sempre o nativo; implemente na mão apenas para aprender e para entrevistas.

def busca_rotacionada(nums, alvo):
    esq, dir = 0, len(nums) - 1
    while esq <= dir:
        meio = (esq + dir) // 2
        if nums[meio] == alvo:
            return meio
        if nums[esq] <= nums[meio]:          # metade esquerda ordenada
            if nums[esq] <= alvo < nums[meio]:
                dir = meio - 1
            else:
                esq = meio + 1
        else:                                 # metade direita ordenada
            if nums[meio] < alvo <= nums[dir]:
                esq = meio + 1
            else:
                dir = meio - 1
    return -1

def conta_inversoes(a):
    def ms(a):
        if len(a) <= 1:
            return a, 0
        m = len(a)//2
        esq, ce = ms(a[:m])
        dir, cd = ms(a[m:])
        res, i, j, cruz = [], 0, 0, 0
        while i < len(esq) and j < len(dir):
            if esq[i] <= dir[j]:
                res.append(esq[i]); i += 1
            else:
                res.append(dir[j]); j += 1
                cruz += len(esq) - i   # todos à frente em 'esq' invertem com dir[j]
        res += esq[i:] + dir[j:]
        return res, ce + cd + cruz
    return ms(a)[1]

7.1 Vocabulário de árvores

Raiz (topo), filhos, folhas (sem filhos), altura (maior caminho raiz→folha), árvore binária (até 2 filhos). Uma árvore binária balanceada com n nós tem altura O(log n) — daí vem toda a eficiência.

class No:
    def __init__(self, valor):
        self.valor = valor
        self.esq = None
        self.dir = None

7.2 Os quatro percursos

def em_ordem(no):        # esq → raiz → dir  (em BST: sai ordenado!)
    if no:
        em_ordem(no.esq)
        print(no.valor)
        em_ordem(no.dir)

def pre_ordem(no):       # raiz → esq → dir  (copiar/serializar árvore)
    if no:
        print(no.valor)
        pre_ordem(no.esq)
        pre_ordem(no.dir)

def pos_ordem(no):       # esq → dir → raiz  (deletar/calcular de baixo p/ cima)
    if no:
        pos_ordem(no.esq)
        pos_ordem(no.dir)
        print(no.valor)

from collections import deque
def por_nivel(raiz):     # BFS — nível a nível
    if not raiz: return
    fila = deque([raiz])
    while fila:
        for _ in range(len(fila)):   # processa um nível por vez
            no = fila.popleft()
            print(no.valor, end=" ")
            if no.esq: fila.append(no.esq)
            if no.dir: fila.append(no.dir)
        print()

7.3 Árvore binária de busca (BST)

Invariante: tudo à esquerda < nó < tudo à direita. Busca, inserção e remoção em O(altura) — O(log n) se balanceada, O(n) se degenerada em "lista".

def inserir(no, valor):
    if no is None:
        return No(valor)
    if valor < no.valor:
        no.esq = inserir(no.esq, valor)
    else:
        no.dir = inserir(no.dir, valor)
    return no

def buscar(no, valor):
    if no is None or no.valor == valor:
        return no
    if valor < no.valor:
        return buscar(no.esq, valor)
    return buscar(no.dir, valor)

def validar_bst(no, minimo=float("-inf"), maximo=float("inf")):
    """Pegadinha de entrevista: comparar só com o pai NÃO basta."""
    if no is None:
        return True
    if not (minimo < no.valor < maximo):
        return False
    return (validar_bst(no.esq, minimo, no.valor) and
            validar_bst(no.dir, no.valor, maximo))

Para garantir altura O(log n) existem as árvores auto-balanceadas (AVL, Rubro-Negra). Em entrevista basta saber que existem, por que existem e que bancos de dados usam a prima delas, a B-Tree, em índices.

7.4 Problemas canônicos de árvore

def altura(no):
    if no is None:
        return 0
    return 1 + max(altura(no.esq), altura(no.dir))

def lca(raiz, p, q):
    """Menor ancestral comum em BST — O(altura)."""
    while raiz:
        if p.valor < raiz.valor and q.valor < raiz.valor:
            raiz = raiz.esq
        elif p.valor > raiz.valor and q.valor > raiz.valor:
            raiz = raiz.dir
        else:
            return raiz     # caminhos divergem aqui

def diametro(raiz):
    """Maior caminho entre dois nós quaisquer."""
    melhor = 0
    def prof(no):
        nonlocal melhor
        if not no: return 0
        e, d = prof(no.esq), prof(no.dir)
        melhor = max(melhor, e + d)     # caminho que passa por 'no'
        return 1 + max(e, d)
    prof(raiz)
    return melhor

7.5 Heap: a fila de prioridade

Um min-heap é uma árvore binária completa (guardada num array) em que cada pai ≤ filhos. O menor elemento fica sempre na raiz: ler O(1), inserir/remover O(log n), construir de uma lista O(n).

import heapq
h = [7, 2, 9, 4]
heapq.heapify(h)          # O(n)
heapq.heappush(h, 1)      # O(log n)
heapq.heappop(h)          # 1 — sempre o menor
h[0]                      # espiar o mínimo sem remover

# Max-heap em Python: negue os valores
heapq.heappush(mx, -valor);  maior = -heapq.heappop(mx)

# Padrão "top-k": k maiores de n itens em O(n log k)
heapq.nlargest(3, nums)
heapq.nsmallest(3, tarefas, key=lambda t: t["prazo"])

Padrão avançado: mediana em streaming com dois heaps

class MedianaStream:
    """Mantém a mediana de um fluxo: inserção O(log n), consulta O(1)."""
    def __init__(self):
        self.baixos = []   # max-heap (negados): metade menor
        self.altos  = []   # min-heap: metade maior

    def adicionar(self, x):
        heapq.heappush(self.baixos, -x)
        heapq.heappush(self.altos, -heapq.heappop(self.baixos))
        if len(self.altos) > len(self.baixos):
            heapq.heappush(self.baixos, -heapq.heappop(self.altos))

    def mediana(self):
        if len(self.baixos) > len(self.altos):
            return -self.baixos[0]
        return (-self.baixos[0] + self.altos[0]) / 2

def simetrica(raiz):
    def espelho(a, b):
        if a is None and b is None: return True
        if a is None or b is None:  return False
        return (a.valor == b.valor and
                espelho(a.esq, b.dir) and
                espelho(a.dir, b.esq))
    return espelho(raiz, raiz)

import heapq
def merge_k(listas):
    """O(N log k), N = total de itens."""
    h = [(lst[0], i, 0) for i, lst in enumerate(listas) if lst]
    heapq.heapify(h)
    saida = []
    while h:
        val, i, j = heapq.heappop(h)
        saida.append(val)
        if j + 1 < len(listas[i]):
            heapq.heappush(h, (listas[i][j+1], i, j+1))
    return saida

8.1 Representação

Um grafo é um conjunto de vértices ligados por arestas (direcionadas ou não, com peso ou não). Na prática, use lista de adjacência: espaço O(V+E) e iteração eficiente pelos vizinhos.

from collections import defaultdict

grafo = defaultdict(list)
arestas = [("A","B"), ("A","C"), ("B","D"), ("C","D"), ("D","E")]
for u, v in arestas:
    grafo[u].append(v)
    grafo[v].append(u)      # remova esta linha para grafo direcionado

Matriz de adjacência (V×V) só compensa em grafos densos ou quando você precisa testar "existe aresta u→v?" em O(1).

8.2 BFS — busca em largura

Explora em "ondas" a partir da origem usando uma fila. Propriedade de ouro: em grafos sem peso, o BFS encontra o caminho mais curto (em número de arestas).

from collections import deque

def bfs_distancias(grafo, origem):
    """Distância mínima da origem a todos os vértices. O(V+E)."""
    dist = {origem: 0}
    fila = deque([origem])
    while fila:
        u = fila.popleft()
        for v in grafo[u]:
            if v not in dist:            # marcar AO ENFILEIRAR evita duplicatas
                dist[v] = dist[u] + 1
                fila.append(v)
    return dist

Para reconstruir o caminho, guarde pai[v] = u ao visitar e retroceda do destino até a origem.

8.3 DFS — busca em profundidade

Vai fundo antes de voltar, via recursão ou pilha explícita. Usos: componentes conexos, detecção de ciclo, ordenação topológica, backtracking.

def dfs(grafo, u, visitados=None):
    if visitados is None:
        visitados = set()
    visitados.add(u)
    for v in grafo[u]:
        if v not in visitados:
            dfs(grafo, v, visitados)
    return visitados

def conta_componentes(grafo, vertices):
    visitados, comp = set(), 0
    for v in vertices:
        if v not in visitados:
            dfs(grafo, v, visitados)
            comp += 1
    return comp

O padrão "ilhas" em matriz (grade como grafo implícito)

def num_ilhas(grade):
    """Cada célula é um vértice; vizinhos ortogonais são arestas."""
    if not grade: return 0
    L, C = len(grade), len(grade[0])
    def afundar(i, j):
        if 0 <= i < L and 0 <= j < C and grade[i][j] == "1":
            grade[i][j] = "0"                  # marca como visitada
            for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):
                afundar(i+di, j+dj)
    ilhas = 0
    for i in range(L):
        for j in range(C):
            if grade[i][j] == "1":
                afundar(i, j)
                ilhas += 1
    return ilhas          # O(L·C)

8.4 Dijkstra — caminho mínimo com pesos

Com arestas de peso não negativo, o BFS não basta. Dijkstra usa um min-heap para sempre expandir o vértice mais próximo já conhecido — guloso e correto.

import heapq

def dijkstra(grafo, origem):
    """grafo[u] = [(vizinho, peso), ...]. O((V+E) log V)."""
    dist = {origem: 0}
    heap = [(0, origem)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float("inf")):
            continue                      # entrada obsoleta ("lazy deletion")
        for v, peso in grafo[u]:
            nd = d + peso
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

8.5 Ordenação topológica — o algoritmo dos sistemas de build

Em um grafo direcionado acíclico (DAG) de dependências ("A antes de B"), produz uma ordem válida de execução. É o coração de npm install, Makefiles, pipelines de dados e planejamento de matérias.

from collections import deque, defaultdict

def ordem_topologica(n, pre_reqs):
    """Algoritmo de Kahn. pre_reqs: lista de (antes, depois). O(V+E)."""
    grafo = defaultdict(list)
    grau = [0] * n
    for a, b in pre_reqs:
        grafo[a].append(b)
        grau[b] += 1
    fila = deque(v for v in range(n) if grau[v] == 0)
    ordem = []
    while fila:
        u = fila.popleft()
        ordem.append(u)
        for v in grafo[u]:
            grau[v] -= 1
            if grau[v] == 0:
                fila.append(v)
    return ordem if len(ordem) == n else None   # None → há ciclo!

8.6 Union-Find (Disjoint Set Union)

Responde "u e v estão no mesmo grupo?" e une grupos em tempo quase O(1) amortizado. Essencial para conectividade dinâmica, detecção de ciclo em grafo não-direcionado e o algoritmo de Kruskal (árvore geradora mínima).

class UnionFind:
    def __init__(self, n):
        self.pai = list(range(n))
        self.rank = [0] * n

    def find(self, x):                       # compressão de caminho
        while self.pai[x] != x:
            self.pai[x] = self.pai[self.pai[x]]
            x = self.pai[x]
        return x

    def union(self, a, b):                   # união por rank
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                     # já conectados (ciclo!)
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.pai[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

8.7 Qual algoritmo de grafo usar?

from collections import deque
def escada(inicio, fim, dicionario):
    dic = set(dicionario)
    if fim not in dic: return 0
    fila = deque([(inicio, 1)])
    while fila:
        w, passos = fila.popleft()
        if w == fim:
            return passos
        for i in range(len(w)):
            for c in "abcdefghijklmnopqrstuvwxyz":
                nova = w[:i] + c + w[i+1:]
                if nova in dic:
                    dic.remove(nova)         # visitada
                    fila.append((nova, passos + 1))
    return 0

9.1 Quando um problema é de DP?

Dois sinais precisam coexistir:

• Subproblemas sobrepostos — a recursão ingênua recalcula os mesmos estados várias vezes (como fib).
• Subestrutura ótima — a solução ótima do todo é composta por soluções ótimas das partes.

Frases-gatilho no enunciado: "número de maneiras de…", "custo mínimo / lucro máximo…", "maior subsequência…", "é possível atingir…".

9.2 O método em 5 passos (framework de entrevista)

1. Defina o estado: o que dp[i] significa em português. Este é o passo mais importante.
2. Escreva a transição: como dp[i] deriva de estados menores.
3. Casos base.
4. Ordem de cálculo (ou memoização automática).
5. Resposta final: qual célula (ou combinação) responde o problema.

9.3 Top-down vs bottom-up

# Problema: subir escada de n degraus, 1 ou 2 por vez. Quantas formas?

# TOP-DOWN (memoização): recursão natural + cache
from functools import lru_cache
@lru_cache(maxsize=None)
def escada_td(n):
    if n <= 2: return n
    return escada_td(n-1) + escada_td(n-2)

# BOTTOM-UP (tabulação): preenche a tabela em ordem
def escada_bu(n):
    if n <= 2: return n
    a, b = 1, 2                     # dp[1], dp[2]
    for _ in range(3, n + 1):
        a, b = b, a + b             # espaço otimizado: O(1)
    return b

Ambos custam O(n). Memoização é mais fácil de derivar; tabulação evita limite de recursão e permite otimizar espaço. Em entrevista, comece top-down e ofereça a conversão.

9.4 Clássicos 1D

def roubo_de_casas(valores):
    """House Robber: não pode roubar casas adjacentes.
    dp[i] = máximo até a casa i."""
    com, sem = 0, 0            # com/sem roubar a casa atual
    for v in valores:
        com, sem = sem + v, max(sem, com)
    return max(com, sem)

def troco_minimo(moedas, alvo):
    """Coin Change: menor nº de moedas para formar 'alvo'.
    dp[x] = mínimo de moedas para o valor x."""
    INF = float("inf")
    dp = [0] + [INF] * alvo
    for x in range(1, alvo + 1):
        for m in moedas:
            if m <= x and dp[x - m] + 1 < dp[x]:
                dp[x] = dp[x - m] + 1
    return dp[alvo] if dp[alvo] != INF else -1   # O(alvo · moedas)

def max_subarray(nums):
    """Kadane: maior soma de subarray contíguo. O(n)/O(1)."""
    melhor = atual = nums[0]
    for x in nums[1:]:
        atual = max(x, atual + x)   # estende ou recomeça
        melhor = max(melhor, atual)
    return melhor

9.5 Clássicos 2D

Maior subsequência comum (LCS) — base do git diff

def lcs(a, b):
    """dp[i][j] = LCS entre a[:i] e b[:j]. O(n·m)."""
    n, m = len(a), len(b)
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[n][m]

Distância de edição (Levenshtein) — corretores e busca fuzzy

def edit_distance(a, b):
    """Mínimo de inserções/remoções/substituições para a → b."""
    n, m = len(a), len(b)
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n+1): dp[i][0] = i
    for j in range(m+1): dp[0][j] = j
    for i in range(1, n+1):
        for j in range(1, m+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j],     # remover
                                   dp[i][j-1],     # inserir
                                   dp[i-1][j-1])   # substituir
    return dp[n][m]

Mochila 0/1 (Knapsack) — a mãe dos problemas de otimização

def mochila(pesos, valores, capacidade):
    """dp[c] = melhor valor com capacidade c. O(n·C) tempo, O(C) espaço."""
    dp = [0] * (capacidade + 1)
    for p, v in zip(pesos, valores):
        for c in range(capacidade, p - 1, -1):   # DECRESCENTE: cada item 1x
            dp[c] = max(dp[c], dp[c - p] + v)
    return dp[capacidade]

Maior subsequência crescente (LIS) em O(n log n)

import bisect
def lis(nums):
    """'caudas[k]' = menor final possível de uma subsequência de tamanho k+1."""
    caudas = []
    for x in nums:
        i = bisect.bisect_left(caudas, x)
        if i == len(caudas):
            caudas.append(x)
        else:
            caudas[i] = x
    return len(caudas)

def caminhos(m, n):
    dp = [[1]*n for _ in range(m)]        # bordas têm 1 caminho
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[-1][-1]                     # O(m·n)

def word_break(s, dicionario):
    dic = set(dicionario)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True                          # prefixo vazio ok
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in dic:
                dp[i] = True
                break
    return dp[n]                          # O(n²) com fatias O(n) → O(n³) pior caso

10.1 Estratégia gulosa (greedy)

A cada passo, tome a melhor decisão local e nunca volte atrás. Só funciona quando o problema tem a propriedade da escolha gulosa — e provar isso (ou ao menos argumentar) faz parte da resposta.

def max_atividades(intervalos):
    """Seleção de atividades: máximo de intervalos sem sobreposição.
    Guloso correto: ordenar por TÉRMINO. O(n log n)."""
    intervalos.sort(key=lambda iv: iv[1])
    fim, escolhidas = float("-inf"), 0
    for inicio, termino in intervalos:
        if inicio >= fim:
            escolhidas += 1
            fim = termino
    return escolhidas

def salto_minimo(nums):
    """Jump Game II: mínimo de saltos até o fim. Guloso por 'alcance'. O(n)."""
    saltos = fim_atual = alcance = 0
    for i in range(len(nums) - 1):
        alcance = max(alcance, i + nums[i])
        if i == fim_atual:          # esgotou a "onda" atual
            saltos += 1
            fim_atual = alcance
    return saltos

Gulosos famosos que funcionam: Dijkstra, Kruskal/Prim (MST), codificação de Huffman (compressão), escalonamento por término.

10.2 Backtracking: busca com arrependimento

Constrói a solução incrementalmente; ao detectar que o caminho não leva a nada, desfaz ("backtrack") e tenta outra opção. Estrutura universal:

def backtrack(estado, opcoes):
    if solucao_completa(estado):
        registrar(estado)
        return
    for opcao in opcoes_validas(estado):
        aplicar(estado, opcao)        # escolhe
        backtrack(estado, opcoes)     # explora
        desfazer(estado, opcao)       # desfaz — o coração do padrão

Permutações e subconjuntos

def permutacoes(nums):
    res, atual = [], []
    usados = [False] * len(nums)
    def bt():
        if len(atual) == len(nums):
            res.append(atual[:])          # cópia!
            return
        for i, x in enumerate(nums):
            if usados[i]: continue
            usados[i] = True; atual.append(x)
            bt()
            atual.pop(); usados[i] = False
    bt()
    return res                            # O(n · n!)

def subconjuntos(nums):
    res, atual = [], []
    def bt(inicio):
        res.append(atual[:])
        for i in range(inicio, len(nums)):
            atual.append(nums[i])
            bt(i + 1)
            atual.pop()
    bt(0)
    return res                            # O(n · 2^n)

N-Rainhas: o exemplo canônico de poda

def n_rainhas(n):
    solucoes = []
    colunas, diag1, diag2 = set(), set(), set()
    posicao = []
    def bt(linha):
        if linha == n:
            solucoes.append(posicao[:])
            return
        for col in range(n):
            if col in colunas or (linha-col) in diag1 or (linha+col) in diag2:
                continue                   # PODA: célula atacada
            colunas.add(col); diag1.add(linha-col); diag2.add(linha+col)
            posicao.append(col)
            bt(linha + 1)
            posicao.pop()
            colunas.discard(col); diag1.discard(linha-col); diag2.discard(linha+col)
    bt(0)
    return solucoes

A poda com três conjuntos torna cada verificação O(1). Sem poda, o espaço de busca é nⁿ; com ela, o algoritmo resolve n=12 em milissegundos.

10.3 Como escolher a estratégia

def combination_sum(cands, alvo):
    res, atual = [], []
    def bt(inicio, resto):
        if resto == 0:
            res.append(atual[:]); return
        for i in range(inicio, len(cands)):
            if cands[i] > resto:           # poda (com cands ordenado)
                continue
            atual.append(cands[i])
            bt(i, resto - cands[i])        # 'i' (não i+1): pode repetir
            atual.pop()
    cands.sort()
    bt(0, alvo)
    return res

import heapq
def salas(reunioes):
    reunioes.sort()                        # por início
    heap = []                              # términos das salas em uso
    for inicio, fim in reunioes:
        if heap and heap[0] <= inicio:     # sala mais cedo já liberou
            heapq.heappop(heap)
        heapq.heappush(heap, fim)
    return len(heap)                       # O(n log n)

11.1 Trie (árvore de prefixos)

Cada nó representa um caractere; caminhos da raiz formam prefixos. Busca e inserção em O(L) (L = tamanho da palavra), independente de quantas palavras existam. É a base de autocomplete, corretores e roteamento de IP.

class Trie:
    def __init__(self):
        self.raiz = {}

    def inserir(self, palavra):
        no = self.raiz
        for ch in palavra:
            no = no.setdefault(ch, {})
        no["$"] = True                     # marca fim de palavra

    def buscar(self, palavra):
        no = self._desce(palavra)
        return no is not None and "$" in no

    def tem_prefixo(self, prefixo):
        return self._desce(prefixo) is not None

    def _desce(self, s):
        no = self.raiz
        for ch in s:
            if ch not in no:
                return None
            no = no[ch]
        return no

11.2 Segment Tree: consultas de intervalo em O(log n)

Problema: dado um array mutável, responder milhões de consultas "soma (ou mínimo/máximo) do intervalo [l, r]" com atualizações intercaladas. Prefix sums resolvem consulta em O(1) mas atualização em O(n); a segment tree equilibra: ambas em O(log n).

class SegmentTree:
    """Soma de intervalos com atualização pontual."""
    def __init__(self, dados):
        self.n = len(dados)
        self.arv = [0] * (2 * self.n)
        for i, v in enumerate(dados):            # folhas em [n, 2n)
            self.arv[self.n + i] = v
        for i in range(self.n - 1, 0, -1):       # internos de baixo p/ cima
            self.arv[i] = self.arv[2*i] + self.arv[2*i + 1]

    def atualizar(self, i, valor):               # O(log n)
        i += self.n
        self.arv[i] = valor
        while i > 1:
            i //= 2
            self.arv[i] = self.arv[2*i] + self.arv[2*i + 1]

    def consulta(self, l, r):                    # soma de [l, r) — O(log n)
        s = 0
        l += self.n; r += self.n
        while l < r:
            if l % 2: s += self.arv[l]; l += 1
            if r % 2: r -= 1; s += self.arv[r]
            l //= 2; r //= 2
        return s

Prima mais simples: Fenwick Tree (BIT) — mesmo par de custos para somas de prefixo, com um terço do código. Extensão avançada: lazy propagation para atualizações em intervalo inteiro.

11.3 Janela deslizante (sliding window)

Para subarrays/substrings contíguos: mantenha dois ponteiros e um estado incremental, expandindo a direita e contraindo a esquerda. Converte O(n²) em O(n).

def maior_substring_sem_repetir(s):
    """Clássico absoluto de entrevista. O(n)."""
    ultimo = {}                    # char -> última posição
    inicio = melhor = 0
    for i, ch in enumerate(s):
        if ch in ultimo and ultimo[ch] >= inicio:
            inicio = ultimo[ch] + 1        # contrai além da repetição
        ultimo[ch] = i
        melhor = max(melhor, i - inicio + 1)
    return melhor

def menor_subarray_soma(nums, alvo):
    """Menor comprimento com soma >= alvo (positivos). O(n)."""
    soma = esq = 0
    melhor = float("inf")
    for dir, x in enumerate(nums):
        soma += x
        while soma >= alvo:
            melhor = min(melhor, dir - esq + 1)
            soma -= nums[esq]
            esq += 1
    return 0 if melhor == float("inf") else melhor

11.4 Dois ponteiros em arrays ordenados

def two_sum_ordenado(nums, alvo):
    """Em lista ORDENADA: O(n) tempo, O(1) espaço."""
    e, d = 0, len(nums) - 1
    while e < d:
        s = nums[e] + nums[d]
        if s == alvo: return [e, d]
        if s < alvo:  e += 1
        else:         d -= 1

def area_maxima(alturas):
    """Container With Most Water. O(n)."""
    e, d, melhor = 0, len(alturas) - 1, 0
    while e < d:
        melhor = max(melhor, (d - e) * min(alturas[e], alturas[d]))
        if alturas[e] < alturas[d]: e += 1   # mova o lado menor
        else:                        d -= 1
    return melhor

11.5 Busca em strings: KMP e Rabin-Karp

Encontrar um padrão P (tamanho m) num texto T (tamanho n) ingênuo custa O(n·m). KMP pré-computa, para cada posição do padrão, o maior prefixo que também é sufixo (tabela de falhas) e nunca retrocede no texto: O(n + m) garantido.

def kmp(texto, padrao):
    if not padrao: return 0
    # tabela de falhas
    f = [0] * len(padrao)
    k = 0
    for i in range(1, len(padrao)):
        while k and padrao[i] != padrao[k]:
            k = f[k-1]
        if padrao[i] == padrao[k]:
            k += 1
        f[i] = k
    # varredura
    k = 0
    for i, ch in enumerate(texto):
        while k and ch != padrao[k]:
            k = f[k-1]
        if ch == padrao[k]:
            k += 1
        if k == len(padrao):
            return i - k + 1          # primeira ocorrência
    return -1

Rabin-Karp compara hashes rolantes das janelas: O(n+m) em média, ideal para buscar vários padrões ao mesmo tempo (detecção de plágio, antivírus).

11.6 Manipulação de bits

x & 1              # é ímpar?
x >> 1             # divide por 2
x & (x - 1)        # remove o bit 1 mais baixo
x & (x - 1) == 0   # é potência de 2? (x > 0)
x ^ y              # XOR: soma sem carry; a ^ a == 0

def numero_solitario(nums):
    """Todos aparecem 2x, exceto um. O(n)/O(1) — resposta 'uau'."""
    r = 0
    for x in nums:
        r ^= x                 # os pares se cancelam
    return r

def conta_bits(x):             # popcount manual (ou bin(x).count("1"))
    c = 0
    while x:
        x &= x - 1
        c += 1
    return c

# Iterar todos os subconjuntos com máscara de bits — DP bitmask
for mascara in range(1 << n):
    itens = [i for i in range(n) if mascara & (1 << i)]

Bitmask DP resolve problemas como o Caixeiro Viajante em O(2ⁿ·n²) — exponencial, porém viável para n ≤ 20 e muito melhor que O(n!).

11.7 Amostragem e aleatoriedade

import random

def fisher_yates(a):
    """Embaralhamento uniforme e imparcial. O(n)."""
    for i in range(len(a) - 1, 0, -1):
        j = random.randint(0, i)
        a[i], a[j] = a[j], a[i]

def reservoir(iteravel, k):
    """Amostra k itens de um stream de tamanho desconhecido."""
    res = []
    for i, x in enumerate(iteravel):
        if i < k:
            res.append(x)
        else:
            j = random.randint(0, i)
            if j < k:
                res[j] = x
    return res

Complete o repertório expert sabendo o que resolve o quê: Bloom filter (pertencimento probabilístico com pouquíssima memória — caches e bancos), consistent hashing (distribuir chaves entre servidores), skip lists (alternativa probabilística a árvores balanceadas — usada no Redis).

from collections import Counter
def anagramas_no_texto(s, p):
    if len(p) > len(s): return []
    alvo, janela = Counter(p), Counter(s[:len(p)])
    res = [0] if janela == alvo else []
    for i in range(len(p), len(s)):
        janela[s[i]] += 1
        janela[s[i - len(p)]] -= 1
        if janela[s[i - len(p)]] == 0:
            del janela[s[i - len(p)]]
        if janela == alvo:
            res.append(i - len(p) + 1)
    return res      # janela fixa: O(n)

12.1 Prefix sum: o padrão 14 em 10 linhas

def subarrays_com_soma_k(nums, k):
    """Quantos subarrays contíguos somam k (com negativos!). O(n)."""
    from collections import defaultdict
    freq = defaultdict(int)
    freq[0] = 1
    soma = total = 0
    for x in nums:
        soma += x
        total += freq[soma - k]   # prefixos anteriores que fecham soma k
        freq[soma] += 1
    return total

12.2 O protocolo da entrevista (roteiro de 45 minutos)

1. Clarifique (3–5 min): tamanho da entrada? valores negativos? empates? entrada pode ser vazia? Repita o problema com suas palavras.
2. Exemplos e casos de borda: crie você mesmo 2–3 exemplos, incluindo um degenerado.
3. Solução ingênua em voz alta + Big-O dela. Nunca pule esta etapa: mostra estrutura de raciocínio e serve de rede de segurança.
4. Otimize: identifique o gargalo, escolha o padrão da tabela acima e negocie a abordagem com o entrevistador antes de codar.
5. Implemente narrando: nomes claros, funções pequenas. Silêncio prolongado é o maior erro comportamental.
6. Teste na mão: rode seu exemplo linha a linha, depois os casos de borda. Encontrar o próprio bug vale pontos.
7. Feche: declare tempo e espaço finais e mencione melhorias possíveis.

12.3 Erros que mais reprovam (checklist negativo)

• Começar a codar sem clarificar o problema.
• Ignorar entrada vazia, um único elemento, duplicatas e valores negativos.
• Não saber o Big-O da própria solução ("acho que é rápido…").
• Usar lista.insert(0, x) ou x in lista dentro de laço sem perceber o custo O(n).
• Travar em silêncio em vez de verbalizar hipóteses e pedir uma dica.
• Receber uma dica e ignorá-la (o entrevistador está te dando o caminho!).

13.1 Onde algoritmos aparecem no trabalho real

Em outras palavras: mesmo que sua vaga não tenha "algoritmos" na descrição, você usará estes padrões para escrever código que escala — e é isso que separa júnior de pleno na revisão de código.

13.2 Plano de estudos de 12 semanas

13.3 Onde praticar

• LeetCode — o padrão de mercado; filtre por empresa e por padrão. Priorize listas curadas (Top Interview 150, Blind 75 / NeetCode 150).
• HackerRank — muitas empresas brasileiras aplicam seus testes online; acostume-se ao formato de leitura de entrada.
• Beecrowd (ex-URI) — enunciados em português, ótimo para começar.
• Codeforces / AtCoder — competições; excelente para velocidade e casos de borda (opcional, nível expert).
• Entrevistas simuladas — Pramp e afins, ou um colega com cronômetro; treinar falando é inegociável.

13.4 Portfólio que algoritmos ajudam a construir

Recrutadores abrem seu GitHub por ~2 minutos. Ideias de repositórios que exibem exatamente o conteúdo desta apostila:

• Biblioteca de estruturas de dados em Python com testes (pytest) e análise de complexidade no README de cada estrutura.
• Visualizador de algoritmos (ordenações ou Dijkstra animado) — projeto visual, memorável em entrevista.
• Motor de autocomplete com trie + distância de edição sobre um dataset real.
• Resolvedor de Sudoku/N-Rainhas com backtracking e benchmark das podas.
• Cache LRU (dict + lista duplamente ligada) com benchmark — pergunta de entrevista que vira projeto.

# Exemplo de "projeto-entrevista": Cache LRU em O(1) por operação
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacidade):
        self.cap = capacidade
        self.dados = OrderedDict()

    def get(self, chave):
        if chave not in self.dados:
            return -1
        self.dados.move_to_end(chave)          # vira o mais recente
        return self.dados[chave]

    def put(self, chave, valor):
        if chave in self.dados:
            self.dados.move_to_end(chave)
        self.dados[chave] = valor
        if len(self.dados) > self.cap:
            self.dados.popitem(last=False)     # expulsa o mais antigo

13.5 O funil seletivo típico (e como cada módulo te salva)

1. Triagem de currículo — projetos do 13.4 + palavras-chave reais (Python, estruturas de dados, testes).
2. Teste online (OA) — 2–3 questões em 60–90 min; busca binária, hash e janela deslizante dominam. Leia TODOS os enunciados antes de começar e ataque o mais fácil primeiro.
3. Entrevista técnica ao vivo — o protocolo do Módulo 12.2.
4. System design (pleno/sênior) — os blocos são os daqui: cache (hash/LRU), fila (mensageria), consistent hashing, ordenação topológica de serviços. Estudar algoritmos é o pré-requisito silencioso desta etapa.
5. Comportamental — prepare 4–5 histórias no formato situação → ação → resultado, incluindo uma de otimização de performance ("reduzi de O(n²) para O(n log n) e o job caiu de 3 h para 4 min" é uma história real e poderosa).

13.6 Código de produção ≠ código de entrevista

No trabalho, complete o algoritmo com engenharia: nomes descritivos, docstrings, tratamento de erros, testes e uso da biblioteca padrão em vez de reimplementação. Exemplo do mesmo problema nas duas versões:

# Entrevista: direto ao ponto
def top_k(nums, k):
    import heapq
    return heapq.nlargest(k, nums)

# Produção: contrato claro, validação e testabilidade
import heapq
from typing import Iterable, TypeVar
T = TypeVar("T")

def top_k(itens: Iterable[T], k: int) -> list[T]:
    """Retorna os k maiores itens em O(n log k).

    Levanta ValueError se k for negativo.
    """
    if k < 0:
        raise ValueError(f"k deve ser >= 0, recebido {k}")
    return heapq.nlargest(k, itens)

from collections import Counter
def primeiro_unico(s):
    c = Counter(s)
    for ch in s:
        if c[ch] == 1:
            return ch
    return None      # O(n)/O(1) — alfabeto limitado

def mesclar(intervalos):
    intervalos.sort()
    res = [intervalos[0]]
    for ini, fim in intervalos[1:]:
        if ini <= res[-1][1]:
            res[-1][1] = max(res[-1][1], fim)
        else:
            res.append([ini, fim])
    return res       # O(n log n)

def dias_espera(temps):
    resp = [0] * len(temps)
    pilha = []                        # índices com temps decrescentes
    for i, t in enumerate(temps):
        while pilha and temps[pilha[-1]] < t:
            j = pilha.pop()
            resp[j] = i - j
        pilha.append(i)
    return resp      # O(n): cada índice entra e sai 1 vez

from collections import deque
def minutos(grade):
    L, C = len(grade), len(grade[0])
    fila, frescas = deque(), 0
    for i in range(L):
        for j in range(C):
            if grade[i][j] == 2: fila.append((i, j, 0))
            elif grade[i][j] == 1: frescas += 1
    t = 0
    while fila:
        i, j, t = fila.popleft()
        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):
            a, b = i+di, j+dj
            if 0 <= a < L and 0 <= b < C and grade[a][b] == 1:
                grade[a][b] = 2
                frescas -= 1
                fila.append((a, b, t+1))
    return t if frescas == 0 else -1   # BFS multi-fonte, O(L·C)

def maior_palindromo(s):
    """Expansão pelo centro: O(n²) tempo, O(1) espaço."""
    def expandir(e, d):
        while e >= 0 and d < len(s) and s[e] == s[d]:
            e -= 1; d += 1
        return s[e+1:d]
    melhor = ""
    for i in range(len(s)):
        for cand in (expandir(i, i), expandir(i, i+1)):  # centros ímpar/par
            if len(cand) > len(melhor):
                melhor = cand
    return melhor

from collections import Counter
def tempo_minimo(tarefas, n):
    freq = Counter(tarefas)
    fmax = max(freq.values())
    qtd_max = sum(1 for v in freq.values() if v == fmax)
    # (fmax-1) blocos de tamanho (n+1) + as últimas tarefas de freq máxima
    return max(len(tarefas), (fmax - 1) * (n + 1) + qtd_max)

def dividir(nums, m):
    def cabe(limite):
        partes, atual = 1, 0
        for x in nums:
            if atual + x > limite:
                partes += 1
                atual = 0
            atual += x
        return partes <= m
    esq, dir = max(nums), sum(nums)
    while esq < dir:
        meio = (esq + dir) // 2
        if cabe(meio): dir = meio
        else:          esq = meio + 1
    return esq       # O(n log(soma))

from functools import lru_cache
def tsp(dist):
    n = len(dist)
    TODAS = (1 << n) - 1

    @lru_cache(maxsize=None)
    def dp(mascara, u):
        """Menor custo estando em u, tendo visitado 'mascara'."""
        if mascara == TODAS:
            return dist[u][0]              # volta para a origem
        melhor = float("inf")
        for v in range(n):
            if not (mascara >> v) & 1:
                melhor = min(melhor, dist[u][v] + dp(mascara | (1 << v), v))
        return melhor

    return dp(1, 0)      # O(2^n · n²) — viável até n≈20

Encerramento

Se você chegou até aqui implementando os códigos e refazendo os exercícios, você cobriu o conteúdo algorítmico cobrado da maioria das vagas de desenvolvimento — do estágio ao sênior. O próximo passo não é mais teoria: é volume deliberado de prática (plano do Módulo 13.2) e treino verbal (protocolo do Módulo 12.2). Bons estudos e boas entrevistas.