Algoritmos e Estruturas de Dados
para Entrevista Tech — Guia Completo em Português
O guia definitivo de algoritmos e estruturas de dados para entrevistas técnicas em empresas americanas. Todos os tópicos essenciais com exemplos práticos, complexidade de tempo/espaço e padrões de reconhecimento.
Big O Notation — Complexidade de Tempo
| Notação | Nome | Exemplo |
|---|---|---|
| O(1) | Constante | Acesso por índice em array |
| O(log n) | Logarítmica | Binary search |
| O(n) | Linear | Loop simples, busca em array |
| O(n log n) | Log-linear | Merge sort, heap sort |
| O(n²) | Quadrática | Loops aninhados, bubble sort |
| O(2ⁿ) | Exponencial | Fibonacci recursivo, combinações |
Estruturas de Dados Fundamentais
Array / Lista
O(1) acesso, O(n) buscaA estrutura mais básica. Acesso por índice O(1). Inserção/deleção no meio O(n). Fundamental em qualquer linguagem.
Hash Map / Dicionário
O(1) acesso médioPara problemas de contagem, cache e busca por chave. A estrutura mais poderosa para otimizar soluções O(n²) para O(n).
Stack (Pilha)
O(1) push/popLIFO (Last In, First Out). Usado em problemas de parsing, balanceamento de parênteses, e backtracking.
Queue (Fila)
O(1) enqueue/dequeueFIFO (First In, First Out). Essencial para BFS (Breadth-First Search) em grafos e trees.
Linked List
O(n) acesso, O(1) inserçãoLista com ponteiros. Menos usada em prática, mas frequente em entrevistas. Padrões: Fast/Slow pointers, reverse.
Binary Tree / BST
O(log n) busca (BST)Estrutura hierárquica. BST: filhos esquerda < raiz < direita. Traversals: inorder, preorder, postorder.
Heap (Min/Max Heap)
O(log n) insert/removePara problemas de 'k maiores/menores', top-K. Python: heapq. Java: PriorityQueue.
Grafo (Graph)
O(V+E) traversalConjunto de nós e arestas. Pode ser dirigido ou não-dirigido, com ou sem peso. BFS e DFS são os algoritmos base.
Padrões de Algoritmos
Two Pointers
Geralmente O(n)Dois ponteiros movendo-se no mesmo array. Resolve: somas de pares, strings palíndromos, merge de arrays. Substitui loops O(n²) por O(n).
Sliding Window
O(n)Janela de tamanho fixo ou variável deslizando pelo array. Para: subarray de soma máxima, substring com k caracteres únicos.
BFS (Busca em Largura)
O(V+E)Explora nível por nível usando uma fila. Para: caminho mais curto em grafos não-ponderados, nível de uma árvore, conexões entre nodes.
DFS (Busca em Profundidade)
O(V+E)Explora o mais fundo possível usando recursão ou stack. Para: detectar ciclos, componentes conectados, backtracking.
Binary Search
O(log n)Divide e conquista em array sorted. Para: encontrar elemento, primeiro/último true/false. Sempre verificar: array ordenado? posso dividir ao meio?
Dynamic Programming
Varia: O(n) a O(n²)Memorização de subproblemas para evitar recalcular. Patterns: 0/1 Knapsack, Longest Common Subsequence, Fibonacci-style.
Backtracking
Exponencial (pior caso)Exploração com desfazer. Para: permutações, combinações, Sudoku, N-Queens. DFS + undo da escolha ao retornar.
Greedy
Geralmente O(n log n)Escolhe a melhor opção local em cada passo. Para: interval scheduling, coin change (com certas condições), Dijkstra.
Plano de estudo de 8 semanas
- →Arrays e Hash Maps (20 problemas)
- →Two Pointers (10 problemas)
- →Sliding Window (10 problemas)
- →Binary Trees — BFS e DFS (15 problemas)
- →Grafos — componentes, ciclos (10 problemas)
- →Binary Search (10 problemas)
- →Dynamic Programming básico (15 problemas)
- →Heaps e Priority Queues (10 problemas)
- →Backtracking (10 problemas)
- →Mock interviews completos (3x por semana)
- →Review de problemas errados
- →Praticar comunicação em inglês técnico
FAQ sobre algoritmos para entrevistas
Preciso saber todos os algoritmos para passar em entrevistas de FAANG?
Não. Para a maioria das vagas, você precisa dominar os padrões fundamentais: arrays, hash maps, two pointers, sliding window, BFS/DFS e dynamic programming básico. Hard DP é necessário para FAANG+, mas não para a maioria das startups.
Quantos LeetCode problems preciso resolver?
Qualidade importa mais que quantidade. 100–150 problemas bem resolvidos (entendendo os padrões) valem mais que 500 soluções decoradas. Foque em Medium, com alguns Easy para aquecimento e alguns Hard para FAANG.
Qual a diferença de complexidade O(n) vs O(n²)?
O(n) significa que o tempo cresce linearmente com a entrada — dobrou o input, dobrou o tempo. O(n²) cresce quadraticamente — dobrou o input, quadruplicou o tempo. Para entrevistas: loops simples = O(n), loops aninhados = O(n²). O objetivo é sempre minimizar a complexidade.
Como estudar algoritmos de forma eficiente?
Estude por padrão, não por problema. Aprenda o padrão 'Two Pointers', então resolva 5–10 problemas que usam ele. Depois 'Sliding Window', depois 'BFS', etc. Assim você reconhece o padrão em problemas novos, em vez de memorizar soluções.
Pratique algoritmos com feedback de IA
O simulador de coding do VagaNaGringa cobre todos esses padrões, com problemas reais no estilo LeetCode e feedback instantâneo sobre sua solução, comunicação e Big O. Tudo em português.