As principais estruturas de dados que você deve saber para sua próxima entrevista de codificação

Niklaus Wirth, um cientista da computação suíço, escreveu um livro em 1976 intitulado Algorithms + Data Structures = Programs.

Mais de 40 anos depois, essa equação ainda é válida. É por isso que os candidatos à engenharia de software precisam demonstrar sua compreensão das estruturas de dados junto com seus aplicativos.

Quase todos os problemas exigem que o candidato demonstre um conhecimento profundo das estruturas de dados. Não importa se você acabou de se formar (em uma universidade ou em um bootcamp de programação), ou se você tem décadas de experiência.

Às vezes, as perguntas da entrevista mencionam explicitamente uma estrutura de dados, por exemplo, "dada uma árvore binária". Outras vezes, está implícito, como “queremos rastrear o número de livros associados a cada autor”.

Aprender estruturas de dados é essencial, mesmo se você estiver apenas tentando melhorar em seu trabalho atual. Vamos começar entendendo o básico.

O que é uma estrutura de dados?

Simplificando, uma estrutura de dados é um contêiner que armazena dados em um layout específico. Este “layout” permite que uma estrutura de dados seja eficiente em algumas operações e ineficiente em outras. Seu objetivo é entender as estruturas de dados para que você possa escolher a estrutura de dados mais adequada para o problema em questão.

Por que precisamos de estruturas de dados?

Como as estruturas de dados são usadas para armazenar dados de forma organizada, e como os dados são a entidade mais importante na ciência da computação, o verdadeiro valor das estruturas de dados é claro.

Não importa o problema que você esteja resolvendo, de uma forma ou de outra você tem que lidar com os dados - sejam eles o salário de um funcionário, o preço das ações, uma lista de compras ou até mesmo uma simples lista telefônica.

Com base em diferentes cenários, os dados precisam ser armazenados em um formato específico. Temos um punhado de estruturas de dados que atendem à necessidade de armazenar dados em diferentes formatos.

Estruturas de dados comumente usadas

Vamos primeiro listar as estruturas de dados mais comumente usadas e, em seguida, vamos cobri-las uma por uma:

  1. Arrays
  2. Pilhas
  3. Filas
  4. Listas Ligadas
  5. Árvores
  6. Gráficos
  7. Tenta (elas são efetivamente árvores, mas ainda é bom chamá-las separadamente).
  8. Hash Tables

Arrays

Um array é a estrutura de dados mais simples e mais amplamente usada. Outras estruturas de dados, como pilhas e filas, são derivadas de matrizes.

Aqui está uma imagem de um array simples de tamanho 4, contendo elementos (1, 2, 3 e 4).

Cada elemento de dados é atribuído a um valor numérico positivo denominado Índice , que corresponde à posição desse item na matriz. A maioria das linguagens define o índice inicial da matriz como 0.

A seguir estão os dois tipos de matrizes:

  • Matrizes unidimensionais (como mostrado acima)
  • Arrays multidimensionais (arrays dentro de arrays)

Operações básicas em matrizes

  • Inserir - insere um elemento em um determinado índice
  • Get - Retorna o elemento em um determinado índice
  • Excluir - exclui um elemento em um determinado índice
  • Tamanho - obtém o número total de elementos em uma matriz

Perguntas comuns para a entrevista do Array

  • Encontre o segundo elemento mínimo de uma matriz
  • Primeiros inteiros não repetidos em uma matriz
  • Mesclar dois arrays classificados
  • Reorganizar valores positivos e negativos em uma matriz

Pilhas

Todos conhecemos a famosa opção Desfazer , que está presente em quase todos os aplicativos. Já se perguntou como funciona? A ideia: você armazena os estados anteriores do seu trabalho (que são limitados a um número específico) na memória, de forma que o último apareça primeiro. Isso não pode ser feito apenas usando arrays. É aí que o Stack se torna útil.

