Clean Code & Algorithms

Referencia Completa para LLM

Este documento e uma referencia consolidada e densa cobrindo os pilares do desenvolvimento de

software profissional: escrita de codigo limpo, principios de design, padroes, estruturas de dados e
algoritmos fundamentais. Ideal para uso como contexto em modelos de linguagem.

Topicos cobertos:

• Clean Code — Nomenclatura, funcoes, comentarios, formatacao

• SOLID, DRY, KISS, YAGNI e outros principios
• Refactoring — Smells e tecnicas
• Design Patterns — Criacionais, Estruturais, Comportamentais
• Complexidade — Big O, analise assintótica
• Estruturas de Dados — Arrays, Listas, Filas, Pilhas, Arvores, Grafos, Hash
• Algoritmos de Busca e Ordenacao
• Programacao Dinamica e Tecnicas Avancadas
PARTE 1: CLEAN CODE
Clean Code, conceito popularizado por Robert C. Martin (Uncle Bob), define codigo limpo como aquele
que e facil de ler, entender, modificar e testar. Codigo limpo nao e apenas codigo que funciona — e
codigo que comunica a intencao de forma clara para outros desenvolvedores (e para o futuro voce
mesmo).

1.1 Nomenclatura — Use Nomes que Revelam Intencao

Nomes sao a primeira linha de comunicacao do codigo. Um nome ruim forca o leitor a manter contexto
mental extra desnecessario.

Regras fundamentais:

• Use nomes que revelem proposito sem precisar de comentario

• Evite abreviacoes (d, tmp, x, aux) — use nomes completos e descritivos
• Distinga nomes de forma significativa (nao use data1/data2)
• Use nomes pronunciaveis e buscaveis
• Evite encodings de tipo (strNome, iContador)
• Classes: substantivos. Metodos: verbos.

// RUIM
int d; // elapsed time in days
List<int[]> getThem() { ... }
void cpy(User u1, User u2) { ... }

// BOM
int elapsedTimeInDays;
List<Cell> getFlaggedCells() { ... }
void copyUserData(User source, User destination) { ... }

TIP: Se voce precisa de um comentario para explicar o nome, o nome esta errado.

1.2 Funcoes — Pequenas, Coesas, com Uma Responsabilidade

A regra de ouro: funcoes devem fazer UMA coisa, fazer bem, e fazer somente aquilo.

Principios:

• Tamanho: idealmente 5-20 linhas. Se precisar de scroll, provavelmente faz coisas demais
• Um nivel de abstracao por funcao (nao misture logica de negocio com I/O)
• Maximo 3 parametros — acima disso, use um objeto
• Sem efeitos colaterais ocultos
• Prefira retornar valores a modificar estado externo
• Evite flags booleanos como parametro — dividam a funcao

// RUIM — faz varias coisas, nivel de abstracao misturado

void processOrder(Order order, bool sendEmail) {
 // valida, calcula, persiste, envia email...
if ([Link]()) throw new Error("empty");
double total = 0;
for (Item item : [Link]) total += [Link] * [Link];
[Link] = total;
[Link](order);
if (sendEmail) [Link]([Link], "Pedido confirmado");
}

// BOM — cada funcao faz uma coisa

void processOrder(Order order) {
validateOrder(order);
calculateTotal(order);
saveOrder(order);
notifyUser(order);
}

private void validateOrder(Order order) {

if ([Link]()) throw new EmptyOrderException();
}

private void calculateTotal(Order order) {

[Link] = [Link]()
.mapToDouble(i -> [Link] * [Link])
.sum();
}

1.3 Comentarios — O Codigo e a Documentacao

O melhor comentario e aquele que nao precisa existir. Codigo bem escrito se documenta sozinho.

Comentarios ruins (evite):

• Comentarios redundantes que repetem o que o codigo ja diz

