Carreira

100+ desafios de programação que aparecem em entrevistas de emprego [com solução]

{{post.author.node.name}}

Por: Larissa Fereguetti | Em: | Atualizado: 7 meses atrás | 14 min de leitura

Compartilhe »

Muitas entrevistas de emprego relacionadas a programação (como para cargos de engenharia da computação/software, desenvolvedores e outros) são compostas não só por aquela tradicional entrevista de perguntas e respostas, mas também por desafios ligados ao cargo.

tela de computador com linhas de programação
Imagem: techsors.com

Para ajudar nesse processo, um perfil no GitHub está construindo um banco de dados com os problemas que aparecem com maior frequência. Esse perfil não só lista mais de 100 problemas, como também coloca exemplos, abordagem, solução e o custo computacional de cada um.

Abaixo, nós separamos uma lista traduzida com os links para cada problema e solução dados. Basta clicar no nome do problema e você será redirecionado para a página com os códigos e a explicação.

Problemas de programação:

Manipulação de matrizes e strings:
Misturar horários de reuniões: Dada uma lista de reuniões independentes e não classificadas, retorna uma lista de reuniões mescladas.
Inverter uma lista de string: Dada uma lista de strings, inverta sua ordem.
Inverter palavras: Dada uma lista de strings que são compostas por palavras, mas ao contrário, retorne a ordem correta.
Mesclar matrizes ordenadas: mescle duas matrizes ordenadas.

Tabelas hash:
Entretenimento em voo: Dada uma lista de tamanhos de filme (número inteiro) e uma duração de voo (número inteiro), determine se existem dois filmes que somam a duração total. Suponha que um usuário assista exatamente dois filmes, mas não o mesmo duas vezes.
Permutação de palíndromo: Dada uma string, verifique se sua permutação é um palíndromo.
Nuvem de palavras: Dada uma frase (string), retorne seu mapa de contagem de palavras.
Melhores pontuações: Dada uma lista de pontuações não ordenadas (número inteiro) e a pontuação mais alta possível (número inteiro), retorne uma lista classificada.

Algoritmos gulosos:
Ações da Apple: Dada uma lista de preços das ações (inteiro) em ordem cronológica, retorne o lucro máximo comprando mais cedo e vendendo mais tarde.
Maior produto de três: Dada uma lista de números inteiros, retorne o produto mais alto de três números.
Produto de todos os outros números: Dada uma lista de números inteiros, retorne uma lista correspondente em que cada índice contém o produto de todos os outros valores, exceto o valor nesse índice. E você não pode usar a divisão.
Aleatório local: Dada uma lista de números inteiros, embaralhe sua localização.
Classificação, pesquisa e logaritmos:
Encontrar o rotation point: dada uma lista de palavras, retorne um índice de um rotation point.

Árvores e grafos:
Árvore binária balanceada: Dada uma árvore binária, determine se ela está "superbalanceada" - a diferença entre as profundidades de quaisquer dois nós de folhas não é maior que 1.
Verificador de árvore de pesquisa binária: Dada uma árvore binária, determine se é uma árvore de pesquisa binária.
Segundo maior item em uma árvore de pesquisa binária: Dada uma árvore de pesquisa binária, encontre o segundo maior item.
Coloração de grafo: Dado um grafo não direcionado, com o grau máximo d, encontre uma coloração de grafo usando no máximo d + 1 cores. Suponha que não haja nó com um loop.

Programação dinâmica e recursividade:
Permutação recursiva de sequências: Escreva uma função recursiva para gerar todas as permutações de uma sequência de entrada. Suponha que cada caractere na sequência seja único.
Computar o enésimo número da sequência de Fibonacci: Dado um número inteiro n, escreva uma função para retornar o enésimo número de Fibonacci. Suponha que n é um número inteiro positivo.
Fazendo trocas: Dada uma quantidade de dinheiro e uma lista de denominações de moedas, calcule o número de maneiras de fazer esse valor com essas moedas disponíveis.

