Esta lição foi traduzida automaticamente para português e ainda não foi revisada por uma pessoa. Se algo parecer estranho, a versão em inglês é a definitiva.
Aqui está um segredo que os melhores treinadores de entrevistas não cobrarão US$ 500 para aprender: cerca de 90% dos problemas de codificação de entrevistas giram em torno de apenas sete estruturas de dados. Se você compreender profundamente quando e por que buscar cada um deles, já venceu metade da batalha. A outra metade é prática – mas sem os modelos mentais corretos, a prática é apenas memorização. Esta lição fornece o mapa para que cada problema que você encontre pareça um território familiar.
Cada entrevista técnica baseia-se no mesmo poço. Aqui estão as estruturas que você encontrará, classificadas por frequência:
| Estrutura de dados | Frequência da Entrevista | Operações principais | Quando os entrevistadores esperam isso | |---|---|---|---| | Matrizes/Strings | ★★★★★ | Acesse O(1), Pesquise O(n), Inserir O(n) | Quase todos os problemas começam aqui | | Mapas/conjuntos de hash | ★★★★★ | Inserir O(1), Pesquisar O(1), Excluir O(1) | "Otimize isso de O(n²) para O(n)" | | Listas vinculadas | ★★★★☆ | Inserir O(1), Excluir O(1), Acesse O(n) | Manipulação de ponteiro, detecção de ciclo | | Pilhas e filas | ★★★★☆ | Push/Pop O(1), Enfileirar/Desenfileirar O(1) | Análise, BFS, desfazer operações | | Árvores (Binário, BST) | ★★★★☆ | Pesquisar O(log n), Inserir O(log n) | Dados hierárquicos, operações ordenadas | | Gráficos | ★★★☆☆ | Depende da representação | Relacionamentos, caminhos, conectividade | | ** Montes ** | ★★★☆☆ | Inserir O(log n), Extrair-min O(log n) | "Encontre o k maior/menor" |
Matrizes são o ponto de partida para quase todos os problemas de entrevista. O principal insight é que a maioria dos problemas de matrizes não são realmente sobre matrizes — tratam-se de reconhecer padrões como dois ponteiros, janelas deslizantes ou somas de prefixos.
# Two Sum — the most classic interview problem
# "Given an array and target, find two numbers that add to target"
def two_sum(nums, target):
seen = {} # Hash map to store complement
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
# Time: O(n), Space: O(n) — trading space for time
Observe como até mesmo esse problema de “matriz” é na verdade um problema de mapa hash. Esse padrão se repete constantemente: a força bruta usa loops aninhados em uma matriz e a solução ideal introduz um mapa hash.
Inicie sessão para participar na discussão
Se você estiver preso em algum problema e a força bruta for O(n²), pergunte-se: "Um mapa hash pode reduzir isso para O(n)?" A resposta é sim, com uma frequência surpreendente.
Os mapas hash brilham quando você precisa:
// Group Anagrams — a classic hash map problem
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
Problemas de lista vinculada testam sua capacidade de manipular ponteiros sem perder o controle dos nós. As três técnicas que você precisa são:
# Detect a cycle in a linked list (Floyd's Algorithm)
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Pilhas (LIFO) e filas (FIFO) são estruturas mais simples, mas desbloqueiam categorias inteiras de problemas:
# Valid Parentheses — classic stack problem
def is_valid(s: str) -> bool:
stack = []
matching = {')': '(', '}': '{', ']': '['}
for char in s:
if char in matching:
if not stack or stack[-1] != matching[char]:
return False
stack.pop()
else:
stack.append(char)
return len(stack) == 0
Os problemas de árvore normalmente envolvem recursão e uma das três ordens de travessia (em ordem, pré-ordem, pós-ordem). O modelo mental a desenvolver é: "O que preciso da subárvore esquerda, da subárvore direita e como combiná-las no nó atual?"
# Maximum depth of a binary tree — the template for tree recursion
def max_depth(root):
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return 1 + max(left_depth, right_depth)
Os problemas BST (Binary Search Tree) adicionam uma propriedade crucial: a travessia em ordem produz elementos classificados. Se você vir "classificado" e "árvore" no mesmo problema, pense no BST imediatamente.
Os problemas gráficos parecem intimidantes, mas a maioria se reduz a BFS ou DFS depois que você cria a lista de adjacências. As principais habilidades são:
# BFS shortest path in an unweighted graph
from collections import deque
def shortest_path(graph, start, end):
queue = deque([(start, 0)])
visited = {start}
while queue:
node, distance = queue.popleft()
if node == end:
return distance
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append((neighbour, distance + 1))
return -1 # Not reachable
Sempre que um problema diz "encontre o K maior", "K o mais próximo" ou "mescle K listas classificadas", um heap (fila de prioridade) é quase certamente a resposta. Em Python, heapq fornece um heap mínimo; para um heap máximo, negue os valores.
import heapq
# Find the K largest elements in an array
def k_largest(nums, k):
return heapq.nlargest(k, nums) # Uses a min-heap of size k internally
Você precisa encontrar a mediana de um fluxo de números em O(log n) por inserção. Qual combinação de estrutura de dados é mais apropriada?
| Estrutura | Acesso | Pesquisar | Inserir | Excluir | Espaço | |---|---|---|---|---|---| | Matriz | O(1) | Sobre(n) | Sobre(n) | Sobre(n) | Sobre(n) | | Mapa de hash | — | O(1)* | O(1)* | O(1)* | Sobre(n) | | Lista vinculada | Sobre(n) | Sobre(n) | O(1) | O(1) | Sobre(n) | | Pilha/Fila | Sobre(n) | Sobre(n) | O(1) | O(1) | Sobre(n) | | BST (equilibrado) | O(logn) | O(logn) | O(logn) | O(logn) | Sobre(n) | | Pilha | — | Sobre(n) | O(logn) | O(logn) | Sobre(n) |
* Caso médio; o pior caso é O(n) devido a colisões de hash.
Desenvolva esta lista de verificação mental ao ler um problema: