Análise de perguntas e respostas de entrevistas para desenvolvedor Java. Parte 9

Fogo de artifício! Ser programador não é fácil. Você precisa aprender constantemente, sempre aprender algo novo. Mas, como em qualquer outro negócio, o mais difícil é começar, dar o primeiro passo em direção ao seu objetivo. E como você está neste site e lendo este artigo, você concluiu a primeira etapa. Isso significa que agora você precisa se mover propositalmente em direção ao seu objetivo, sem desacelerar ou desligar no caminho. Se bem entendi, seu objetivo é se tornar um desenvolvedor Java ou aprimorar seus conhecimentos, se você for um. Se sim, então você está no lugar certo, porque continuaremos analisando uma extensa lista de mais de 250 perguntas de entrevistas para desenvolvedores Java. Vamos continuar!

Coleções

84. Conte-nos sobre iteradores e seu uso

Coleções são um dos tópicos favoritos em qualquer entrevista de desenvolvedor Java e, ao falar sobre hierarquia de coleções, os candidatos costumam dizer que ela começa com a interface Collection . Mas isso não é verdade, pois acima dessa interface existe outra - Iterable . Esta interface representa o método iterator() , que permite chamar um objeto Iterator para a coleção atual. E o que exatamente é esse objeto Iterator ? Um Iterador é um objeto que fornece a capacidade de percorrer uma coleção e iterar sobre elementos sem que o usuário precise conhecer a implementação de uma coleção específica. Ou seja, é uma espécie de ponteiro para os elementos da coleção, que, por assim dizer, aponta para um determinado lugar dela. O iterador possui os seguintes métodos:

• hasNext() - retorna verdadeiro se houver um elemento localizado após o ponteiro (este método permite descobrir se o final da coleção foi atingido);
• next() – retorna o próximo elemento após o ponteiro. Se não houver nenhum, NoSuchElementException será lançado . Ou seja, antes de usar este método, é melhor ter certeza de que o elemento existe - usando hasNext() ;
• remove() - remove o último elemento recebido da coleção usando o método next() . Se next() nunca tiver sido chamado antes de remove() ser chamado, uma exceção será lançada - IllegalStateException ;
• forEachRemaining(<Consumer>) - executa a ação passada com cada elemento da coleção (o método apareceu no Java 8).

Aqui está um pequeno exemplo de iteração em uma lista e remoção de todos os seus elementos usando os métodos iteradores discutidos:

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();

while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

O console exibirá: Isso significa que a remoção dos elementos foi bem-sucedida. Assim que tivermos um iterador, poderíamos usar um método para imprimir todos os elementos na tela:

iterator.forEachRemaining(x -> System.out.print(x));

Mas depois disso, o iterador se tornaria inadequado para uso posterior, pois percorreria toda a lista, e um iterador regular não possui métodos para retrocesso. Aqui abordamos gradualmente LinkedList , ou seja, seu método listIterator() , que retorna um tipo modernizado de iterador - ListIterator . Além dos métodos iteradores regulares (padrão), este possui outros adicionais:

• add(<Element>) - insere um novo elemento na lista;
• hasPrevious() - retorna verdadeiro se existe um elemento localizado antes do ponteiro (se existe um elemento anterior);
• nextIndex() - retorna o índice na lista do próximo elemento após o ponteiro;
• previous() – retorna o elemento anterior (até o ponteiro);
• previousIndex() – retorna o índice do elemento anterior;
• set(<Element>) - Substitui o último elemento retornado pelos métodos next() ou previous() .

Como você pode ver, a funcionalidade deste iterador é muito mais interessante: permite mover-se nas duas direções e libera as mãos ao trabalhar com elementos. Além disso, quando as pessoas falam sobre iteradores, às vezes elas se referem ao próprio padrão. Para evitar problemas e falar sobre isso de forma convincente, leia este artigo sobre o padrão Iterator .

85. Qual é a hierarquia de coleção no Java Collection Framework?

Existem duas hierarquias de coleção em Java. A primeira hierarquia é a própria hierarquia de Coleções com a seguinte estrutura: Ela, por sua vez, é dividida nas seguintes subcoleções:

• Conjunto é uma interface que descreve tal estrutura de dados como um conjunto contendo elementos únicos não ordenados (não repetidos). A interface possui implementações padrão - TreeSet , HashSet e LinkedHashSet .
• Lista é uma interface que descreve uma estrutura de dados que armazena uma sequência ordenada de objetos. As instâncias que estão contidas em uma Lista podem ser inseridas e excluídas pelo seu índice nesta coleção (análogo a um array, mas com redimensionamento dinâmico). A interface possui implementações padrão - ArrayList , Vector ( considerado obsoleto e não usado de fato ) e LinkedList .
• Fila é uma interface que descreve uma estrutura de dados que armazena elementos na forma de uma fila que segue a regra FIFO - First In First Out . A interface possui as seguintes implementações padrão: LinkedList (sim, ela também implementa Queue ) e PriotityQueue .

