As estruturas de dados mais importantes que você deve saber sobre sua entrevista de programação

Nicklaus Wirth, um cientista da computação suíço, escreveu um livro em 1976 intitulado Algoritmos + Estruturas de Dados = Programas .

Depois de mais de 40 anos, essa identidade permanece válida. É por isso que os candidatos a emprego que desejam se tornar programadores devem demonstrar que conhecem as estruturas de dados e são capazes de aplicá-las.

Em quase todas as tarefas, um candidato precisa de um entendimento profundo das estruturas de dados. Ao mesmo tempo, não é tão importante se você é graduado (formado em uma universidade ou em cursos de programação) ou se tem dezenas de anos de experiência atrás de você.

Às vezes, nas perguntas da entrevista, uma ou outra estrutura de dados é mencionada diretamente, por exemplo, "dada uma árvore binária". Em outros casos, a tarefa é formulada de uma maneira mais velada, por exemplo, "você precisa acompanhar quantos livros temos de cada autor".

Estudar estruturas de dados é um negócio indispensável, mesmo que você esteja apenas tentando melhorar profissionalmente em seu trabalho atual. Vamos começar com o básico.

Traduzido para Alconost

O que é uma estrutura de dados?

Em resumo, uma estrutura de dados é um contêiner no qual as informações são organizadas de maneira característica. Graças a esse "layout", a estrutura de dados será eficaz em algumas operações e ineficiente em outras. Nosso objetivo é entender as estruturas de dados de forma que você possa escolher entre elas as mais adequadas para solucionar o problema específico que está enfrentando.

Por que precisamos de estruturas de dados?

Como as estruturas de dados são usadas para armazenar informações de maneira ordenada e os dados são o fenômeno mais importante na ciência da computação, o verdadeiro valor das estruturas de dados é óbvio.

Não importa que tipo de tarefa você esteja resolvendo, de uma forma ou de outra você terá que lidar com os dados, seja o salário de um funcionário, cotações de ações, uma lista de produtos para ir à loja ou uma lista telefônica comum.

Dependendo do cenário específico, os dados devem ser armazenados em um formato adequado. Temos à nossa disposição uma série de estruturas de dados que nos fornecem esses vários formatos.

Estruturas de dados comuns

Primeiro, vamos listar as estruturas de dados mais comuns e depois analisar cada uma delas:

1. Matrizes
2. Pilhas
3. Filas
4. Listas Vinculadas
5. Árvores
6. Conta
7. Brocas (em essência, também são árvores, mas devem ser consideradas separadamente).
8. Tabelas de hash

Matrizes

Uma matriz é a estrutura de dados mais simples e comum. Outras estruturas de dados, como pilhas e filas, são derivadas de matrizes.

É mostrada aqui uma matriz simples de tamanho 4 contendo elementos (1, 2, 3 e 4).

Cada item de dados recebe um valor numérico positivo chamado índice e corresponde à posição desse item na matriz. Na maioria das linguagens de programação, os elementos na matriz são numerados de 0.

Existem dois tipos de matrizes:

• Unidimensional (como mostrado acima)
• Multidimensional (matrizes nas quais outras matrizes estão incorporadas)

As operações mais simples da matriz

• Inserir - insere um elemento em uma posição com um determinado índice
• Get - retorna um elemento que ocupa uma posição com um determinado índice
• Excluir - exclui o item com o índice especificado
• Tamanho - Obtenha o número total de elementos na matriz

Perguntas Frequentes da Entrevista

• Encontre o segundo elemento mínimo da matriz
• Encontre números inteiros não repetitivos em uma matriz
• Mesclar duas matrizes classificadas
• Reordenar valores positivos e negativos em uma matriz

Pilhas

Todo mundo conhece a famosa opção "Cancelar", que é fornecida em quase todas as aplicações. Já se perguntou como isso funciona? O significado é o seguinte: o estado anterior do seu trabalho é salvo no programa (o número de estados salvos é limitado) e eles estão localizados na memória nesta ordem: o último elemento salvo é o primeiro. Somente matrizes não podem resolver esse problema. É aqui que a pilha é útil.