Filas e pilhas:
Maior pilha: Implemente uma pilha com um método getMax () que retorne o maior elemento da pilha com custo O(1).
Uma fila com duas pilhas: Implemente uma fila com 2 pilhas.
Correspondência entre parêntesis: Dada uma frase como string, e a posição de uma posição de parêntese de abertura, encontre a posição de fechamento correspondente.
Validador de colchetes: Dada uma sequência, determine se seus colchetes estão aninhados corretamente.

Listas vinculadas:
Excluir nó: Exclua um nó de uma lista vinculada individualmente, dado apenas um ponteiro para esse nó.
Lista vinculada tem um ciclo: Determine se uma lista vinculada individualmente possui um ciclo.
Inverter uma lista vinculada: Inverta uma lista vinculada.
Do k-ésimo ao último nó: Encontre do k-ésimo ao último nó em uma lista vinculada.

Manipulação de bits:
Lista de inteiros: Dada uma lista de números inteiros onde cada elemento aparece um número par de vezes, exceto um, encontre esse elemento com custo O (1).
Matriz/Sequência
Soma I: Dada uma matriz de números inteiros, retorne índices dos dois números, de forma que eles sejam adicionados a um destino específico. Você pode assumir que cada entrada teria exatamente uma solução e não poderá usar o mesmo elemento duas vezes.
Soma II: Dada uma matriz ordenada de números inteiros, retorne índices dos dois números, de forma que eles sejam adicionados a um destino específico.
Palíndromo válido: Dada uma sequência, determine se é um palíndromo, considerando apenas caracteres alfanuméricos.
Implementando strstr(): Implemente strstr () que encontra a primeira ocorrência da agulha de substring no palheiro de strings. Retorna -1 se a agulha não faz parte do palheiro.
Inverter palavras na sequência: Dada uma string, inverta-a palavra por palavra.
Subsequência mais longa sem caracteres repetidos: Dada uma sequência, encontre o comprimento da substring mais longa sem repetir caracteres.
Intervalos ausentes: Dada uma matriz inteira classificada em que o intervalo de elementos é [0, 99] inclusive, retorne os intervalos ausentes.
Distância entre sequências: Dadas duas sequências de caracteres, determine se ambas estão a uma mesma distância de edição.
Matemática:
Inverter número inteiro: Dado um número inteiro de 64 bits, inverta seus dígitos.
Somar um: Dado um número representado como uma matriz de dígitos, some um ao número.
Número palíndromo: Determine se um número inteiro é um palíndromo.

Lista vinculada:
Mesclar lista vinculada: Mesclar duas listas vinculadas classificadas e retornar como uma nova lista.
Adicionar dois números: Dadas duas listas vinculadas que representam dois números não negativos, adicione-as e retorne-as como uma lista vinculada.
Trocar nós em pares: Dada uma lista vinculada, troque a cada dois nós adjacentes e retorne o head.

Árvore binária:
Validar árvore de pesquisa binária: Dada uma árvore binária, determine se é uma árvore de pesquisa binária válida.
Profundidade máxima da árvore binária: Dada uma árvore binária, encontre sua profundidade máxima.
Profundidade mínima da árvore binária: Dada uma árvore binária, encontre sua profundidade mínima.
Árvore binária balanceada: Dada uma árvore binária, determine se ela está balanceada.
Soma do caminho da árvore binária: Dada uma árvore binária, encontre a soma do maior caminho.

Manipulação de bits :
Número único I: Dada uma lista de números inteiros onde cada elemento aparece um número par de vezes, exceto um, encontre esse elemento com o custo O (1).
Número único II: Dada uma lista de números inteiros onde cada elemento aparece três vezes, exceto um, encontre esse elemento com custo O (1).
Diversos:
Matriz espiral: Dada uma matriz de m linhas x n colunas, retorne todos os elementos da matriz em ordem espiral.
Pilha:
Pilha mínima: Crie uma pilha que suporte push, pop, top e recuperação do elemento mínimo em tempo constante.
Parêntesis válidos: Dada uma lista de parênteses, determine se ela é válida.

Programação dinâmica:
Subindo escadas: Você está subindo uma escada. São necessários n passos para chegar ao topo. Cada vez você pode subir 1 ou 2 passos. De quantas maneiras distintas você pode subir ao topo?