A segunda hierarquia de coleções é Map , que possui a seguinte estrutura: Nesta coleção não há divisões em subcoleções (já que a hierarquia Map em si é algo como uma subcoleção, mas separada). As implementações de mapa padrão são Hashtable (considerado obsoleto), LinkedHashMap e TreeMap . Na verdade, quando questionado sobre Collection , geralmente se refere a ambas as hierarquias.

86. Qual é a estrutura interna de um ArrayList?

ArrayList é semelhante a um array, mas com a capacidade de expansão dinâmica. O que isso significa? O fato é que ArrayList funciona com base em um array regular, ou seja, armazena elementos em um array interno (seu tamanho padrão é 10 células). Quando o array interno está cheio, um novo array é criado, cujo tamanho é determinado pela fórmula:

<размерТекущегоМассива> * 3 / 2  + 1

Ou seja, se o tamanho do nosso array for 10, o tamanho do novo será: 10 * 3/2 + 1 = 16. Em seguida, todos os valores do primeiro array (antigo) são copiados para ele usando o método nativo System.arraycopy () e a primeira matriz é excluída. Na verdade, é assim que a extensibilidade dinâmica do ArrayList é implementada . Vejamos os métodos ArrayList mais usados : 1. add(<Elelement>) - adiciona um elemento ao final do array (na última célula vazia) e primeiro verifica se há espaço neste array. Se não estiver, é criado um novo array no qual os elementos são copiados. A complexidade logarítmica desta operação é O(1). Existe um método semelhante - add(<Index>,<Elelement>) . Ele adiciona um elemento não ao final da lista (array), mas a uma célula específica com o índice que veio como argumento. Neste caso, a complexidade logarítmica será diferente dependendo de onde for adicionada:

• se este for aproximadamente o início da lista, a complexidade logarítmica será próxima de O(N), pois todos os elementos localizados à direita do novo deverão ser movidos uma célula para a direita;
• se o elemento for inserido no meio - O(N/2) porque precisamos mover apenas metade dos elementos da lista uma célula para a direita.

Ou seja, a complexidade logarítmica deste método varia de O(N) a O(1) dependendo de onde o elemento está inserido. 2. set(<Index>,<Elelement>) - grava um elemento na posição especificada na lista. Se já existir um elemento nessa posição, sobrescreve-o. A complexidade logarítmica desta operação é O(1), pois não há deslocamentos: apenas busca por índice no array, que, como lembramos, tem complexidade O(1), e escrita do elemento. 3. remove(<index>) - remove um elemento pelo seu índice no array interno. Ao excluir um item que não está no final da lista, você deve mover todos os itens à direita dele, uma célula para a esquerda, para fechar a lacuna deixada após a exclusão do item. Portanto, a complexidade logarítmica será a mesma que add(<Index>,<Elelement>) se o elemento estiver no meio - O(N/2) - porque você precisa deslocar metade dos elementos um para a esquerda. Assim, se foi no início - SOBRE(N). Bem, se no final for O(1), não há necessidade de mover nada. Para quem quiser se aprofundar neste tema, deixarei este link de um artigo com análise da classe ArrayList .

87. Qual é a estrutura interna do LinkedList?

Se ArrayList contiver elementos em um array interno, então LinkedList estará na forma de uma lista duplamente vinculada. Isso significa que cada elemento contém um link para o elemento anterior ( anterior ) e o próximo ( próximo ). O primeiro elemento não possui link para o anterior (é o primeiro), mas é considerado o topo da lista, e o LinkedList possui um link direto para ele. O último elemento, na verdade, não possui um próximo elemento, ele é o final da lista e, portanto, existe um link direto para ele no próprio LinkedList . Portanto, a complexidade logarítmica de acessar o início ou o final de uma lista é O(1). Em ArrayList, quando a lista cresceu, o array interno aumentou, mas aqui tudo acontece de forma mais simples - ao adicionar um elemento, alguns links simplesmente mudam. Vejamos alguns dos métodos LinkedlList mais usados : 1. add(<Elelement>) - adicionando no final da lista, ou seja, após o último elemento (5) um link para o novo elemento será adicionado como next . O novo elemento terá um link para o último (5) como elemento anterior . A complexidade logarítmica de tal operação será O(1), já que é necessário apenas um link para o último elemento, e como você lembra, a cauda tem um link direto do LinkedList e a complexidade logarítmica de acessá-lo é mínima. 2. add(<Index>,<Elelement>) - adicionando um elemento por índice. Ao adicionar um elemento, por exemplo, no meio de uma lista, os elementos da cabeça e da cauda (em ambos os lados) são primeiro iterados até que o local desejado seja encontrado. Se quisermos inserir um elemento entre o terceiro e o quarto (na figura acima), então ao procurar o local certo, o próximo link do terceiro elemento já apontará para o novo. Para o novo, o link anterior apontará para o terceiro. Assim, o link do quarto elemento - anterior - já apontará para o novo elemento, e o próximo link do novo elemento apontará para o quarto elemento: A complexidade logarítmica deste método dependerá do índice dado ao novo elemento:

• se estiver próximo do início ou do final, se aproximará de O(1), pois não será realmente necessário iterar sobre os elementos;
• se estiver próximo do meio, então O(N/2) - os elementos da cabeça e da cauda serão classificados simultaneamente até que o elemento necessário seja encontrado.

3. set(<Index>,<Elelement>) - grava um elemento na posição especificada na lista. A complexidade logarítmica desta operação variará de O(1) a O(N/2), novamente dependendo de quão próximo o elemento está da cabeça, cauda ou meio. 4. remove(<index>) - remove um elemento da lista, essencialmente fazendo com que o elemento que vem antes daquele que está sendo removido ( previous ) faça referência ao elemento que vem depois daquele que está sendo removido ( next ). E vice-versa: para que o elemento que vem depois daquele que está sendo excluído se refira àquele que vem antes daquele que está sendo excluído: O resultado é um processo inverso à adição por índice ( add(<Index>,<Elelement>) ). Para quem deseja saber mais sobre a estrutura interna do LinkedList , recomendo a leitura deste artigo .

88. Qual é a estrutura interna de um HashMap?

Talvez uma das perguntas mais populares ao entrevistar um desenvolvedor Java. HashMap v funciona com pares chave-valor . Como eles são armazenados dentro do próprio HashMapv ? Dentro do HashMap existe uma matriz de nós:

Node<K,V>[] table

Por padrão, o tamanho do array é 16 e dobra cada vez que é preenchido com elementos (quando LOAD_FACTOR é atingido - uma certa porcentagem de preenchimento, por padrão é 0,75 ). Cada nó armazena um hash da chave, uma chave, um valor e um link para o próximo elemento: Na verdade, “link para o próximo elemento” significa que estamos lidando com uma lista vinculada individualmente, onde cada elemento contém um link para o proximo. Ou seja, o HashMap armazena dados em uma série de listas vinculadas individualmente. Mas observarei imediatamente: quando uma célula da matriz da tabela tem um link para uma lista vinculada simples semelhante que consiste em mais de um elemento, isso não é bom. Este fenômeno é chamado de colisão . Mas primeiro as primeiras coisas. Vamos ver como um novo par é salvo usando o método put . Primeiro, o hachCode() da chave é obtido. Portanto, para que o hashmap funcione corretamente , você precisa usar classes nas quais esse método seja substituído como chaves. Este código hash é então usado no método interno - hash() - para determinar o número dentro do tamanho do array da tabela . A seguir, a partir do número recebido, acessa-se uma célula específica do array da tabela . Aqui temos dois casos:

1. A célula está vazia – o novo valor do Node está armazenado nela .
2. A célula não está vazia - o valor das chaves é comparado. Se forem iguais, o novo valor do Node substitui o antigo, se não forem iguais, o próximo elemento é acessado e comparado com sua chave... E assim por diante até que o novo valor substitua algum antigo ou chegue ao final do lista vinculada individualmente e será armazenada lá como o último elemento.

Ao pesquisar um elemento por chave ( método get(<key>) ), o hashCode da chave é calculado, então seu valor dentro do array usando hash() , e usando o número resultante, a célula do array da tabela é encontrada , em que a busca já é realizada enumerando os nós e comparando a chave do nó desejado com a chave do nó atual. As operações no Map, em uma situação ideal, possuem uma complexidade algorítmica de O(1), pois estão acessando um array, e como você lembra, independente do número de elementos, as operações em um array possuem uma complexidade de O(1) . Mas isso é ideal. Quando a célula do array utilizada não está vazia (2) e já existem alguns nós nela, a complexidade algorítmica se transforma em O(N) linear, pois agora é necessário iterar sobre os elementos antes de encontrar o lugar certo. Não posso deixar de mencionar isto: começando com Java 8, se um nó de lista vinculada individualmente tiver mais de 8 elementos (colisões), ele se transformará em uma árvore binária. Nesse caso, a complexidade algorítmica não será mais O(N), mas O(log(N)) - isso é outro assunto, não é? HashMap é um assunto extenso e as pessoas gostam de fazer perguntas sobre ele em entrevistas. Portanto, aconselho você a entendê-lo detalhadamente (para que ricocheteie nos dentes). Pessoalmente, não tive uma entrevista sem perguntas do HashMap . Você pode encontrar um mergulho profundo no HashMap neste artigo . Por hoje é tudo, continua...