A pilha pode ser comparada a uma pilha alta de livros. Se você precisar de um livro próximo ao centro da pilha, será necessário primeiro remover todos os livros acima. É assim que o princípio LIFO funciona (último a chegar, primeiro a ir).

Parece uma pilha contendo três elementos de dados (1, 2 e 3), onde 3 está no topo - portanto, ele será removido primeiro:

Operações de pilha mais simples:

• Empurrar - Empurra um item para a pilha na parte superior
• Pop - Retorna o item principal depois que ele é removido da pilha
• isEmpty - Retorna true se a pilha estiver vazia
• Superior - Retorna o item superior sem removê-lo da pilha

Entreviste perguntas freqüentes sobre o Stack

• Calcular a expressão postfix usando a pilha
• Classificar valores na pilha
• Verifique parênteses balanceados na expressão

Filas

Uma fila, como uma pilha, é uma estrutura de dados linear na qual os elementos são armazenados em ordem sequencial. A única diferença significativa entre a pilha e a fila é que, na fila, em vez de LIFO, o princípio FIFO se aplica (primeiro a chegar, primeiro a ir).

Um exemplo realista ideal de uma fila - essa é a fila de clientes na bilheteria. Um novo comprador está no final da linha, não no começo. Quem estiver na fila primeiro será o primeiro a comprar um ingresso e deixá-lo primeiro.

Aqui está uma imagem de uma fila com quatro elementos de dados (1, 2, 3 e 4), onde 1 vai primeiro e sai da fila primeiro:

Operações de fila simples

• Enfileirar () - Adiciona um item ao final da fila
• Desfileirar () - remove um item da frente da fila
• isEmpty () - Retorna true se a fila estiver vazia
• Top () - Retorna o primeiro item da fila

Perguntas Frequentes da Entrevista

• Implementar uma pilha usando uma fila
• Pague os primeiros k itens na fila
• Gere números binários de 1 a n usando uma fila

Lista vinculada

Uma lista vinculada é outra importante estrutura de dados linear que, à primeira vista, se assemelha a uma matriz. No entanto, uma lista vinculada difere de uma matriz na alocação de memória, estrutura interna e como as operações básicas de inserção e exclusão são executadas nela.

Uma lista vinculada se assemelha a uma cadeia de nós, cada um dos quais contém informações: por exemplo, dados e um ponteiro para o próximo nó na cadeia. Há um ponteiro correspondente ao primeiro elemento em uma lista vinculada e, se a lista estiver vazia, ela será direcionada simplesmente para nulo (nada).

O uso de listas vinculadas, sistemas de arquivos, tabelas de hash e listas de adjacência é implementado.

É assim que você pode visualizar a estrutura interna de uma lista vinculada:


Existem tipos de listas vinculadas:

• Lista de links únicos (unidirecional)
• Lista duplamente vinculada (bidirecional)

As operações mais simples com listas vinculadas são:

• InsertAtEnd - insere o item especificado no final da lista vinculada.
• InsertAtHead - Insere o elemento especificado no início (da cabeça) da lista vinculada
• Excluir - exclui o item especificado da lista vinculada.
• DeleteAtHead - exclui o primeiro item de uma lista vinculada.
• Pesquisar - Retorna o item especificado da lista vinculada.
• isEmpty - Retorna true se a lista vinculada estiver vazia

Perguntas frequentes da entrevista:

• Pagar uma lista vinculada
• Encontre o loop na lista vinculada
• Retorne o nó enésimo da parte superior da lista vinculada
• Remover valores duplicados da lista vinculada

Conta

Um gráfico é um conjunto de nós conectados um ao outro na forma de uma rede. Nós também são chamados vértices. O par (x, y) é chamado de aresta, o que significa que o vértice x está conectado ao vértice y . Uma aresta pode ter peso / custo - um indicador que caracteriza o quanto a transição do vértice x para o vértice y é cara.


Tipos de gráficos:

• Gráfico não direcionado
• Gráfico Orientado

Em uma linguagem de programação, os gráficos podem ser de dois tipos:

• Matriz de adjacência
• Lista de adjacências

