Conteúdo[Esconder][Mostrar]
- 1. Como você define um Array?
- 2. Matrizes dinâmicas: o que são? O que os diferencia dos arrays básicos?
- 3. Como um array e um dicionário variam um do outro?
- 4. Liste algumas das vantagens e desvantagens dos arrays.
- 5. A que se refere “Sparse Array”?
- 6. Quando você escolheria uma lista encadeada em vez de uma matriz?
- 7. O que distingue um array indexado de um array associativo?
- 8. Quais são as vantagens do Heap sobre os arrays ordenados?
- 9. Podemos definir o tamanho do array como negativo?
- 10. Como você localiza o inteiro ausente em uma matriz de 1 a 100 elementos?
- 11. Como você encontra o índice de um elemento em um array?
- 12. Como você pode se livrar de um elemento específico de um array?
- 13. Como verificar a igualdade de dois arrays?
- 14. Quando discutimos arrays, o que você quer dizer com as frases “Dimensão” e “Subscrito”?
- Codificação de perguntas da entrevista
- 15. Procure um par em uma matriz que tenha a soma especificada
- 16. Classificação de matriz binária com tempo linear
- 17. Encontre o maior produto de dois int em uma matriz.
- 18. Como deslocar todos os zeros do array para o final
- 19. Como ordenar um array com duas entradas que são trocadas em uma operação.
- 20. Como combinar dois arrays ordenados no lugar.
- 21. Como reordenar uma série de itens em posições altas e baixas alternadas?
- 22. Como substituir cada elemento de um array sem usar um operador de divisão pelo produto de cada elemento do array?
- 23. Encontre o elemento mais estranho em uma matriz em tempo logarítmico
- 24. Como obter o elemento maior subsequente para cada elemento em uma matriz circular?
- 25. Encontre a contagem de inversão de um array?
- 26. Qual é o problema do aprisionamento da água da chuva?
- Conclusão
As entrevistas de codificação contêm uma série de perguntas de DSA. Você deve ser habilidoso com matrizes se estiver se preparando para sua próxima entrevista de tecnologia com a FAANG ou outra empresa de tecnologia de nível 1.
Na maioria das entrevistas de codificação, vem em segundo lugar para Strings. Uma matriz é um agrupamento de elementos de dados relacionados mantidos próximos uns dos outros na memória.
Como eles estão conectados a todas as linguagens de programação, como C, C++, Java, Python, Perl e Ruby, eles estão em toda parte. Continue lendo para alguns desafios práticos de codificação e entreviste perguntas e respostas com base em matrizes.
O Python será usado neste post para resolver os problemas de codificação porque é simples de usar, compreender e deve ser familiar para a maioria de nós.
Vamos começar.
1. Como você define um Array?
- Um grupo de tipos de dados relacionados é uma matriz.
- Arrays são sempre fixos.
- O mesmo tipo de variável é armazenado em vários lugares por objetos de matriz.
- Tipos primitivos e referências de objetos são compatíveis com ele.
2. Matrizes dinâmicas: o que são? O que os diferencia dos arrays básicos?
O dimensionamento automático que os arrays dinâmicos (também chamados de arrays expansíveis, arrays redimensionáveis, arrays alteráveis ou ArrayLists em Java) fornecem é uma vantagem significativa.
Você deve sempre saber quantos elementos seu array armazenará antecipadamente, pois os arrays têm um tamanho fixo. Um array dinâmico, por outro lado, cresce à medida que você adiciona membros adicionais a ele, então você não precisa saber seu tamanho exato de antemão.
3. Como um array e um dicionário variam um do outro?
Esta é uma matriz baseada em fundamentos de perguntas de entrevista que são feitas regularmente. A seguir estão as principais distinções entre arrays e dicionários:
- Uma matriz é uma lista ordenada de itens semelhantes. O dicionário, por outro lado, tem pares chave-valor.
- Os tamanhos dos arrays podem mudar dinamicamente. Tais idéias dinâmicas não existem em dicionários.
- Antes de utilizar um array, seu tamanho deve ser especificado. Os tamanhos de dicionário não precisam ser personalizados.
- Use a instrução Redim se desejar expandir o tamanho da matriz. Nos dicionários, um elemento pode ser adicionado sem uma declaração.
4. Liste algumas das vantagens e desvantagens dos arrays.
Vantagens:
- As matrizes podem classificar vários elementos simultaneamente.
- Outros estruturas de dados, como pilhas, filas, listas encadeadas, árvores, gráficos, etc., podem ser implementados em um array.
- Um índice pode ser usado para alcançar um elemento de uma matriz.
Desvantagens:
- O tamanho de um array deve ser declarado antecipadamente. No momento da declaração do array, podemos não estar cientes do tamanho que exigimos.
- A estrutura do array é estática. Isso implica que o tamanho do array é sempre fixo e que a alocação de memória não pode ser aumentada ou diminuída.
5. A que se refere “Sparse Array”?
Uma matriz esparsa é uma matriz de dados que possui muitas entradas com valores zero. Em contraste, uma matriz densa contém a maioria de seus itens com valores diferentes de zero. Os índices de uma matriz esparsa, que converte números em objetos, podem incluir lacunas. Comparado a um HashMap, eles são mais eficientes em termos de memória.
6. Quando você escolheria uma lista encadeada em vez de uma matriz?
Ao usar listas vinculadas em vez de matrizes, considere:
- Você não precisa de nenhum elemento para ter acesso aleatório.
- Onde a previsibilidade temporal é essencial, você precisa de inserções e remoções em tempo constante da lista.
- Para criar uma fila de prioridade, talvez seja necessário colocar itens no centro da lista.
- Você não tem idéia de quanto tempo a lista será. Se o tamanho do array aumentar, você deve declarar novamente e duplicar a memória, assim como com arrays simples.
7. O que distingue um array indexado de um array associativo?
As principais distinções entre matrizes associativas e indexadas estão listadas na tabela a seguir.
- Um par chave-valor em formato de texto ou numérico é usado para classificar uma matriz associativa. As chaves do array indexado são todas numéricas e cada chave está conectada a um valor distinto.
- Em uma matriz associativa, a chave pode ser uma string. Array indexado com chaves inteiras começando em 0.
- Uma tabela de duas colunas imita o comportamento de uma matriz associativa. Semelhante a uma tabela de coluna única, são matrizes indexadas.
- Os mapas são um tipo de matriz associativa. Uma matriz de índice não é um mapa.
8. Quais são as vantagens do Heap sobre os arrays ordenados?
A eficiência de tempo de utilização de heap sobre arrays classificados é o principal benefício. Embora as operações de heap sejam mais rápidas, classificar uma matriz requer muito tempo. Um heap pode descobrir o menor elemento consideravelmente mais rapidamente do que um array pode ser classificado.
Uma determinada coleção de números pode ser organizada de duas maneiras usando Sorted Arrays. Por outro lado, para uma determinada coleção de números, pode haver mais de um heap potencial.
9. Podemos definir o tamanho do array como negativo?
Não, não podemos definir um inteiro negativo como o tamanho de um array. Não haverá um erro em tempo de compilação se declararmos. No tempo de execução, no entanto, encontraremos um NegativeArraySizeException.
10. Como você localiza o inteiro ausente em uma matriz de 1 a 100 elementos?
O total da série pode ser calculado aplicando a seguinte função: n (n + 1) / 2
Somente se a matriz não tiver duplicatas ou tiver mais de um inteiro ausente, essa função funcionará. Se uma matriz tem elementos duplicados, você pode classificar a matriz para ver se existem elementos equivalentes.
11. Como você encontra o índice de um elemento em um array?
O índice de um elemento pode ser descoberto por meio de uma pesquisa linear ou binária. Até localizar a correspondência do elemento necessário, uma função de pesquisa linear faz um loop sobre cada elemento em uma matriz. Ele retorna o índice assim que localiza o elemento correspondente. Conseqüentemente, a complexidade temporal da busca linear é O. (n). Tanto uma matriz classificada quanto uma não classificada podem usar a pesquisa linear.
Usando uma pesquisa binária, que divide continuamente a matriz ao meio até que a mediana do intervalo corresponda ao elemento necessário e forneça o índice, você pode obter o índice do elemento se a matriz estiver classificada. Conseqüentemente, a complexidade temporal da busca binária é O. (log n).
12. Como você pode se livrar de um elemento específico de um array?
Como você não pode simplesmente excluir elementos do array original, pois são conjuntos fixos com um tamanho definido, o entrevistador está procurando que você sugira uma abordagem diferente e lide com o problema que a pergunta levanta. O melhor curso de ação é criar um novo array para excluir um elemento. Você pode duplicar os elementos do primeiro array neste array e incluir apenas o elemento que deseja deletar.
Outra estratégia envolve encontrar o elemento de destino na matriz e, em seguida, inverter a ordem de todos os itens que estão à direita do elemento de destino.
13. Como verificar a igualdade de dois arrays?
Você deve primeiro verificar os comprimentos das duas matrizes fornecidas. Os itens correspondentes de ambas as matrizes são comparados quando seus comprimentos são iguais. As duas matrizes serão consideradas iguais. se cada par de componentes em cada correspondência for igual. Essa abordagem não é recomendada para verificar a igualdade de dois arrays se os arrays forem grandes, pois levará muito tempo. Você também pode usar o método equals() incluído na classe Arrays, no entanto, se o entrevistador solicitar que você compare dois arrays sem utilizar métodos internos, dessa forma será útil.
14. Quando discutimos arrays, o que você quer dizer com as frases “Dimensão” e “Subscrito”?
A “Dimensão” de um array é o número de índices, ou subscritos, necessários para identificar cada membro individual. Subscritos e dimensões podem não estar claros. Uma dimensão é uma descrição do intervalo de chaves permitidas, enquanto um subscrito é um número. Há apenas um subscrito necessário para cada dimensão da matriz.
Por exemplo, o array arr[10][5] tem duas dimensões. Tamanhos 10 em um e 5 no outro. Para endereçar seus componentes, você precisa de dois subscritos. Ambos estão entre 0 e 4; um entre 0 e 9, inclusive.
Codificação de perguntas da entrevista
15. Procure um par em uma matriz que tenha a soma especificada
Por exemplo,
Entrada:
- números = [8, 7, 2, 5, 3, 1]
- alvo = 10
Saída:
- Par encontrado (8, 2)
- Or
- Par encontrado (7, 3)
Entrada:
- números = [5, 2, 6, 8, 1, 9]
- alvo = 12
Saída:
- Par não encontrado
16. Classificação de matriz binária com tempo linear
Ordena uma matriz binária em tempo linear e em uma área fixa. A saída deve exibir todos os zeros primeiro, depois todos os uns.
Por exemplo,
- Entrada: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Saída: { 0, 0, 0, 0, 1, 1, 1, 1 }
Uma abordagem direta seria calcular o número total de 0s do array, digamos k, e então preencher os primeiros k índices do array com 0s e os índices restantes com 1. Como alternativa, podemos calcular quantos 1s são totais no array array k, preencha os últimos k índices no array com 1 e deixe o resto dos índices preenchidos com 0.
A abordagem dada tem uma complexidade de tempo O(n) e não usa armazenamento adicional, onde n é o tamanho da entrada.
17. Encontre o maior produto de dois int em uma matriz.
Encontre o maior produto de dois números em uma matriz de inteiros.
Pense na matriz 10 3 5 6 2 como exemplo. O par (-10, -3) ou (5, 6) é o produto mais alto.
Pensar em cada combinação de elementos e descobrir seu produto é uma abordagem tola. Se o produto do par atual for maior que o produto máximo obtido até o momento, atualize o produto máximo. Imprima os componentes do produto final por último.
A solução acima, onde n é a quantidade de entrada, tem uma complexidade de tempo O(n2) e não ocupa mais espaço.
18. Como deslocar todos os zeros do array para o final
Mova todos os zeros em uma matriz de inteiros para o final. A resposta deve evitar o uso de espaço constante e preservar a ordem relativa dos componentes do array.
Entrada: {1,2,3,0,8,0,4,7}
A saída será {1,2,3,8,4,7,0,0}
Coloque o elemento na seguinte posição disponível na matriz se o elemento atual não for zero. Preencha todos os índices restantes com 0 assim que todos os itens do array tiverem sido processados.
A solução anterior tem uma complexidade de tempo O(n), onde n é o tamanho da entrada.
19. Como ordenar um array com duas entradas que são trocadas em uma operação.
Classifique um array no tempo linear dado dois itens trocados e um array com todos os seus elementos organizados em ordem crescente. Finja que a matriz não contém duplicatas.
Entrada:= [1,9,3,4,7,2] ou [9,3,7,2,1,4] ou [2,4,1,7,3,9]
Saída: = [1,2,3,4,7,9]
Começando com o segundo elemento na matriz, o objetivo é comparar cada elemento com seu predecessor. A posição da disputa é armazenada tomando dois ponteiros, x e y.
Atualize x para o índice do elemento anterior e y para o índice do elemento atual se o primeiro for maior que o último. Atualize y para o índice do elemento atual se o elemento anterior for maior que o elemento atual.
Finalmente, troque os elementos nos índices x e y assim que terminarmos de processar cada par de elementos adjacentes.
Devido ao fato de que o método supracitado realiza apenas uma única varredura do array de entrada de tamanho n, sua complexidade de tempo é O(n). Nenhum espaço adicional é necessário para a solução.
20. Como combinar dois arrays ordenados no lugar.
Mescle os itens dos arrays X[] e Y[] — dois arrays ordenados de tamanho m e n cada — mantendo a ordem de ordenação, ou seja, preenchendo X[] com os primeiros m menores elementos e preenchendo Y[] com o elementos restantes.
Se um elemento do array X[] já estiver na posição correta (ou seja, aquele que for o menor entre os elementos restantes), desconsidere-o; caso contrário, substitua-o pelo menor elemento, que também é o primeiro membro de Y[]. Para manter a ordem de classificação após a troca, transfira o elemento (agora em Y[0]) para seu local apropriado em Y[].
O tamanho do primeiro array é m e o tamanho do segundo array é n, e a complexidade de tempo é O(mn).
21. Como reordenar uma série de itens em posições altas e baixas alternadas?
Reorganize uma matriz de inteiros para que cada membro subsequente seja maior que os elementos anteriores e seguintes. Suponha que a matriz não inclua nenhum elemento duplicado.
Classificar a matriz ou utilizar espaço adicional não é necessário para uma abordagem eficaz. O plano é, para começar, o segundo membro da matriz e aumentar em dois para cada iteração de loop.
Troque os componentes se o último elemento exceder o primeiro. Da mesma forma, troque os dois itens se o elemento a seguir for maior que o elemento atual. Obteremos a matriz desejada que atende às restrições especificadas na conclusão do loop.
22. Como substituir cada elemento de um array sem usar um operador de divisão pelo produto de cada elemento do array?
Sem usar o operador de divisão, substitua cada elemento em uma matriz de inteiros pelo produto de todos os outros elementos.
Em tempo linear e espaço constante, podemos utilizar a recursão para resolver esse problema. Calcular recursivamente os produtos de cada elemento no subarranjo direito e passar o produto do subarranjo esquerdo como parâmetros de função é a noção.
A complexidade de tempo é O(n).
23. Encontre o elemento mais estranho em uma matriz em tempo logarítmico
Dada uma matriz de inteiros na qual todos, exceto um membro, têm números pares de ocorrências, o problema é determinar quantas vezes esse elemento aparece. Encontre o elemento de ocorrência ímpar em tempo logarítmico e espaço constante se os mesmos elementos ocorrem em pares na matriz e nunca pode haver mais de duas instâncias de um determinado elemento em uma linha.
A operação XOR nos permite resolver esse problema em tempo linear. O objetivo é fazer o XOR de cada elemento na matriz. Apenas os elementos de ocorrência ímpar permanecem depois que os elementos de ocorrência par se cancelam.
Este problema pode até ser resolvido em tempo O(log(n)).
24. Como obter o elemento maior subsequente para cada elemento em uma matriz circular?
O próximo elemento maior para cada elemento em uma matriz circular inteira deve ser localizado. O primeiro inteiro maior após um elemento x na matriz é o elemento maior subsequente desse elemento.
Da direita para a esquerda, podemos operar em itens de array. O objetivo é fazer um loop para cada elemento x até que a pilha esteja vazia ou tenhamos um elemento mais alto em cima dela. Defina o próximo elemento maior de x para aparecer no topo da pilha quando isso acontecer.
25. Encontre a contagem de inversão de um array?
Encontre o número total de inversões de uma matriz. Um par I j) é referido como uma inversão de um array A se I j) e (A[i] > A[j]). Devemos contar cada par destes na matriz.
Contar todos os membros da matriz que são menores que ele à direita e adicionar o resultado à saída é uma abordagem direta.
Esta solução tem complexidade O(n2), onde n é o tamanho da entrada.
26. Qual é o problema do aprisionamento da água da chuva?
Encontrar a maior quantidade de água que pode ser retida em um determinado conjunto de barras com largura de uma unidade cada é conhecido como o problema de “retenção de chuva”.
O objetivo é determinar a barra mais alta que pode ser colocada à esquerda e à direita de cada barra. O mínimo das barras à esquerda e à direita, menos a altura da barra atual, é a quantidade de água que é armazenada no topo de cada barra.
Conclusão
Em comparação com outros tópicos de estrutura de dados, os arrays são mais simples. Para responder às perguntas da entrevista de matrizes, você precisa ter uma compreensão fundamental das matrizes.
Você deve revisar extensivamente os fundamentos de arrays, incluindo operações de array (de declarar/criar um array para acessar/modificar itens de array), bem como conceitos de programação como loops, recursão e operadores básicos para responder com sucesso a perguntas de entrevista de array. Reconheça o problema completamente.
Você deve buscar esclarecimentos se tiver alguma dúvida. Pense em dividir o problema em partes mais gerenciáveis. Certifique-se de ter o algoritmo em mente antes de começar a programar; anote-o ou visualize-o em um fluxograma. então comece a escrever o código.
Deixe um comentário