Bit manipulation:
Operação de bits: Implemente algumas operações bit a bit comuns.
Inserção de bits: Dado dois números, m e n, e a posição de dois bits, i e j, insira m em n de modo que m comece no bit j e termine no bit i.

Matrizes e sequências:
Média de qualquer sub-matriz contígua de tamanho k: Dada uma matriz, encontre a média de todas as sub-matrizes contíguas de tamanho k.
Soma máxima de qualquer sub-matriz contígua de tamanho k: Dada uma matriz de números positivos e um número positivo k, encontre a soma máxima de qualquer sub-matriz contígua de tamanho k.
Submatriz menor com uma determinada soma: Dada uma matriz de números positivos e um número positivo s, encontre o comprimento do menor sub-arranjo contíguo cuja soma seja maior ou igual a s.
Subsequência mais longa com k caracteres distintos: Dada uma sequência, encontre o comprimento da substring mais longa, com no máximo k caracteres distintos.
Frutas em cestos: Dada uma variedade de caracteres em que cada personagem representa uma árvore frutífera, você recebe duas cestas e seu objetivo é colocar o número máximo de frutas em cada cesta.
Subsequência mais longa sem caracteres repetidos: Dada uma sequência, encontre o comprimento da substring mais longa que não possui caracteres repetidos.
Subsequência mais longa após k substituições: Dada uma sequência, se você tiver permissão para substituir no máximo k letras por qualquer letra, encontre o comprimento da substring mais longa com as mesmas letras após a substituição.
Maior subsequência após a substitução: Dada uma matriz contendo 0s e 1s, se você tiver permissão para substituir não mais que k 0s por 1s, encontre o comprimento do subarray contíguo mais longo com todos os 1s.
Permutação em sequência: Dada uma sequência e um padrão, descubra se a sequência contém alguma permutação do padrão.
Anagramas em sequências: Dada uma sequência e um padrão, encontre todos os anagramas do padrão na sequência especificada. Devolva-os como uma lista dos índices iniciais dos anagramas.

Dois ponteiros:
Emparelhar com soma alvo: Dada uma matriz de números classificados e uma soma de destino, encontre um par na matriz cuja soma seja igual ao destino especificado.
Remover duplicatas: Dada uma matriz, remova as duplicatas.
Quadrado de uma matriz: Dada uma matriz classificada, crie uma nova matriz contendo quadrados de todo o número da matriz de entrada na ordem classificada.
Problema da bandeira da Holanda: Dada uma matriz contendo 0s (vermelho), 1s (azul) e 2s (branco), classifique a matriz de acordo com as cores da bandeira nacional da Holanda.

Ponteiros rápidos e lentos:
Ciclo da lista vinculada: Dado o cabeçalho de uma lista vinculada individualmente, escreva uma função para determinar se ela contém um ciclo.
Início de um ciclo de lista vinculada: Dado o cabeçalho de uma lista isolada, escreva uma função para encontrar o nó inicial do ciclo.
Número feliz: Escreva um algoritmo para determinar se um número está feliz. Qualquer número será chamado de número feliz se, depois de substituí-lo repetidamente por um número igual à soma do quadrado de todos os seus dígitos, nos levar a 1.
Meio de uma lista vinculada: Dado o cabeçalho de uma lista vinculada individualmente, escreva uma função para retornar o valor do meio.
Lista vinculada do palíndromo: Dado o cabeçalho de uma lista isolada, escreva uma função para determinar se é um palíndromo.
Reordenar uma lista vinculada: Dado o cabeçalho de uma lista isolada, escreva uma função para reordená-la, de forma que os nós da segunda metade sejam inseridos alternadamente aos nós da primeira metade na ordem inversa.