• Comentarios desatualizados (mentem sobre o comportamento atual)
• Codigo comentado — delete, o git guarda o historico
• Comentarios de diario (// 2024-01-15: fulano corrigiu bug)

Comentarios bons (use com moderacao):

• Explicacao de intencao quando o codigo nao consegue expressar (workarounds, decisoes de

negocio nao obvias)
• Avisos de consequencias importantes
• TODOs legítimos
• Javadoc/JSDoc em APIs publicas

// RUIM — comentario redundante

// Retorna o nome do usuario
public String getUserName() { return [Link]; }

// RUIM — codigo comentado

// List<User> users = [Link]();
// for (User u : users) { ... }
 // BOM — explica o PORQUE, nao o QUE
// Usamos [Link] aqui porque a API externa tem rate limit
// de 100 req/s e nao retorna 429, simplesmente dropa conexoes
[Link](10);

// BOM — decisao nao obvia

// NaN != NaN e a unica forma de checar NaN sem [Link]()
if (value != value) return DEFAULT;

1.4 Formatacao e Estrutura

• Arquivo: ~200-500 linhas idealmente; max ~1000
• Conceitos relacionados devem estar proximos verticalmente
• Declaracoes de variaveis proximas ao uso
• Funcoes chamadas devem estar abaixo das chamadoras
• Linhas: max 120 caracteres
• Use espaco em branco para separar conceitos distintos

TIP: Consistencia e mais importante que preferencia pessoal. Use linters (ESLint, Prettier, Checkstyle) e
configure no CI.

1.5 Tratamento de Erros

• Prefira excecoes a codigos de retorno de erro
• Crie classes de excecao especificas por dominio
• Nao retorne null — use Optional, Result types ou lance excecao
• Nao passe null como argumento
• Catch so o que voce consegue tratar — nao engula excecoes

// RUIM
User getUser(int id) {
try {
return [Link](id);
} catch (Exception e) {
return null; // caller precisa checar null sempre
}
}

// BOM
Optional<User> getUser(int id) {
return [Link](id); // sem null, sem excecao engolida
}

// BOM (alternativa com excecao de dominio)

User getUser(int id) {
return [Link](id)
.orElseThrow(() -> new UserNotFoundException(id));
}
PARTE 2: PRINCIPIOS DE DESIGN

2.1 SOLID
SOLID e um acronimo para cinco principios de design orientado a objetos que tornam o software mais
mantenivel, flexivel e escalavel.

S — Single Responsibility Principle (SRP)

Uma classe deve ter um, e somente um, motivo para mudar. Coesao alta = responsabilidade unica.

// RUIM — User faz tudo

class User {
void saveToDatabase() { ... }
void sendWelcomeEmail() { ... }
String toJson() { ... }
boolean validatePassword(String pwd) { ... }
}

// BOM — responsabilidades separadas

class User { String name; String email; }
class UserRepository { void save(User u) { ... } }
class UserMailer { void sendWelcome(User u) { ... } }
class UserSerializer { String toJson(User u) { ... } }

O — Open/Closed Principle (OCP)

Entidades devem ser abertas para extensao e fechadas para modificacao. Adicione comportamento sem
alterar codigo existente.

// RUIM — adicionar tipo exige modificar calcular()

double calcularArea(Object shape) {
if (shape instanceof Circulo) return [Link] * r * r;
if (shape instanceof Retangulo) return w * h;
// para adicionar Triangulo, edito aqui
}

// BOM — aberto para extensao via polimorfismo

interface Shape { double area(); }
class Circulo implements Shape { public double area() { return [Link] * r * r; } }
class Retangulo implements Shape { public double area() { return w * h; } }
class Triangulo implements Shape { public double area() { return b * h / 2; } }
// calcular agora e: [Link]().mapToDouble(Shape::area).sum()

L — Liskov Substitution Principle (LSP)

Objetos de uma classe derivada devem poder substituir objetos da classe base sem quebrar o
comportamento.

// VIOLACAO classica — Quadrado herda de Retangulo

class Retangulo {
void setLargura(int w) { this.w = w; }
void setAltura(int h) { this.h = h; }
 int area() { return w * h; }
}
class Quadrado extends Retangulo {
void setLargura(int w) { this.w = w; this.h = w; } // QUEBRA LSP
void setAltura(int h) { this.w = h; this.h = h; } // QUEBRA LSP
}
// Teste que falha com Quadrado mas nao com Retangulo:
// [Link](5); [Link](4); assert [Link]() == 20; // Quadrado retorna 16!

I — Interface Segregation Principle (ISP)

Clientes nao devem depender de interfaces que nao usam. Prefira interfaces especificas a interfaces
gordas.

// RUIM — interface gorda

interface Worker {
void work();
void eat();
void sleep();
}
class Robot implements Worker {
void eat() { throw new UnsupportedOperationException(); } // robos nao comem!
}

// BOM — interfaces segregadas

interface Workable { void work(); }
interface Feedable { void eat(); }
interface Restable { void sleep(); }
class Human implements Workable, Feedable, Restable { ... }
class Robot implements Workable { ... }

D — Dependency Inversion Principle (DIP)

Modulos de alto nivel nao devem depender de modulos de baixo nivel. Ambos devem depender de
abstracoes.

// RUIM — alto nivel (OrderService) depende de baixo nivel (MySQLRepo)

class OrderService {
private MySQLOrderRepository repo = new MySQLOrderRepository();
void placeOrder(Order o) { [Link](o); }
}

// BOM — depende da abstracao, nao da implementacao

interface OrderRepository { void save(Order o); }
class OrderService {
private final OrderRepository repo;
OrderService(OrderRepository repo) { [Link] = repo; } // injecao
void placeOrder(Order o) { [Link](o); }
}
// Pode usar MySQL, Postgres, InMemory, Mock — sem alterar OrderService
2.2 DRY, KISS e YAGNI
DRY — Don't Repeat Yourself
Cada pedaco de conhecimento deve ter uma representacao unica, inequivoca e autoritativa no sistema.
Duplicacao e a raiz de muita manutencao dolorosa — uma mudanca exige atualizacoes em N lugares.

• Extraia logica duplicada em funcoes/metodos

• Use constantes em vez de magic numbers espalhados
• Compartilhe esquemas de validacao, nao os repita em cada camada
ATENCAO: DRY se aplica a CONHECIMENTO, nao apenas a texto. Dois trechos identicos com
semânticas diferentes NAO sao duplicacao.

KISS — Keep It Simple, Stupid

A solucao mais simples que funciona e geralmente a melhor. Complexidade desnecessaria aumenta bugs
e dificulta manutencao.

• Evite over-engineering — nao adicione camadas de abstracao sem necessidade

• Prefira codigo linear a recursao quando ambos tem complexidade similar
• Pergunte: existe uma forma mais simples de resolver isso?

YAGNI — You Aren't Gonna Need It

Nao implemente funcionalidade antecipando necessidades futuras. Implemente o que voce precisa agora.

• Custo de funcionalidade: construir + manter + documentar + testar

• Codigo que nao existe nao tem bugs
• Combine com KISS: simples agora, refatore quando necessario

Lei de Demeter (Principio do Minimo Conhecimento)

Um metodo deve conversar apenas com seus amigos imediatos, nao com estranhos.

// RUIM — viola Lei de Demeter (train wreck)

String city = [Link]().getCity().getName();
[Link]().getWallet().debit(amount);

// BOM — delega para o objeto responsavel

String city = [Link](); // User conhece seu endereco
[Link](amount); // Order sabe como cobrar
PARTE 3: REFACTORING
Refactoring e o processo de melhorar a estrutura interna do codigo sem alterar seu comportamento
externo. E uma pratica continua, nao um evento pontual.

3.1 Code Smells — Sinais de Problema

Code Smell Descricao

Long Method Metodos grandes demais. Regra: se voce precisa comentar blocos dentro do metodo, extraia em funcoes.

Large Class Classe com muitas responsabilidades. Violar SRP. Sintoma: muitas variaveis de instancia sem relacao.

Long Parameter List Mais de 3-4 parametros. Agrupe em objeto Parameter Object.

Duplicate Code Mesmo codigo em dois lugares. Extraia para funcao/classe compartilhada.

Divergent Change Uma classe e modificada por razoes diferentes. Separe as responsabilidades.

Shotgun Surgery Uma mudanca de requisito exige alteracoes em muitas classes. Consolide a responsabilidade.

Feature Envy Um metodo usa mais dados de outra classe do que da propria. Mova o metodo.

Data Clumps Grupos de dados que sempre aparecem juntos. Extraia para uma classe.

Primitive Obsession Uso excessivo de primitivos onde objetos de dominio seriam mais claros (CPF como String, Dinheiro como

Switch Statements Switches sobre tipo costumam violar OCP. Polimorfismo frequentemente e melhor.

Lazy Class Classe que nao faz o suficiente para justificar sua existencia. Inline ou delete.

Dead Code Codigo que nunca e executado. Delete sem piedade — o git tem historico.

Comments Comentarios excessivos compensando codigo obscuro. Melhore o codigo, nao o comentario.

3.2 Tecnicas de Refactoring

Extract Method
// ANTES
void printOrder(Order order) {
[Link]("Order: " + [Link]);
double total = 0;
for (Item i : [Link]) total += [Link] * [Link];
[Link]("Total: " + total);
}

// DEPOIS
void printOrder(Order order) {
printHeader(order);
printTotal(order);
}
private void printHeader(Order o) { [Link]("Order: " + [Link]); }
private double calculateTotal(Order o) {
return [Link]().mapToDouble(i -> [Link] * [Link]).sum();
}
private void printTotal(Order o) { [Link]("Total: " + calculateTotal(o)); }

Replace Conditional with Polymorphism

 // ANTES
double getSpeed(Animal animal) {
switch ([Link]) {
case EUROPEAN_SWALLOW: return BASE_SPEED;
case AFRICAN_SWALLOW: return BASE_SPEED - [Link] * 2;
case PARROT: return [Link] ? 0 : BASE_SPEED + [Link] / 10;
}
}

// DEPOIS
abstract class Animal { abstract double getSpeed(); }
class EuropeanSwallow extends Animal { double getSpeed() { return BASE_SPEED; } }
class AfricanSwallow extends Animal { double getSpeed() { return BASE_SPEED - coconuts * 2; } }
class Parrot extends Animal { double getSpeed() { return isNailed ? 0 : BASE_SPEED + voltage / 10;

Introduce Parameter Object

// ANTES
void reserveRoom(Date startDate, Date endDate, int guests, String roomType) { ... }

// DEPOIS
class ReservationRequest {
DateRange period;
int guests;
String roomType;
}
void reserveRoom(ReservationRequest request) { ... }
PARTE 4: DESIGN PATTERNS
Design Patterns sao solucoes reutilizaveis para problemas recorrentes no design de software.
Categorizados em Criacionais, Estruturais e Comportamentais (GoF — Gang of Four).

4.1 Padroes Criacionais

Singleton
Garante uma unica instancia e ponto de acesso global.

public class Database {

private static Database instance;
private Database() {}
public static synchronized Database getInstance() {
if (instance == null) instance = new Database();
return instance;
}
}
// Thread-safe alternative: initialization-on-demand holder
private static class Holder { static final Database DB = new Database(); }
public static Database getInstance() { return [Link]; }

Factory Method
Define interface para criar objetos, deixando subclasses decidirem qual classe instanciar.

interface Button { void render(); }

class WindowsButton implements Button { public void render() { /* win style */ } }
class MacButton implements Button { public void render() { /* mac style */ } }

abstract class Dialog {

abstract Button createButton(); // factory method
void render() { Button btn = createButton(); [Link](); }
}
class WindowsDialog extends Dialog { Button createButton() { return new WindowsButton(); } }
class MacDialog extends Dialog { Button createButton() { return new MacButton(); } }

Builder
Constroi objetos complexos passo a passo. Util quando ha muitos parametros opcionais.

class Pizza {
private final String size, crust;
private final boolean cheese, pepperoni, mushrooms;
private Pizza(Builder b) { [Link] = [Link]; /* ... */ }

static class Builder {

private String size, crust = "thin";
private boolean cheese, pepperoni, mushrooms;
Builder(String size) { [Link] = size; }
Builder crust(String c) { [Link] = c; return this; }
Builder cheese() { [Link] = true; return this; }
Builder pepperoni() { [Link] = true; return this; }
 Pizza build() { return new Pizza(this); }
}
}
Pizza p = new [Link]("large").cheese().pepperoni().build();

4.2 Padroes Estruturais

Adapter
Converte a interface de uma classe em outra esperada pelos clientes.

// Sistema legado
class OldLogger { void logMessage(String msg) { [Link]("[OLD] " + msg); } }

// Interface nova esperada

interface Logger { void info(String msg); void error(String msg); }

// Adapter
class LoggerAdapter implements Logger {
private OldLogger old = new OldLogger();
public void info(String msg) { [Link]("INFO: " + msg); }
public void error(String msg) { [Link]("ERROR: " + msg); }
}

Decorator
Adiciona responsabilidades a objetos dinamicamente, alternativa flexivel ao subclassing.

interface Coffee { double getCost(); String getDescription(); }

class SimpleCoffee implements Coffee {
public double getCost() { return 1.0; }
public String getDescription() { return "Coffee"; }
}
abstract class CoffeeDecorator implements Coffee {
protected Coffee coffee;
CoffeeDecorator(Coffee c) { [Link] = c; }
}
class MilkDecorator extends CoffeeDecorator {
MilkDecorator(Coffee c) { super(c); }
public double getCost() { return [Link]() + 0.25; }
public String getDescription() { return [Link]() + ", Milk"; }
}
// Uso: Coffee c = new MilkDecorator(new SugarDecorator(new SimpleCoffee()));

Observer
Define dependencia um-para-muitos: quando um objeto muda, todos dependentes sao notificados.

interface Observer { void update(String event); }

interface Observable {
void subscribe(Observer o);
void unsubscribe(Observer o);
void notify(String event);
}
class EventBus implements Observable {
 private List<Observer> observers = new ArrayList<>();
public void subscribe(Observer o) { [Link](o); }
public void unsubscribe(Observer o) { [Link](o); }
public void notify(String event) { [Link](o -> [Link](event)); }
}
class EmailNotifier implements Observer {
public void update(String event) { [Link]("Email: " + event); }
}

Strategy
Define familia de algoritmos, encapsula cada um e os torna intercambiaveis.

interface SortStrategy { void sort(int[] arr); }

class BubbleSort implements SortStrategy { public void sort(int[] arr) { /* bubble */ } }
class QuickSort implements SortStrategy { public void sort(int[] arr) { /* quick */ } }

class Sorter {
private SortStrategy strategy;
Sorter(SortStrategy s) { [Link] = s; }
void setStrategy(SortStrategy s) { [Link] = s; }
void sort(int[] arr) { [Link](arr); }
}
// Sorter s = new Sorter(new QuickSort());
// [Link](new BubbleSort()); // troca em runtime
PARTE 5: COMPLEXIDADE E NOTACAO BIG O
Big O descreve o comportamento assintótico de um algoritmo — como o tempo de execucao ou uso de
memoria cresce em relacao ao tamanho da entrada (n), ignorando constantes e termos menores.

Notacao Nome Exemplo n=10 n=100 n=1000

O(1) Constante Acesso array por indice 1 1 1

O(log n) Logaritmica Binary search 3 7 10

O(n) Linear Loop simples 10 100 1.000

O(n log n) Linearitmica Merge sort, heap sort 33 664 9.966

O(n^2) Quadratica Bubble sort, nested loops 100 10.000 1.000.000

O(n^3) Cubica Matrix multiplication naive 1.000 1.000.000 ~10^9

O(2^n) Exponencial Subsets, recursive fib 1.024 ~10^30 impossivel

O(n!) Fatorial Permutacoes, TSP bruteforce 3.628.800 impossivel impossivel

5.1 Regras de Analise

• Drop constants: O(2n) = O(n), O(100) = O(1)
• Drop non-dominant terms: O(n^2 + n) = O(n^2)
• Different variables: loop em A e B = O(a + b), nested = O(a * b)
• Recursao: complexidade = branches^depth (sem memoizacao)

// O(1) — sem loop, sem recursao proporcional a n

int first = arr[0];

// O(n) — loop unico

for (int x : arr) process(x);

// O(n^2) — nested loops sobre mesma colecao

for (int i : arr)
for (int j : arr)
if (i != j) compare(i, j);

// O(log n) — divide input pela metade a cada passo

int binarySearch(int[] arr, int target) {
int lo = 0, hi = [Link] - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) lo = mid + 1; else hi = mid - 1;
}
return -1;
}

// O(n log n) — divide e conquista com merge

void mergeSort(int[] arr, int lo, int hi) {
if (lo >= hi) return;
 int mid = (lo + hi) / 2;
mergeSort(arr, lo, mid);
mergeSort(arr, mid+1, hi);
merge(arr, lo, mid, hi); // O(n)
}

5.2 Complexidade de Espaco

• O(1): variaveis de tamanho fixo, sem estruturas proporcionais a n
• O(n): array/lista de tamanho n, recursao com n niveis na call stack
• O(log n): recursao binary search (log n frames na stack)
• O(n^2): matriz n x n
TIP: Sempre analise tanto tempo quanto espaco. Muitos algoritmos trocam um pelo outro (memoizacao:
tempo O(n) com espaco O(n) vs tempo O(2^n) com espaco O(n)).
PARTE 6: ESTRUTURAS DE DADOS

6.1 Array / Lista Dinamica

Colecao de elementos em posicoes contíguas de memoria. Acesso O(1) por indice. Insercao/remocao no
meio O(n).

Operacao Array Dynamic Array (ArrayList)

Acesso por indice O(1) O(1)

Busca O(n) O(n)

Insercao no final O(1)* O(1) amortizado

Insercao no inicio/meio O(n) O(n)

Remocao no final O(1) O(1)

Remocao no inicio/meio O(n) O(n)

Espaco O(n) O(n)

6.2 Linked List

Nos encadeados onde cada no aponta para o proximo. Insercao/remocao O(1) se voce tem o ponteiro;
busca O(n).

class Node<T> {
T data;
Node<T> next;
Node(T data) { [Link] = data; }
}
class LinkedList<T> {
Node<T> head;
void addFirst(T data) {
Node<T> node = new Node<>(data);
[Link] = head;
head = node;
}
void addLast(T data) {
Node<T> node = new Node<>(data);
if (head == null) { head = node; return; }
Node<T> curr = head;
while ([Link] != null) curr = [Link];
[Link] = node;
}
boolean contains(T data) {
Node<T> curr = head;
while (curr != null) {
if ([Link](data)) return true;
curr = [Link];
}
return false;
}
}
6.3 Stack (Pilha)
LIFO — Last In, First Out. Operacoes: push, pop, peek. Todas O(1). Usada em: undo, chamadas
recursivas, parsing de expressoes.

// Implementacao com array

class Stack<T> {
private Object[] data;
private int top = -1;
Stack(int capacity) { data = new Object[capacity]; }
void push(T item) { data[++top] = item; }
T pop() { return (T) data[top--]; }
T peek() { return (T) data[top]; }
boolean isEmpty() { return top == -1; }
}

// Verificar parenteses balanceados — uso classico de stack

boolean isBalanced(String s) {
Stack<Character> st = new Stack<>([Link]());
for (char c : [Link]()) {
if ("([{".indexOf(c) >= 0) [Link](c);
else if (c == ')' && ([Link]() || [Link]() != '(')) return false;
else if (c == ']' && ([Link]() || [Link]() != '[')) return false;
else if (c == '}' && ([Link]() || [Link]() != '{')) return false;
}
return [Link]();
}

6.4 Queue (Fila)

FIFO — First In, First Out. Operacoes: enqueue, dequeue, peek. Todas O(1) com linked list. Usada em:
BFS, filas de processamento, agendamento.

6.5 Hash Table

Estrutura de mapa chave-valor com acesso O(1) medio. Usa funcao hash para mapear chaves em
indices. Colisoes resolvidas por chaining ou open addressing.

// Complexidades HashMap/HashSet
// Acesso/busca/insercao/remocao: O(1) medio, O(n) pior caso (muitas colisoes)

// Padrao de uso: contagem de frequencias

Map<String, Integer> freq = new HashMap<>();
for (String word : words) {
[Link](word, [Link](word, 0) + 1);
}

// Two Sum — uso classico de hash

int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>(); // valor -> indice
for (int i = 0; i < [Link]; i++) {
int complement = target - nums[i];
if ([Link](complement)) return new int[]{[Link](complement), i};
[Link](nums[i], i);
}
 return new int[]{};
}

6.6 Arvores Binarias

Estrutura hierarquica onde cada no tem ate 2 filhos. BST (Binary Search Tree): no esquerdo < no atual <
no direito.

class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { [Link] = val; }
}

