O que eles podem perguntar em uma entrevista: Estruturas de dados em Java. Parte 1

Olá! Não importa como você olhe, você não pode se tornar um desenvolvedor sem passar com sucesso em uma entrevista técnica de admissão. Existem muitas tecnologias relacionadas ao Java e é impossível aprender tudo. Via de regra, algo específico é perguntado durante as entrevistas apenas se estiverem procurando um desenvolvedor com boa experiência em algum framework importante para o projeto. Se for assim, você será perseguido por esse framework a toda velocidade, não tenha dúvidas disso. Mas agora estamos falando da base que todo desenvolvedor Java deve conhecer. Sobre aquele conhecimento clássico a partir do qual tudo começa. Hoje eu gostaria de abordar um dos tópicos fundamentais de qualquer estrutura de dados de entrevistas em Java . Então, em vez de rodeios, vamos começar. Encontre uma lista de perguntas que podem ser feitas sobre esse tópico durante uma entrevista.

1. Conte-nos um pouco sobre estruturas de dados

Uma estrutura de dados é um armazenamento de dados que contém informações estruturadas de uma determinada maneira. Essas estruturas são projetadas para o desempenho eficiente de determinadas operações. Exemplos típicos de estruturas de dados são:

• matrizes,
• pilhas,
• filas,
• listas relacionadas,
• gráficos,
• árvores,
• árvores de prefixo,
• tabela hash.

Você pode descobrir mais sobre eles aqui e aqui . Os dados são um componente chave em um programa e as estruturas permitem que esses dados sejam armazenados de uma forma específica e claramente estruturada. Qualquer que seja a sua aplicação, este aspecto estará sempre presente nela: se for uma loja web, serão armazenadas informações sobre produtos, se for uma rede social, dados de usuários e arquivos, e assim por diante.

2. O que você sabe sobre matrizes?

Um array é um contêiner para armazenar valores do mesmo tipo, cujo número foi especificado antecipadamente. Um exemplo de criação de um array com valores de string:

String[] strArray = {"Java","is","the","best","language"};

Ao criar um array, a memória é alocada para todos os seus elementos: quanto mais células para elementos forem especificadas inicialmente, mais memória será alocada. Se um array vazio com um certo número de células for criado, todos os elementos do array receberão valores padrão. Por exemplo:

int[] arr = new int[10];

Assim, para um array com elementos do tipo booleano , os valores iniciais ( padrão ) serão false , para arrays com valores numéricos - 0, com elementos do tipo char - \u0000 . Para uma matriz do tipo de classe (objetos) - null (não strings vazias - “” mas especificamente null ). Ou seja, no exemplo acima, todos os valores do array arr serão 0 até serem especificados diretamente. Ao contrário das coleções, os arrays não são dinâmicos. Depois que uma matriz de determinado tamanho é declarada, o tamanho em si não pode ser alterado. Para adicionar um novo elemento a um array, você precisa criar um novo array maior e copiar todos os elementos do antigo para ele (é assim que ArrayList funciona). Há um ponto que nem todo mundo sabe e no qual você pode ser muito bem apanhado. Existem dois tipos de variáveis ​​em Java - tipos simples e referências a objetos completos. Quais destas são matrizes? Por exemplo, aqui:

int[] arr = new int[10];

Parece que tudo é simples - são 10 elementos int . Então, podemos dizer que este é um tipo simples? Não importa como seja. Em Java, arrays são objetos criados dinamicamente e podem ser atribuídos a variáveis ​​do tipo Object. Todos os métodos da classe Object podem ser chamados em um array. Então podemos até escrever:

Object arr = new int[]{7,5,4,3};
System.out.println(arr.toString());

Ao enviar para o console você pode obter algo como: Leia mais sobre os recursos de arrays em Java neste artigo sobre Java Array . Para consolidar seu conhecimento, você pode resolver diversos problemas desta coleção .

3. Explique a hierarquia das coleções

As coleções são usadas em situações em que você precisa de flexibilidade ao trabalhar com dados. As coleções podem adicionar um elemento, remover um elemento e realizar muitas outras operações. Existem muitas implementações diferentes em Java e só precisamos escolher a coleção certa para a situação atual. Normalmente, quando você menciona a interface Collection , é solicitado que você liste algumas de suas implementações e seu relacionamento com Map . Bem, vamos descobrir. Portanto, Collection e Map são duas hierarquias diferentes para estruturas de dados. Qual a aparência da hierarquia da coleção : A interface da coleção é o link principal com uma lista de métodos básicos, dos quais se originam três tipos básicos de estruturas de dados - Set , List , Queue . Set<T> é uma interface que representa uma coleção de objetos em que cada objeto é único. List<T> é uma interface que representa uma sequência ordenada de objetos chamada lista. Queue<T> é uma interface responsável por estruturas que são organizadas como uma fila (armazenamento sequencial de elementos). Conforme mencionado anteriormente, Map é uma hierarquia separada: Map<K, V> é uma interface que representa um dicionário no qual os elementos estão contidos como pares de valores-chave. Além disso, todas as chaves (K) são exclusivas no objeto Map . Esse tipo de coleção torna mais fácil encontrar um elemento se conhecermos a chave - o identificador exclusivo do objeto.

