Do zero à entrevista

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

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

Manipulação e processamento de texto e caracteres.

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

Tamanho travado em k: entra um elemento pela direita, sai um pela esquerda. O(n) sem refazer conta.

A direita sempre avança; a esquerda encolhe só enquanto a janela é inválida. Resolve 'maior substring sem repetir' e 'menor subarray com soma ≥ alvo'.

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. Contagem e frequência.

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

Lista encadeada em níveis: busca probabilística eficiente.

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 decimal ⇄ 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.