// Travessias — complexidade O(n) para todas

void inorder(TreeNode node) { // esquerda, raiz, direita — retorna ordenado para BST
if (node == null) return;
inorder([Link]);
[Link]([Link] + " ");
inorder([Link]);
}
void preorder(TreeNode node) { // raiz, esquerda, direita — util para copiar arvore
if (node == null) return;
[Link]([Link] + " ");
preorder([Link]);
preorder([Link]);
}
void postorder(TreeNode node) { // esquerda, direita, raiz — util para deletar
if (node == null) return;
postorder([Link]);
postorder([Link]);
[Link]([Link] + " ");
}

// Altura da arvore
int height(TreeNode node) {
if (node == null) return 0;
return 1 + [Link](height([Link]), height([Link]));
}

6.7 Grafos
Conjunto de nos (vertices) conectados por arestas. Podem ser direcionados ou nao, ponderados ou nao.

// Representacao por lista de adjacencia

class Graph {
private Map<Integer, List<Integer>> adj = new HashMap<>();
void addEdge(int u, int v) {
[Link](u, k -> new ArrayList<>()).add(v);
[Link](v, k -> new ArrayList<>()).add(u); // remova para grafo dirigido
}
List<Integer> neighbors(int u) { return [Link](u, new ArrayList<>()); }
}