Intervalos mesclados:
Mesclar intervalos: Dada uma lista de intervalos, mescle todos os intervalos sobrepostos para produzir uma lista que tenha apenas intervalos mutuamente exclusivos.
Inserir intervalos: Dada uma lista de intervalos sem sobreposição classificados pela hora de início, insira um determinado intervalo na posição correta e mescle todos os intervalos necessários para produzir uma lista que tenha apenas intervalos mutuamente exclusivos.
Interseção de intervalos: Dadas duas listas ordenadas de intervalos, encontre a interseção entre eles.
Conflito de compromissos: Dada uma lista de intervalos, verifique se algum deles está em conflito.

Ordenação cíclica:
Ordenação cíclica: Dada uma matriz que contém n objetos em que cada objeto, quando criado, recebeu um número exclusivo de 1 a n com base em sua sequência de criação. Isso significa que o objeto com o número de sequência 3 foi criado logo antes do objeto com o número de sequência 4. Escreva uma função para classificar os objetos no número de sequência de criação com custo O (n) e sem espaço extra.
Números ausentes: Dado um array contendo n números retirados do intervalo de 1 a n. Pode ter duplicatas. Encontre todos os números ausentes.
Número ausente: Dada uma matriz que contém n números distintos retirados do intervalo de 0 a n. Como a matriz possui apenas n números do total de n + 1, encontre o número ausente.
Encontrar duplicata: Dada uma matriz que contém n + 1 números retirados do intervalo de 1 a n. Ele possui apenas um número duplicado, mas pode ser repetido ao longo do tempo. Encontre-o.
Encontrar duplicatas: Dado um array contendo n números retirados do intervalo de 1 a n. Pode ter algumas duplicatas. Encontre-as.
Encontrar par corrompido: Dada uma matriz que contém n + 1 números retirados do intervalo de 1 a n. Um dos números foi duplicado, o que também resultou na perda de um número. Encontre esses números.

Reverter lista vinculada:
Reverter lista: Dado o cabeçalho de uma lista vinculada individualmente, escreva uma função para retornar o novo cabeçalho da lista vinculada revertida.

Pesquisa em árvores:
Caminhar na árvore binária: Dada uma árvore binária, preencha os valores de todos os nós de cada nível da esquerda para a direita em sub-matrizes separadas.
Caminhar de forma reversa: Dada uma árvore binária, preencha os valores de todos os nós de cada nível na ordem inversa em sub-matrizes separadas.
Travessia em zigzag: Dada uma árvore binária, preencha os valores de todos os nós de cada nível em uma ordem em zigue-zague em sub-matrizes separadas.
Médias de nível: Dada uma árvore binária, preencha uma matriz para representar as médias de todos os seus níveis.
Profundidade mínima: Dada uma árvore binária, encontre a profundidade mínima, também conhecida como número de nós, no caminho mais curto, do nó raiz ao nó folha mais próximo.
Profundidade máxima: Dada uma árvore binária, encontre a profundidade máxima.
Sucessor da ordem de nível: Dada uma árvore binária e um nó, encontre o sucessor da ordem de nível do nó especificado. O sucessor da ordem de nível é o nó que aparece logo após o nó especificado no percurso da ordem de nível.

Profundidade da árvore em primeira busca:
Soma do caminho da árvore binária: Dada uma árvore binária e uma soma, descubra se a árvore possui um caminho da raiz para a folha, de modo que a soma de todos os valores de nó desse caminho seja igual à soma.
Soma do número dos caminhos: Dada uma árvore binária em que cada nó pode ter apenas um valor de dígito (0-9), cada caminho raiz-a-folha representará um número. Encontre a soma total de todos os números representados por todos os caminhos.

Árvores:
Árvore binária balanceada: Determine se uma árvore binária é equilibrada em altura.
Caminhos de árvores bináriasinary tree traversals: Implemente a pesquisa em profundidade da árvore binária na primeira ordem (ordem de entrada, pré-ordem, pós-ordem) e na primeira pesquisa por ordem de nível.

Ordenação:
Bubble sort: implemente o método bubble sort.
Seleção: implemente o método de seleção.
Inserção: implemente o método de inserção.
Merge Sort: implemente o método merge sort.
Quicksort: implemente o método quicksort.
Heapsort: implemente o método heapsort.
Counting Sort: implemente o método counting sort.

LEIA O PRÓXIMO ARTIGO