Algoritmos de passagem de gráfico comuns:

• Pesquisa ampla
• Pesquisa em profundidade

Perguntas frequentes da entrevista:

• Implementar pesquisas de amplitude e profundidade
• Verifique se o gráfico é uma árvore ou não
• Contar o número de arestas em um gráfico
• Encontre o caminho mais curto entre dois picos

Árvores

Uma árvore é uma estrutura de dados hierárquica que consiste em vértices (nós) e arestas que os conectam. As árvores são semelhantes aos gráficos, no entanto, a principal diferença entre uma árvore e um gráfico é a seguinte: não há ciclos em uma árvore.

As árvores são amplamente utilizadas no campo da inteligência artificial e em algoritmos complexos, atuando como um repositório eficaz de informações na solução de problemas.

Aqui está um diagrama em árvore simples e uma terminologia básica associada a essa estrutura de dados:


Existem os seguintes tipos de árvores:

• N-tree
• Árvore equilibrada
• Árvore binária
• Árvore de pesquisa binária
• Árvore AVL
• Ébano vermelho
• 2-3 árvore

Das árvores acima, a árvore binária e a árvore de pesquisa binária são mais usadas.

Perguntas frequentes sobre entrevistas sobre árvores:

Encontre a altura de uma árvore binária
Encontre o k-ésimo valor máximo na árvore de pesquisa binária
Encontre nós localizados "k" da raiz
Encontre os ancestrais de um determinado nó em uma árvore binária

Boro

O boro, também chamado de "árvore de prefixo", é uma estrutura de dados semelhante a uma árvore que é especialmente eficaz na solução de problemas de cadeia de caracteres. Ele fornece recuperação rápida de dados e é usado com mais frequência para procurar palavras em um dicionário, preenchimento automático em um mecanismo de pesquisa e até mesmo para roteamento IP.

É assim que as três palavras “superior” (superior), “assim” (daí) e “deles” (eles) são armazenadas na floresta:


As palavras são organizadas de cima para baixo, e os nós verdes "p", "s" e "r" completam, respectivamente, as palavras "top", "assim" e "seus".

Perguntas freqüentes sobre entrevistas sobre brocas:

• Contar o número total de palavras armazenadas no pinhal
  
• Exibe todas as palavras armazenadas na floresta.
  
• Classificar elementos da matriz usando boro
  
• Crie palavras de vocabulário usando boro
  
• Criar dicionário T9
  

Tabela de hash

Hashing é um processo usado para identificar objetos de forma exclusiva e armazenar cada objeto por um índice pré-calculado chamado de "chave". Assim, o objeto é armazenado como um valor-chave e uma coleção desses objetos é chamada de dicionário. Cada objeto pode ser pesquisado por sua chave. Existem diferentes estruturas de dados criadas com base no princípio do hash, mas na maioria das vezes uma tabela de hash é usada nessas estruturas.

Como regra, tabelas de hash são implementadas usando matrizes.

O desempenho de uma estrutura de dados com hash depende dos três fatores a seguir:

• Função hash
• Tamanho da tabela de hash
• Método de processamento de colisão

A seguir, mostra como um hash é mapeado para uma matriz. O índice dessa matriz é calculado usando uma função hash.

Perguntas freqüentes sobre a hash da entrevista:

• Encontre pares simétricos em uma matriz
• Acompanhe o caminho completo
• Descubra se uma matriz é um subconjunto de outra matriz
• Verifique se as matrizes são desunidas

A descrição acima descreve as oito estruturas de dados mais importantes que você definitivamente precisa conhecer antes de ir para uma entrevista de programação.

Boa sorte e aprendizado interessante! :)

Sobre o tradutor

O artigo foi traduzido por Alconost.

A Alconost localiza jogos , aplicativos e sites em 68 idiomas. Tradutores em idioma nativo, teste linguístico, plataforma em nuvem com API, localização contínua, gerentes de projeto 24/7, qualquer formato de recursos de string.

Também criamos vídeos de publicidade e treinamento - para sites que vendem, imagem, publicidade, treinamento, teasers, exploradores, trailers do Google Play e da App Store.

Mais detalhes