// BFS — nivel por nivel, menor caminho em grafo nao ponderado

void bfs(int start) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
[Link](start);
[Link](start);
while (![Link]()) {
int node = [Link]();
[Link](node + " ");
for (int neighbor : [Link](node, [Link]())) {
if () {
[Link](neighbor);
[Link](neighbor);
}
}
}
}

// DFS — explora fundo antes de voltar, detecta ciclos, componentes conexos

void dfs(int node, Set<Integer> visited) {
[Link](node);
[Link](node + " ");
for (int neighbor : [Link](node, [Link]())) {
if () dfs(neighbor, visited);
}
}
PARTE 7: ALGORITMOS DE ORDENACAO
Algoritmo Melhor Medio Pior Espaco Estavel? Uso

Bubble Sort O(n) O(n^2) O(n^2) O(1) Sim Didatico

Selection Sort O(n^2) O(n^2) O(n^2) O(1) Nao Raramente

Insertion Sort O(n) O(n^2) O(n^2) O(1) Sim Pequenos/quase ordenados

Merge Sort O(n log n) O(n log n) O(n log n) O(n) Sim Geral, listas

Quick Sort O(n log n) O(n log n) O(n^2) O(log n) Nao Geral, cache-friendly

Heap Sort O(n log n) O(n log n) O(n log n) O(1) Nao Garantia pior caso