Um exemplo da vida real de Stack poderia ser uma pilha de livros colocados em ordem vertical. Para obter o livro que está em algum lugar no meio, você precisará remover todos os livros colocados em cima dele. É assim que funciona o método LIFO (Last In First Out).

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

Operações básicas de pilha:

  • Empurrar - insere um elemento no topo
  • Pop - Retorna o elemento superior após removê-lo da pilha
  • isEmpty - Retorna verdadeiro se a pilha estiver vazia
  • Top - Retorna o elemento superior sem removê-lo da pilha

Perguntas comuns da entrevista de Stack

  • Avalie a expressão pós-fixada usando uma pilha
  • Classificar valores em uma pilha
  • Verifique os parênteses equilibrados em uma expressão

Filas

Semelhante a Stack, Queue é outra estrutura de dados linear que armazena o elemento de maneira sequencial. A única diferença significativa entre Stack e Queue é que em vez de usar o método LIFO, Queue implementa o FIFO, que é a abreviação de First in First Out.

Um exemplo perfeito da vida real de Fila: uma fila de pessoas esperando em uma bilheteria. Se uma nova pessoa vier, ela entrará na fila do final, não do início - e a pessoa que estiver na frente será a primeira a obter o bilhete e, portanto, sair da fila.

Aqui está uma imagem de Queue contendo quatro elementos de dados (1, 2, 3 e 4), onde 1 está no topo e será removido primeiro:

Operações básicas de Queue

  • Enqueue () - Insere um elemento no final da fila
  • Dequeue () - Remove um elemento do início da fila
  • isEmpty () - Retorna verdadeiro se a fila estiver vazia
  • Top () - Retorna o primeiro elemento da fila

Perguntas comuns da entrevista de fila

  • Implementar pilha usando uma fila
  • Reverter os primeiros k elementos de uma fila
  • Gere números binários de 1 a n usando uma fila

Lista Ligada

Uma lista encadeada é outra estrutura de dados linear importante que pode parecer semelhante a matrizes no início, mas difere na alocação de memória, estrutura interna e como as operações básicas de inserção e exclusão são realizadas.

Uma lista encadeada é como uma cadeia de nós, onde cada nó contém informações como dados e um ponteiro para o nó seguinte na cadeia. Existe um ponteiro principal, que aponta para o primeiro elemento da lista vinculada e, se a lista estiver vazia, ele simplesmente aponta para nulo ou nada.

Listas vinculadas são usadas para implementar sistemas de arquivos, tabelas de hash e listas de adjacência.

Esta é uma representação visual da estrutura interna de uma lista vinculada:

A seguir estão os tipos de listas vinculadas:

  • Lista vinculada individualmente (unidirecional)
  • Lista duplamente vinculada (bidirecional)

Operações básicas da lista vinculada:

  • InsertAtEnd - insere um determinado elemento no final da lista vinculada
  • InsertAtHead - Insere um determinado elemento no início / cabeçalho da lista vinculada
  • Excluir - Exclui um determinado elemento da lista vinculada
  • DeleteAtHead - Exclui o primeiro elemento da lista vinculada
  • Pesquisar - Retorna o elemento fornecido de uma lista vinculada
  • isEmpty - Retorna verdadeiro se a lista vinculada estiver vazia

Perguntas comuns da entrevista da lista vinculada

  • Reverter uma lista vinculada
  • Detectar loop em uma lista vinculada
  • Retorne o enésimo nó do final em uma lista vinculada
  • Remover duplicatas de uma lista vinculada

Gráficos

Um gráfico é um conjunto de nós conectados uns aos outros na forma de uma rede. Os nós também são chamados de vértices. Um par (x, y) é chamado de aresta , o que indica que o vértice x está conectado ao vértice y . Uma aresta pode conter peso / custo, mostrando quanto custo é necessário para atravessar do vértice x para y .

Tipos de gráficos:

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

Em uma linguagem de programação, os gráficos podem ser representados usando duas formas:

  • Matriz de adjacência
  • Lista de Adjacência

Algoritmos comuns de passagem de gráfico:

  • Largura da primeira pesquisa
  • Profundidade primeira pesquisa