4. O que você sabe sobre Set?

Conforme afirmado anteriormente, esta coleção apresenta muitos elementos exclusivos. Em outras palavras, o mesmo objeto não pode aparecer mais de uma vez em um Java Set . Gostaria também de salientar que não podemos extrair um elemento de um Set por número (índice) - apenas por força bruta. O importante é que diferentes implementações de Set tenham diferentes formas de estruturar dados. Consideraremos implementações específicas mais adiante. Portanto, as principais implementações de Set : HashSet é um conjunto que se baseia em uma tabela hash, que por sua vez auxilia na busca. Usa uma função hash que melhora o desempenho durante pesquisas e inserções. Independentemente do número de elementos, em geral, a inserção e a busca (às vezes a exclusão) são realizadas em tempo quase constante - O(1). Veremos a função hash com mais detalhes um pouco mais tarde. Gostaria também de observar que o HashSet contém um HashMap , que é onde toda a mágica acontece. Aqui está um artigo detalhado sobre HashSet em Java . LinkedHashSet – esta classe estende HashSet sem adicionar novos métodos. Assim como LinkedList , esta classe mantém uma lista vinculada dos elementos de um conjunto na ordem em que foram inseridos. Isso permite organizar a ordem necessária em uma determinada implementação do Set . A classe TreeSet cria um conjunto baseado em uma árvore rubro-preta para organizar a estrutura de armazenamento de elementos. Em outras palavras, em um determinado conjunto podemos ordenar os elementos em ordem crescente. Se usarmos alguns objetos padrão da “caixa”, por exemplo, Integer , então não precisamos fazer nada para organizar o conjunto de Inteiros em ordem crescente:

TreeSet set = new TreeSet<>();
set.add(4);
set.add(2);
set.add(3);
set.add(1);

System.out.println(set);

E no console obteremos a saída: Ou seja, neste conjunto os números são armazenados de forma ordenada. Se usarmos elementos String em um TreeSet , eles serão classificados, mas em ordem alfabética. Bem, e se tivermos alguma classe padrão (personalizada)? Como os objetos desta classe estruturarão o TreeSet ? Se tentarmos atribuir um objeto arbitrário a este Set :

TreeSet set = new TreeSet<>();
set.add(new Cat(4, "Murzik"));
set.add(new Cat(2, "Barsik"));
set.add(new Cat(3, "Гарфилд"));

System.out.println(set);

Receberemos uma ClassCastException porque o TreeSet não sabe como classificar objetos deste tipo. Neste caso, precisamos de nosso objeto personalizado para implementar a interface Comparable e seu método compareTo :

public class Cat implements Comparable {
    int age;
    String name;

   public Cat(int age, String name) {
       this.age = age;
       this.name = name;
   }

   @Override
   public int compareTo(Cat cat) {
       return age > cat.age ? 1 : -1;
   }

   @Override
   public String toString() {
       return "Cat{" +
               "age=" + age +
               ", name='" + name + '\'' +
               '}';
   }
}

Como você percebeu, o método compareTo retorna um int :

• 1 se o objeto atual (este) for considerado grande;
• -1 se o objeto atual for considerado menor que aquele que veio como argumento;
• 0 se os objetos forem iguais (não usamos neste caso).

Neste caso, nosso TreeSet funcionará corretamente e exibirá o resultado: Outra maneira é criar uma classe de classificação separada que implemente a interface do comparador e seu método de comparação :

public class CatComparator implements Comparator {

   @Override
   public int compare(Cat o1, Cat o2) {
       return o1.age > o2.age ? 1 : -1;
   }
}

Neste caso, para utilizá-lo, devemos definir um objeto desta classe para o construtor TreeSet :

TreeSet set = new TreeSet<>(new CatComparator());

Depois disso, todos os objetos da classe Cat incluídos no TreeSet serão classificados usando a classe Cat Comparator . Você pode aprender mais sobre Comparator e Comparable em Java neste artigo .

5. Conte-nos sobre a fila

Queue é uma interface responsável por estruturas que são organizadas como uma fila – uma estrutura de dados que armazena elementos sequencialmente. Por exemplo, em uma fila de pessoas, a primeira pessoa a entrar será aquela que chegou mais cedo que as outras, e a última será aquela que chegou mais tarde que todos os demais. Este método é denominado FIFO , ou seja, First in First Out . Os métodos de fila exclusivos concentram-se em trabalhar com o primeiro ou o último elemento, por exemplo:

• add e offer - insere um elemento no final da fila,
• remove - recupera e remove o cabeçalho desta fila,
• peek - Recupera, mas não remove o cabeçalho da fila.

PARTE 2