As 30 principais perguntas e respostas da entrevista sobre estruturas de dados e algoritmos [para calouros e experientes]

Estruturas de Dados e Algoritmos estão entre os assuntos mais importantes no mundo da Ciência da Computação e Engenharia. Se você aparecer para uma entrevista de engenharia de software, pode ter certeza de enfrentar uma rodada de perguntas especialmente dedicadas a Estruturas de Dados e Algoritmos – é por isso que eles são cruciais!

Os algoritmos estão no centro de tudo o que acontece em ciência da computação e ciência de dados. De Machine Learning a IA e Blockchain – todas as tecnologias são executadas em algoritmos. E os algoritmos precisam de estruturas de dados para funcionar. Assim, o conhecimento combinado de Estruturas de Dados e Algoritmos pode ajudá-lo a se destacar da multidão durante sua entrevista.

No entanto, o desafio é que o DSA é um domínio extenso. Aqui, o aprendizado nunca para e sempre há algum novo desenvolvimento que você precisa entender. Embora o aprimoramento contínuo seja obrigatório ao lidar com estruturas de dados e algoritmos, hoje veremos alguns fundamentos de DSA que ajudarão você a se sair bem em entrevistas técnicas.

Principais Perguntas e Respostas sobre Estruturas de Dados e Algoritmos

1. O que você entende sobre 'Estruturas de Dados'?

Estruturas de dados podem ser definidas como técnicas usadas para definir, armazenar e acessar dados sistematicamente. Eles formam o componente mais importante de qualquer algoritmo. Dependendo do tipo de Estruturas de Dados, elas armazenam diferentes tipos de dados e são acessíveis de diferentes maneiras. Para que um algoritmo retorne um resultado, ele precisa operar e manipular um conjunto de estruturas de dados de forma organizada e eficiente para chegar ao resultado final.

2. Como você pode diferenciar entre uma estrutura de arquivos e uma estrutura de dados?

Em Estruturas de Arquivos, os dados são armazenados em discos seguindo as políticas de armazenamento de arquivos padrão e não são compatíveis com aplicativos externos de terceiros. Em Estruturas de Dados, por outro lado, os dados são armazenados tanto no disco quanto na RAM em políticas de armazenamento personalizadas, e estas são altamente compatíveis com aplicativos externos.

3. Quais são os tipos gerais de estruturas de dados?

Estruturas de dados podem ser divididas em duas categorias:

• Linear: Neste, todos os elementos são armazenados sequencialmente, e a recuperação ocorre de forma linear. O arranjo não é hierárquico e cada elemento tem um sucessor e um predecessor. Exemplo – Arrays, Listas Ligadas, Pilhas, Filas, etc.
• Não-linear: Aqui, o armazenamento não ocorre em uma sequência linear – ou seja, nem todos os elementos têm necessariamente apenas um sucessor e um predecessor. Em vez disso, os elementos em estruturas de dados não lineares são conectados a dois ou mais itens de maneira não linear. Exemplo – Árvores, Gráficos, Heaps.

4. Quais são algumas das principais áreas de uso das Estruturas de Dados?

Estruturas de dados são praticamente necessárias em todos os campos da computação que você possa imaginar, especialmente algoritmos e otimização de algoritmos. Aqui estão algumas outras áreas onde as Estruturas de Dados são amplamente utilizadas:

• Projeto do sistema operacional
• Análise numérica
• Aprendizado de máquina e IA
• Projeto e desenvolvimento de compiladores
• Gerenciamento de banco de dados
• Análise léxica
• Programação gráfica
• Algoritmos de pesquisa e classificação e muito mais.

5. Explique a estrutura de dados da pilha e mencione suas áreas de uso.