Counting Sort O(n+k) O(n+k) O(n+k) O(k) Sim Inteiros pequenos

Radix Sort O(nk) O(nk) O(nk) O(n+k) Sim Inteiros, strings

7.1 Implementacoes
Merge Sort
int[] mergeSort(int[] arr) {
if ([Link] <= 1) return arr;
int mid = [Link] / 2;
int[] left = mergeSort([Link](arr, 0, mid));
int[] right = mergeSort([Link](arr, mid, [Link]));
return merge(left, right);
}
int[] merge(int[] left, int[] right) {
int[] result = new int[[Link] + [Link]];
int i = 0, j = 0, k = 0;
while (i < [Link] && j < [Link])
result[k++] = left[i] <= right[j] ? left[i++] : right[j++];
while (i < [Link]) result[k++] = left[i++];
while (j < [Link]) result[k++] = right[j++];
return result;
}

Quick Sort
void quickSort(int[] arr, int lo, int hi) {
if (lo < hi) {
int pivot = partition(arr, lo, hi);
quickSort(arr, lo, pivot - 1);
quickSort(arr, pivot + 1, hi);
}
}
int partition(int[] arr, int lo, int hi) {
int pivot = arr[hi];
int i = lo - 1;
for (int j = lo; j < hi; j++) {
if (arr[j] <= pivot) { i++; swap(arr, i, j); }
}
swap(arr, i + 1, hi);
return i + 1;
}
void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
PARTE 8: ALGORITMOS DE BUSCA

