Fundamentos de Algoritmos e Estruturas de Dados

Como medir tempo e espaço de um algoritmo sem cronômetro.

A estrutura sequencial base: acesso por índice em O(1).

String é um array de caracteres com duas regras a mais: o elemento não é um byte e você não pode escrever numa posição. É dessa imutabilidade que nasce o O(n²) escondido em qualquer concatenação dentro de um laço.

Subarray, substring, subsequence e subset: quatro palavras parecidas que levam a algoritmos diferentes. Duas perguntas separam todas: os elementos precisam ser contíguos? A ordem importa?

Dois índices caminhando na mesma passada. Em array ordenado, um começa na ponta esquerda e o outro na direita, e eles convergem.

Uma janela contígua que anda pelo array. Fixa, com tamanho travado em k, ou variável, crescendo pela direita e encolhendo pela esquerda enquanto está inválida.

Somas de intervalo em tempo constante depois de um pré-processamento.

Merge, insert e agendamento: ordenar por início e varrer os intervalos.

Busca, inserção e remoção em O(1) amortizado, quase sempre. A chave calcula o próprio endereço, e o preço disso é colisão, fator de carga e rehash.

Nós apontando para nós. Ponteiro rápido e lento, sentinelas e detecção de ciclos.

LIFO: parênteses balanceados e próximo maior elemento (pilha monotônica).

FIFO e a fila de duas pontas para a janela com máximo.

Funções que chamam a si mesmas, sem medo do stack.

Recursão de cauda e o estilo funcional.

Pré, in, pós-ordem e por nível.

Recursão estrutural sobre dois filhos.

Nós com qualquer número de filhos.

Ordem invariante para busca em O(log n).

Árvore de prefixos para busca de strings, autocomplete e dicionários.

Vértices, arestas e representação (matriz / lista de adjacência).

Os dois jeitos de percorrer um grafo.

Caminho mais curto com pesos não-negativos.

Caminho mais curto que aceita pesos negativos.

Pathfinding guiado por heurística.

Menor caminho entre todos os pares de vértices, em O(V³).

Ordem linear de um DAG (Kahn e DFS).

Conectar tudo com o menor custo: Kruskal e Prim.

Componentes fortemente conexos, pontes, pontos de articulação e union-find.

A fila de prioridade por trás do heap sort e do Dijkstra.

Ordenar com um heap em O(n log n).

Corte o espaço de busca pela metade a cada passo: O(log n).

Binary search on answer: achar a fronteira de uma condição monotônica, não um valor.

Bubble, Selection e Insertion Sort, os O(n²) que ensinam a base.

Divisão e conquista, estável, O(n log n).

Particiona em torno de um pivô. O(n log n) na média.

Insertion Sort turbinado com gap sequences.

Ordenação linear por contagem, sem comparações, para inteiros num intervalo.

Ordena dígito a dígito usando counting sort como base.

Distribui em baldes, ordena cada um e concatena.

Tentar, falhar e voltar atrás, busca exaustiva com poda.

Memoização, tabulação e o desafio de enxergar o estado. 1D e multidimensional.

Algoritmos gulosos: quando a escolha local ótima leva à global.

O sistema binário e a conversão entre decimal e binário.

Sign-magnitude, complemento de um e de dois.

AND, OR, XOR, shifts e os truques de bit mais usados em entrevistas.

GCD/LCM, números primos, exponenciação rápida e teoria dos números.