Tema: algorithms
-
Ordem de dependências com travessia de grafos: BFS, DFS e ordenação topológica
Modele dependências como um grafo dirigido, use busca em largura ou em profundidade para encontrar tudo o que uma mudança afeta e aplique o algoritmo de Kahn ou a pós-ordem do DFS para obter uma ordem de build ou de migração que reporta ciclos em vez de escondê-los; graphlib e tsort implementam a ordenação.
-
Tabelas hash na prática: colisões, fator de carga e hashing com semente
Uma tabela hash só é rápida em média enquanto as chaves se distribuem uniformemente pelos buckets; colisões, o fator de carga que dispara o rehash e a semente de hash por processo contra hash flooding determinam o comportamento real. Nunca persista valores de hash nem dependa da ordem de iteração.
-
Programação dinâmica passo a passo: derivando a distância de edição
A programação dinâmica transforma uma definição recursiva com subproblemas sobrepostos em um algoritmo polinomial: defina o estado, escreva a recorrência e os casos-base, aplique memoização ou preencha uma tabela e, por fim, reduza o uso de memória. A distância de edição entre duas strings é derivada por completo como exemplo.
-
Recursão versus iteração: profundidade da pilha, limites e quando converter
A recursão espelha problemas em forma de árvore, mas consome um frame de pilha por nível; a pilha é limitada pelo limite de recursão do interpretador ou pelo tamanho da pilha da thread. Por isso, recursão com profundidade controlada pela entrada é um crash à espera de acontecer. Converta para uma pilha explícita ou um laço quando a profundidade cresce com o tamanho da entrada.
-
Reservoir sampling: uma amostra uniforme de um fluxo de tamanho desconhecido
Mantenha k itens de um fluxo sem conhecer o seu tamanho: preencha o reservatório com os k primeiros e, para o item i, substitua uma posição aleatória com probabilidade k/i. Uma única passagem, memória O(k) e cada item entra na amostra com probabilidade exatamente k/n, como mostra um breve argumento telescópico.
-
Tries para buscas por prefixo: autocompletar e correspondência pelo prefixo mais longo
Uma trie armazena strings com um nó por prefixo comum: a busca custa o tamanho da chave, independentemente de quantas chaves existam, todas as chaves com um prefixo formam uma subárvore e o prefixo armazenado mais longo de uma consulta é encontrado numa única descida. Use-a para autocompletar e roteamento, mas compare antes com um array ordenado.
-
Armadilhas da busca binária: overflow no ponto médio e limites com erro de uma unidade
A busca binária é curta e notoriamente fácil de errar: o ponto médio (low + high) / 2 estoura inteiros de largura fixa, limites inclusivos e exclusivos são misturados e os duplicados levantam a dúvida de qual índice retornar. Use uma biblioteca ou a forma com predicado monótono e intervalos semiabertos, e teste os extremos.
-
Analisar a complexidade antes de otimizar
A complexidade assintótica indica como o tempo de execução cresce com o tamanho da entrada. Identificar no code review loops quadráticos, buscas lineares repetidas e recursão sem limite evita a maioria dos incidentes de desempenho antes mesmo de ser preciso fazer profiling.
-
Token bucket, leaky bucket e janela deslizante: como os algoritmos de rate limiting se diferenciam
A janela fixa é barata, mas deixa passar o dobro do limite na fronteira entre janelas; o log deslizante é exato, mas guarda todos os timestamps; o contador de janela deslizante aproxima o resultado com memória constante; o token bucket permite rajadas até o tamanho do balde a uma taxa fixa de reposição; o leaky bucket suaviza a saída atrasando requisições. O nginx e o Envoy documentam os dois últimos.
-
Filtros de Bloom: pertinência probabilística a conjuntos sem falsos negativos
Um filtro de Bloom responde "definitivamente não está no conjunto" ou "provavelmente está no conjunto" usando um pequeno array de bits e k funções de hash; os falsos positivos são ajustáveis, falsos negativos são impossíveis e não há suporte a remoção. Use-o para evitar consultas por chaves ausentes e sempre verifique um positivo na fonte de verdade.
-
Heurísticas do A*: preserve o significado do custo de movimento
Escolha uma heurística de limite inferior para o grafo de movimento real, trate corretamente as rotas melhoradas e verifique a qualidade do caminho comparando com uma busca não informada.
-
Usar um token bucket para chamadas de ferramentas
Implemente rajadas limitadas com uma equação explícita de reposição de tokens, consumo atômico e um limite separado para requisições em andamento.
-
Estabilidade de ordenação: o que garante e quando importa
Uma ordenação estável preserva a ordem de entrada dos elementos que se comparam como iguais. Python garante isso, o ECMAScript exige desde 2019, e Go e o GNU sort oferecem como opção; é isso que torna previsíveis as ordenações por várias chaves, as tabelas ordenáveis e as consultas paginadas.
Legível por máquina: JSON