8.1 Binary Search

Busca em array ORDENADO dividindo o espaco pela metade a cada passo. O(log n).

// Iterativo
int binarySearch(int[] arr, int target) {
int lo = 0, hi = [Link] - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // evita overflow vs (lo+hi)/2
if (arr[mid] == target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1; // nao encontrado
}

// Buscar primeira ocorrencia (lower bound)

int lowerBound(int[] arr, int target) {
int lo = 0, hi = [Link];
while (lo < hi) {
int mid = (lo + hi) / 2;
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo; // indice da primeira ocorrencia >= target
}

// Template mental: lo=0, hi=n-1, loop while lo<=hi, ajusta lo/hi baseado em comparacao

8.2 BFS vs DFS em Grafos/Arvores

BFS (Breadth-First Search) — Use quando: menor caminho em grafo nao ponderado, nivel por nivel,
proximos primeiros.

DFS (Depth-First Search) — Use quando: detectar ciclos, componentes conexos, topological sort,
backtracking, explorar todos os caminhos.

// BFS em arvore binaria (nivel por nivel)

List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
[Link](root);
while (![Link]()) {
int size = [Link]();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = [Link]();
[Link]([Link]);
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}
 [Link](level);
}
return result;
}
PARTE 9: PROGRAMACAO DINAMICA
Programacao Dinamica (DP) resolve problemas quebrando-os em subproblemas sobrepostos e
armazenando solucoes (memoizacao/tabulacao) para evitar recomputacao.

Quando usar DP: problema de otimizacao (max/min), contagem, decisao binaria; subproblemas
sobrepostos; subestrutura otima (solucao otima usa solucoes otimas dos subproblemas).

9.1 Fibonacci — Exemplo Base

// RECURSAO PURA: O(2^n) — ruim
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}

// TOP-DOWN (Memoizacao): O(n) tempo, O(n) espaco

int[] memo = new int[101];
int fibMemo(int n) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n];
return memo[n] = fibMemo(n-1) + fibMemo(n-2);
}

// BOTTOM-UP (Tabulacao): O(n) tempo, O(n) espaco

int fibTab(int n) {
int[] dp = new int[n+1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}

// OTIMIZADO: O(n) tempo, O(1) espaco

int fibOpt(int n) {
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) { int c = a + b; a = b; b = c; }
return b;
}

9.2 0/1 Knapsack

Dado n itens com peso e valor, e uma mochila com capacidade W, maximize o valor total sem exceder W.

int knapsack(int[] weights, int[] values, int W) {

int n = [Link];
int[][] dp = new int[n+1][W+1];
// dp[i][w] = max valor usando primeiros i itens com capacidade w
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
dp[i][w] = dp[i-1][w]; // nao pega item i
if (weights[i-1] <= w) {
 dp[i][w] = [Link](dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1]); // pega item i
}
}
}
return dp[n][W]; // O(n*W) tempo e espaco
}

9.3 Longest Common Subsequence (LCS)

int lcs(String a, String b) {
int m = [Link](), n = [Link]();
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if ([Link](i-1) == [Link](j-1)) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = [Link](dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n]; // O(m*n) tempo e espaco
}

9.4 Coin Change

// Minimo de moedas para atingir amount
int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
[Link](dp, amount + 1); // inicializa com infinito
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) dp[i] = [Link](dp[i], dp[i - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount]; // O(amount * coins) tempo
}

9.5 Sliding Window

Tecnica para subarray/substring de tamanho k ou com restricao. Evita loops aninhados O(n^2), reduz
para O(n).

// Maior soma de subarray de tamanho k

int maxSumSubarray(int[] arr, int k) {
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
int maxSum = windowSum;
for (int i = k; i < [Link]; i++) {
windowSum += arr[i] - arr[i - k]; // desliza a janela
maxSum = [Link](maxSum, windowSum);
}
return maxSum; // O(n)
}

// Menor subarray com soma >= target (janela variavel)

