Padrões de algoritmos em C# para entrevistas e maratonas

Cinco padrões que não precisam de memória extra nenhuma — dois inteiros e o array que te deram. Onde cada um se aplica, por que é linear, e a linha do último que todo mundo escreve ao contrário.

Os dois ponteiros andam para o mesmo lado e o espaço entre eles é a resposta. Quatro formatos de janela, mais o truque de contagem que transforma “exatamente K” numa subtração, porque “exatamente K” não dá para deslizar direto.

Pré-calcule uma vez e responda qualquer pergunta sobre um intervalo em tempo constante — e o truque inverso que quase ninguém ensina, que aplica uma atualização a um intervalo inteiro escrevendo duas células.

Encontrar um valor num array ordenado é a coisa menos útil que a busca binária faz. O padrão que importa busca num espaço de respostas que ninguém nunca construiu, e não precisa de array ordenado nenhum.

Uma pilha que se recusa a guardar qualquer coisa inútil responde qual é o próximo elemento maior de um array inteiro em uma passada — e a mesma estrutura mede o maior retângulo de um histograma.

Contar sem fazer dois lookups de hash por item, o tamanho exato de entrada em que Array.Sort para de preservar a ordem, e o heap que C# só ganhou no .NET 6 — que a maioria do código antigo de maratona em C# ainda contorna na mão.

A representação que a maioria das soluções em C# usa é também o motivo de elas estourarem o limite de tempo. Depois, busca em largura, busca em profundidade sem a pilha de chamadas, e a ordenação que detecta um ciclo de graça.

Pesos quebram o BFS. Dijkstra resolve, o PriorityQueue do C# não tem DecreaseKey então você insere duplicatas no lugar, e quando toda aresta é 0 ou 1 o heap acaba sendo puro trabalho a mais.

Não a teoria — as cinco formas que sempre voltam, e a única direção de laço que transforma, em silêncio, uma delas em um problema completamente diferente.

A parte com que você só se importa depois que uma solução correta já estourou o limite de tempo. Ler a entrada sem alocar, o overflow sobre o qual C# não avisa, e por que Console.WriteLine dentro de um laço custa 400,000 escritas.

O C# não traz o tipo de nó que esses problemas assumem, e LinkedList não é ele. Cinco padrões — o meio em uma passada, a detecção de ciclo de Floyd com a prova, a inversão in-place, e o dummy head que apaga seus casos especiais.

Três ordens recursivas que diferem por uma linha, a versão iterativa que ninguém reconstrói sob pressão, e por que o percurso por níveis precisa de uma variável local em vez de esperteza.

Quase todo problema de árvore é uma pergunta só — essa quantidade desce a árvore ou volta por ela? Somas de caminhos, o diâmetro que nunca toca a raiz, ancestrais, e a verificação de BST que todo mundo escreve errado na primeira vez.

A família inteira gira em torno de uma escolha — ordenar pelo início, ou ordenar pelo fim. Mesclar quer uma, o guloso de agendamento quer a outra, e o código fica quase igual nos dois casos.

Um template, cinco problemas. Escolher, explorar, desfazer — e é o passo de desfazer que as pessoas esquecem, porque o código parece pronto sem ele.

XOR para isolar o valor que aparece uma vez, a classe BitOperations que quase nenhum código C# usa, e o deslocamento que silenciosamente não faz nada porque a contagem deu a volta.