Perguntas comuns da entrevista do Graph

  • Implementar a primeira pesquisa em amplitude e profundidade
  • Verifique se um gráfico é uma árvore ou não
  • Conte o número de arestas em um gráfico
  • Encontre o caminho mais curto entre dois vértices

Á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, mas o ponto principal que diferencia uma árvore do gráfico é que um ciclo não pode existir em uma árvore.

Árvores são amplamente utilizadas em Inteligência Artificial e algoritmos complexos para fornecer um mecanismo de armazenamento eficiente para resolução de problemas.

Aqui está uma imagem de uma árvore simples e terminologias básicas usadas na estrutura de dados em árvore:

A seguir estão os tipos de árvores:

  • Árvore N-ária
  • Árvore Equilibrada
  • Árvore Binária
  • Árvore de pesquisa binária
  • Árvore AVL
  • Red Black Tree
  • 2-3 Árvore

Acima, a Árvore Binária e a Árvore de Busca Binária são as árvores mais comumente usadas.

Perguntas frequentes da entrevista da Tree

  • Encontre a altura de uma árvore binária
  • Encontre o k-ésimo valor máximo em uma árvore de pesquisa binária
  • Encontre nós a uma distância “k” da raiz
  • Encontre ancestrais de um determinado nó em uma árvore binária

Trie

O Trie, também conhecido como “Árvores de Prefixo”, é uma estrutura de dados em forma de árvore que se mostra bastante eficiente para resolver problemas relacionados a strings. Ele fornece recuperação rápida e é usado principalmente para pesquisar palavras em um dicionário, fornecer sugestões automáticas em um mecanismo de pesquisa e até mesmo para roteamento de IP.

Aqui está uma ilustração de como três palavras “top”, “assim” e “deles” são armazenadas no Trie:

As palavras são armazenadas de cima para baixo, onde os nós verdes “p”, “s” e “r” indicam o final de “topo”, “assim” e “seus” respectivamente.

Perguntas comuns na entrevista com Trie:

  • Conte o número total de palavras em Trie
  • Imprime todas as palavras armazenadas no Trie
  • Classifique os elementos de uma matriz usando Trie
  • Forme palavras de um dicionário usando Trie
  • Construir um dicionário T9

Tabela Hash

Hashing é um processo usado para identificar objetos de forma exclusiva e armazenar cada objeto em algum índice exclusivo pré-calculado chamado de "chave". Portanto, o objeto é armazenado na forma de um par de "valor-chave", e a coleção de tais itens é chamada de "dicionário". Cada objeto pode ser pesquisado usando essa chave. Existem diferentes estruturas de dados baseadas em hashing, mas a estrutura de dados mais comumente usada é a tabela de hash .

Geralmente, as tabelas de hash são implementadas por meio de matrizes.

O desempenho de hashing da estrutura de dados depende destes três fatores:

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

Aqui está uma ilustração de como o hash é mapeado em uma matriz. O índice desta matriz é calculado por meio de uma função Hash.

Perguntas frequentes da entrevista de Hashing

  • Encontre pares simétricos em uma matriz
  • Trace o caminho completo de uma jornada
  • Descubra se uma matriz é um subconjunto de outra matriz
  • Verifique se as matrizes fornecidas são disjuntas

Acima estão as oito principais estruturas de dados que você definitivamente deve conhecer antes de iniciar uma entrevista de codificação.

Se você está procurando recursos em estruturas de dados para entrevistas de codificação, dê uma olhada nos cursos interativos e baseados em desafios: Estruturas de dados para entrevistas de codificação (Python, Java ou JavaScript).

Para perguntas mais avançadas, dê uma olhada em Coderust 3.0: Preparação para Entrevistas de Codificação Mais Rápida com Desafios e Visualizações Interativos.

Se você está se preparando para uma entrevista de engenharia de software, aqui está um roteiro abrangente para se preparar para a codificação de entrevistas.

Boa sorte e bom aprendizado! :)