int minLenSubarray(int[] arr, int target) {
int lo = 0, sum = 0, minLen = Integer.MAX_VALUE;
for (int hi = 0; hi < [Link]; hi++) {
sum += arr[hi];
while (sum >= target) {
minLen = [Link](minLen, hi - lo + 1);
sum -= arr[lo++];
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen; // O(n)
}
PARTE 10: TECNICAS ADICIONAIS

10.1 Two Pointers

Dois ponteiros movendo-se em direcoes distintas ou na mesma direcao para resolver problemas em O(n)
que teriam O(n^2) naive.

// Two Sum em array ordenado

int[] twoSumSorted(int[] arr, int target) {
int lo = 0, hi = [Link] - 1;
while (lo < hi) {
int sum = arr[lo] + arr[hi];
if (sum == target) return new int[]{lo, hi};
else if (sum < target) lo++;
else hi--;
}
return new int[]{};
}

// Reverter array in-place

void reverse(int[] arr) {
int lo = 0, hi = [Link] - 1;
while (lo < hi) { swap(arr, lo++, hi--); }
}

// Remover duplicatas de array ordenado

int removeDuplicates(int[] arr) {
if ([Link] == 0) return 0;
int slow = 0;
for (int fast = 1; fast < [Link]; fast++) {
if (arr[fast] != arr[slow]) arr[++slow] = arr[fast];
}
return slow + 1; // tamanho do array sem duplicatas
}

10.2 Backtracking
Explore todas as possibilidades construindo candidatos e abandonando (pruning) quando inviavel. Base
de algoritmos para permutacoes, combinacoes, sudoku, N-Queens.

// Gerar todas as permutacoes

List<List<Integer>> permutations(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, new boolean[[Link]], new ArrayList<>(), result);
return result;
}
void backtrack(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> result) {
if ([Link]() == [Link]) {
[Link](new ArrayList<>(current));
return;
}
for (int i = 0; i < [Link]; i++) {
if (used[i]) continue;
 used[i] = true;
[Link](nums[i]);
backtrack(nums, used, current, result); // explora
[Link]([Link]() - 1); // desfaz (backtrack)
used[i] = false;
}
}

// Gerar todos os subsets

List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrackSubsets(nums, 0, new ArrayList<>(), result);
return result;
}
void backtrackSubsets(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
[Link](new ArrayList<>(current));
for (int i = start; i < [Link]; i++) {
[Link](nums[i]);
backtrackSubsets(nums, i + 1, current, result);
[Link]([Link]() - 1);
}
}

10.3 Prefix Sum

Pre-computa somas acumuladas para responder queries de soma de subarray em O(1) apos O(n) de
preprocessamento.

int[] buildPrefixSum(int[] arr) {

int[] prefix = new int[[Link] + 1];
for (int i = 0; i < [Link]; i++) prefix[i+1] = prefix[i] + arr[i];
return prefix;
}
// Soma de arr[l..r] (inclusivo)
int rangeSum(int[] prefix, int l, int r) { return prefix[r+1] - prefix[l]; }

10.4 Monotonic Stack

Stack que mantem elementos em ordem crescente ou decrescente. Resolve problemas de 'proximo
elemento maior/menor' em O(n).

// Proximo elemento maior para cada posicao

int[] nextGreater(int[] arr) {
int[] result = new int[[Link]];
[Link](result, -1);
Deque<Integer> stack = new ArrayDeque<>(); // indices
for (int i = 0; i < [Link]; i++) {
while (![Link]() && arr[[Link]()] < arr[i]) {
result[[Link]()] = arr[i];
}
[Link](i);
}
return result;
}
 PARTE 11: CHEATSHEET — QUANDO USAR O
QUE
Problema / Sinal Estrutura / Tecnica

Acesso rapido por chave Hash Map / Hash Set

Menor caminho (nao ponderado) BFS

Explorar todos os caminhos, ciclos DFS

Menor caminho (ponderado, sem neg) Dijkstra (heap + dist[])

Menor caminho (com negativos) Bellman-Ford

Ordenacao topologica DFS/Kahn (BFS com in-degree)

Subarray/substring continua Sliding Window

Par de indices em array Two Pointers

Busca em array ordenado Binary Search

Max/min de janela Monotonic Deque

Proximo maior/menor elemento Monotonic Stack

Problema de otimizacao/contagem Dynamic Programming

Todas permutacoes/combinacoes Backtracking

Range sum queries Prefix Sum / Segment Tree

Priority queue / top-K Heap (min ou max)

Fila com dequeue ambos lados Deque (ArrayDeque)

Union-Find / componentes conexos DSU (Disjoint Set Union)

Intervalo de valores, busca por indice Segment Tree / BIT (Fenwick)

String matching KMP / Rabin-Karp / Trie

Principios para Lembrar Sempre

• Codigo e lido muito mais vezes do que escrito — otimize para leitura
• Faca funcionar, faca certo, faca rapido — nessa ordem
• Premature optimization is the root of all evil (Knuth)
• Meça antes de otimizar — profile, nao chute
• Um bom nome elimina a necessidade de um comentario
• Testes sao a rede de segurança que permite refatorar com confiança
• Prefira composicao a heranca
• Programe para interfaces, nao implementacoes
• O(n log n) e frequentemente bom o suficiente; O(n^2) frequentemente nao e
• Estrutura de dados certa resolve o problema; estrutura errada cria um
Referencia consolidada — Clean Code (Robert C. Martin), Design Patterns (GoF), Introduction to
Algorithms (CLRS), Cracking the Coding Interview (Gayle McDowell), Refactoring (Martin Fowler).