Stack é simplesmente uma lista ordenada que permite a inserção e exclusão apenas de uma das extremidades – que é conhecida como 'top'. É uma estrutura de dados recursiva que possui um ponteiro para seus elementos 'top' que nos permite saber sobre o elemento mais alto da pilha. Com base na estratégia de recuperação de elementos, o Stack também é conhecido como Last-In-First-Out, pois o último elemento inserido na pilha estará no topo e será o primeiro a ser retirado. Aqui estão alguns usos da Stack Data Structure:

• Retrocedendo
• Gerenciamento de memória
• Retorno e chamada de função
• Avaliação de expressão

6. Quais são as operações que podem ser executadas em uma pilha?

A Stack Data Structure suporta as três operações a seguir:

• push() — para inserir um elemento na posição superior da pilha.
• pop() — para trazer um elemento do topo da pilha.
• peek() — para apenas verificar o elemento presente no topo da pilha sem tirá-lo da pilha.

7. O que você entende sobre Expressões Postfix?

Postfix Expression é uma expressão onde os operadores seguem os operandos. Isso é extremamente benéfico em termos de computação, pois não requer nenhum agrupamento de subexpressões entre parênteses ou mesmo considerar a precedência do operador. A expressão a+b é simplesmente representada como ab+ em postfix.

8. Como os elementos de array 2D são armazenados na memória?

Os elementos de uma matriz 2-D podem ser armazenados na memória de duas maneiras:

• Row-Major: Neste método, primeiro todas as linhas do array são armazenadas de forma contígua na memória. Primeiro, a 1ª linha é armazenada completamente, depois a 2ª linha e assim por diante até a última.
• Column-Major: Neste, todas as colunas do array são armazenadas continuamente na memória. Primeiro, a 1ª coluna é armazenada completamente, depois a 2ª coluna e assim por diante.

9. Definir estrutura de dados de lista vinculada.

Listas vinculadas são coleções de nós – que são objetos armazenados aleatoriamente. Cada nó tem dois elementos internos – um campo de dados e um campo de link. O campo Data contém o valor que o determinado nó possui, enquanto o campo Link possui um ponteiro para o próximo nó ao qual este está vinculado. Dependendo da situação, uma Linked List pode ser considerada tanto como uma estrutura de dados linear quanto não linear.

10. De que forma as listas vinculadas são melhores que os arrays?

Listas vinculadas são melhores que matrizes das seguintes maneiras:

• Os tamanhos dos arrays são fixos em tempo de execução e não podem ser modificados posteriormente, mas as Listas Vinculadas podem ser expandidas em tempo real, conforme os requisitos.
• As listas vinculadas não são armazenadas de forma contígua na memória, como resultado, elas são muito mais eficientes em termos de memória do que matrizes que são armazenadas estaticamente.
• O número de elementos que podem ser armazenados em qualquer Linked List é limitado apenas ao espaço de memória disponível, enquanto o número de elementos é limitado pelo tamanho do array.

11. Na linguagem de programação C, qual ponteiro você usaria para implementar uma lista vinculada heterogênea?

Listas vinculadas heterogêneas, como o nome sugere, contêm diferentes tipos de dados. Como resultado, não é possível usar ponteiros comuns aqui. Assim, os ponteiros Void são normalmente usados ​​em tal cenário, pois são capazes de apontar para qualquer tipo de valor.

12. O que é uma lista duplamente ligada?

Como o nome sugere, uma lista duplamente vinculada é uma lista vinculada que possui nós vinculados aos nós seguintes e anteriores. Como resultado, os nós da Lista Duplamente Ligada têm três, não dois campos:

• O campo de dados
• Próximo ponteiro (para apontar o próximo nó)
• Ponteiro anterior (para apontar o nó anterior)

13. Explique a Estrutura de Dados da Fila com algumas de suas aplicações.

Uma Fila é uma lista ordenada que permite a inserção e exclusão de elementos não de uma, mas de duas extremidades – chamadas REAR e FRONT. A inserção ocorre a partir da extremidade FRONT enquanto a exclusão da extremidade REAR. Como resultado disso, a fila é frequentemente chamada de primeiro a entrar, primeiro a sair (FIFO). Aqui estão algumas aplicações generalizadas de filas como uma estrutura de dados:

• Para listas de espera para recursos compartilhados individualmente, como CPU, impressora, disco etc.
• Para transferência assíncrona de dados, arquivo de exemplo IO, sockets, pipes.
• Como buffers na maioria dos aplicativos de media player.
• Em sistemas operacionais para tratamento de interrupções.

14. Você pode listar algumas desvantagens de implementar filas usando arrays?

Existem principalmente duas desvantagens que ocorrem ao implementar filas com arrays:

• Má gestão de memória, uma vez que os arrays são estruturas de dados estáticas, então implementar Queues com arrays remove muitas funcionalidades do Queues.
• Problema com o tamanho, pois os tamanhos dos arrays são definidos durante a definição do array. Então, se quisermos adicionar mais elementos à nossa fila do que o tamanho do array, não será possível.

15. Quais condições devem ser atendidas para que um elemento seja inserido em uma fila circular?

Aqui estão algumas condições relevantes para a inserção em filas circulares:

• Se (rear + 1)%maxsize == front -> isso significa que a fila está cheia -> não há mais inserção possível.
• Se rear != max – 1, o valor de rear é incrementado para maxsize e um novo valor será inserido na extremidade traseira.
• Se front != 0 e traseiro == max -1 –> isso significa que a fila não está cheia. Assim, o valor de retaguarda é definido como 0 e um novo elemento é inserido na extremidade traseira da fila circular.

16. O que é um desenfileiramento?

Double-Ended Queue ou deque é um conjunto ordenado de elementos que facilita a inserção e exclusão de ambas as extremidades - traseira e frontal. Como resultado, isso é ainda mais flexível do que a estrutura de dados da fila.

17. Defina a Estrutura de Dados da Árvore e liste alguns tipos de árvores.

Árvore é uma estrutura de dados recursiva não linear que contém vários nós. Um nó específico é designado como a raiz da árvore de onde todos os outros nós emergem. Além da raiz, todos os outros nós são chamados de nós filhos. Existem basicamente os seguintes tipos de Estruturas de Dados em Árvore:

• Árvores Gerais
• Árvores Binárias
• Árvores de pesquisa binária
• Florestas
• Árvore de Expressão
• Árvore do Torneio

18. Como funciona a classificação de bolhas?

Bubble Sort é um dos algoritmos de ordenação mais usados, e é usado com arrays comparando elementos adjacentes e trocando suas posições com base em seus valores. É chamado de classificação de bolhas porque a visualização de como funciona é como bolhas flutuando do topo da água e entidades maiores afundando.

Leia: Estruturas de dados em C e como usar?

19. Qual é o algoritmo de ordenação mais rápido disponível?

Existem muitos algoritmos de classificação diferentes disponíveis, como classificação por mesclagem, classificação rápida, classificação por bolhas e muito mais. Desses, não podemos escolher um algoritmo específico que seja objetivamente o mais rápido, pois seu desempenho varia muito com base nos dados de entrada, na reação após o algoritmo ter processado os dados e em como eles são armazenados.

20. O que são Árvores Binárias?

Árvores Binárias são tipos especiais de árvores em que cada nó pode ter NO MÁXIMO dois filhos. Para facilitar as coisas, as Árvores Binárias são geralmente divididas em três conjuntos disjuntos - nó raiz, subárvore direita e subárvore esquerda.

21. Como as árvores AVL podem ser usadas em várias operações em comparação com o BST?

As árvores AVL são árvores com altura equilibrada, portanto, não permitem que a árvore fique inclinada de um lado. O tempo gasto para todas as operações realizadas no BST de altura h é O(h). No entanto, isso pode continuar sendo O(n) no pior cenário – onde o BST se torna distorcido. O AVL ajuda a eliminar essa limitação restringindo a altura da árvore. Ao fazer isso, ele impõe um limite superior em todas as operações para ser o máximo de O(log n) onde n = número de nós.

22. Quais são as propriedades de uma árvore B?

Uma árvore B de ordem m contém as seguintes propriedades:

• Todas as propriedades de uma árvore M-way.
• Cada nó da B_tree terá no máximo m filhos.
• Cada nó, exceto raiz e folha, terá pelo menos m / 2 filhos.
• O nó raiz deve ter pelo menos 2 nós filhos.
• Todos os nós folha devem estar no mesmo nível horizontal.

23. O que você entende sobre a estrutura de dados do gráfico?

A Estrutura de Dados do Grafo (G) pode ser definida como um conjunto ordenado G(V,E) onde V representa o conjunto de vértices e E são as arestas que formam as conexões. Basicamente, um Graph pode ser pensado como uma árvore cíclica onde os nós podem manter relacionamentos complexos entre eles e não apenas relacionamentos pai-filho.

24. Diferencie entre ciclo, caminho e circuito com referência à estrutura de dados do gráfico.

As diferenças entre o ciclo, caminho e circuito são as seguintes:

• Um patch é uma ordem de vértices vizinhos conectados por arestas sem quaisquer restrições.
• Um ciclo é um caminho fechado em que o vértice inicial é o mesmo que o vértice final. Em um ciclo, nenhum vértice em particular pode ser visitado duas vezes.
• Um circuito, como um ciclo, é um caminho fechado com o vértice inicial igual ao vértice final. No entanto, qualquer vértice em particular em um circuito pode ser visitado mais de uma vez.

25. Como funciona o algoritmo de Kruskal?

O Algoritmo de Kruskal considera o grafo como uma floresta e cada um de seus nós como uma árvore individual. Diz-se que uma árvore se conecta a outra árvore se e somente se ela tiver o menor custo entre todas as opções e não violar nenhuma propriedade de uma árvore geradora mínima (MST).

Relacionado: Árvore Binária na Estrutura de Dados

26. Como o algoritmo de Prim encontra a árvore geradora?

O algoritmo de Prim funciona considerando os nós como árvores únicas. Em seguida, ele continua adicionando novos nós à árvore geradora a partir do gráfico fornecido que deve ser convertido na árvore geradora necessária.

27. O que é uma árvore geradora mínima (MST)?

MSTs, em grafos ponderados, são árvores que têm peso mínimo, mas abrangem todos os vértices.

28. O que é uma função recursiva?

Por definição, uma função recursiva chama a si mesma de volta ou chama diretamente uma função que a chama. Toda função recursiva tem alguns critérios básicos, após os quais a função para de chamar a si mesma.

29. O que é a técnica de busca por interpolação?

A técnica de busca por interpolação é uma modificação em relação ao método de busca binária. O algoritmo de busca por interpolação funciona na posição de apalpação dos valores desejados.

30. O que é hash?

Hashing é uma técnica muito útil usada para converter um intervalo de pares chave-valor em índices de uma matriz. As tabelas de hash são úteis ao criar armazenamento de dados associativo no qual o índice de dados pode ser facilmente encontrado apenas fornecendo seu par chave-valor!

Para concluir

As Estruturas de Dados são verdadeiramente a base de tudo o que acontece na Ciência da Computação. Mesmo as aplicações mais complexas da Ciência da Computação, ou seja, Ciência de Dados, Aprendizado de Máquina, Inteligência Artificial, IoT são todas construídas em cima de Estruturas de Dados e Algoritmos.

Portanto, se você é um iniciante que deseja fazer carreira em qualquer um dos campos da nova era, é recomendável começar dominando Estruturas de Dados e Algoritmos. Ou então, você também pode conferir nosso curso sobre Programa PG Executivo em Ciência de Dados , projetado para iniciantes. Aprenda do zero e torne-se um especialista em Data Science. Inscreva-se hoje mesmo!