Explorando perguntas e respostas de uma entrevista de emprego para um cargo de desenvolvedor Java. Parte 9

Ser programador não é fácil. Sempre há algo novo para aprender. E, como em qualquer outra empreitada, o mais difícil é começar, dar o primeiro passo em direção ao seu objetivo. Mas como você já está aqui e lendo este artigo, você concluiu a primeira etapa. Isso significa que agora você precisa se mover deliberadamente em direção ao seu objetivo, sem desacelerar ou desviar para o lado. Presumo que seu objetivo seja se tornar um desenvolvedor Java ou aprimorar seu conhecimento se você já for um desenvolvedor. Nesse caso, vamos continuar abordando uma extensa lista de perguntas da entrevista para desenvolvedores Java. Vamos continuar!

Coleções

84. Conte-nos sobre iteradores e como eles são usados

Coleções é um tópico favorito em qualquer entrevista com desenvolvedor Java. Ao responder perguntas sobre a hierarquia da coleção, os candidatos costumam dizer que ela começa com a interface da Coleção . Mas não é assim. Existe outra interface um nível acima: Iterable . Esta interface consiste no método iterator() , que permite acessar o objeto Iterator da coleção atual. E o que exatamente é esse objeto Iterator ? O objeto Iterator fornece a capacidade de percorrer uma coleção e iterar sobre seus elementos, e o usuário não precisa conhecer os detalhes específicos de implementação da coleção. Ou seja, é uma espécie de ponteiro para os elementos da coleção, como se estivesse espiando um deles. O iterador possui métodos como:

• hasNext() — retorna verdadeiro se a iteração tiver outro elemento (este método permite saber quando você chegou ao final da coleção);

• next() — retorna o próximo item da iteração. Se não houver, uma NoSuchElementException será lançada. Isso significa que antes de usar este método, é melhor usar o método hasNext() para garantir que exista um próximo elemento;

• remove() — remove da coleção o último elemento recebido usando o método next() . Se next() nunca tiver sido chamado, então chamar remove() fará com que uma IllegalStateException seja lançada;

• forEachRemaining(<Consumer>) — executa a ação passada em cada elemento da coleção (este método apareceu em Java 8).

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

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á o seguinte: Isso significa que os elementos foram removidos com sucesso. Depois de obter um iterador, você pode usar um método para exibir todos os elementos na tela:

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

Mas uma vez feito isso, o iterador se torna inadequado para uso posterior: ele percorreu toda a lista e um iterador comum não possui métodos para iterar de trás para frente. E isso é uma boa continuação para uma discussão sobre LinkedList , especificamente, seu método listIterator() , que retorna um tipo aprimorado de iterador: ListIterator . Além dos métodos de um iterador regular (padrão), esse tipo possui o seguinte:

• add(<Element>) — adiciona um novo elemento à lista;

• hasPrevious() — retorna verdadeiro se houver um elemento localizado antes do próximo elemento (se houver um elemento anterior);

• nextIndex() — retorna o índice do próximo elemento;

• previous() — retorna o elemento anterior (aquele antes do próximo elemento);

• previousIndex retorna o índice do elemento anterior.

• set(<Element>) — substitui o último elemento retornado por next() ou previous() .

Como você pode ver, este iterador tem funcionalidades muito mais interessantes: permite caminhar em ambas as direções e oferece uma liberdade considerável ao trabalhar com elementos. Você também deve saber que quando as pessoas falam sobre iteradores, às vezes elas se referem ao próprio padrão de design.

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

Existem duas hierarquias de coleção em Java. A primeira hierarquia é a hierarquia de Coleções, que possui a seguinte estrutura: Está dividida nas seguintes subcoleções:

• Conjunto é uma interface que descreve um conjunto, uma estrutura de dados que contém elementos únicos não ordenados (não repetidos). Esta interface possui algumas 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. Os objetos em uma lista podem ser inseridos e removidos pelo seu índice na lista (como um array, mas com redimensionamento dinâmico). Essa interface também possui algumas implementações padrão: ArrayList , Vector ( obsoleto e não usado de fato ) e LinkedList .

• Fila é uma interface que descreve uma estrutura de dados que armazena itens em uma fila First In First Out (FIFO) . Essa interface possui as seguintes implementações padrão: LinkedList (isso mesmo, ela também implementa Queue ) e PriotityQueue .

A segunda hierarquia de coleção é a hierarquia do Mapa , que possui a seguinte estrutura: Esta hierarquia de coleção não tem divisões em subcoleções (uma vez que a própria hierarquia do Mapa é uma espécie de subcoleção que se destaca por si só). As implementações padrão do Map são Hashtable (obsoleto), LinkedHashMap e TreeMap . Na prática, quando as pessoas perguntam sobre Collections , geralmente se referem a ambas as hierarquias.

86. Qual é a estrutura interna de um ArrayList?

Um ArrayList é como um array, mas pode se expandir dinamicamente. O que isso significa? Nos bastidores, ArrayList usa um array comum, ou seja, ele armazena seus elementos em um array interno cujo tamanho padrão é 10 células. Quando o array interno estiver cheio, um novo array será criado. O tamanho da nova matriz é determinado por esta fórmula:

<size of the current array> * 3 / 2 + 1

Portanto, se o tamanho do nosso array for 10, o tamanho do novo será: 10 * 3/2 + 1 = 16. Em seguida, todos os valores do array original (antigo) serão copiados para ele usando o built-in Método System.arraycopy() e o array original é excluído. Resumindo, é assim que ArrayList implementa o redimensionamento dinâmico. Vamos considerar os métodos ArrayList mais populares : 1. add(<Element>) — adiciona um elemento ao final do array (na última célula vazia), após verificar primeiro se há uma célula disponível no array. Caso contrário, um novo array é criado e os elementos são copiados para ele. A complexidade de tempo desta operação é O(1). Existe um método add(<Index>, <Elelement>) semelhante . Adiciona um elemento não ao final da lista (array), mas à célula específica indicada pelo índice que entrou como argumento. Neste caso, a complexidade do tempo irá variar dependendo de onde você adiciona:

• se a adição estiver próxima do início da lista, então a complexidade de tempo 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, então será O(N/2), pois só precisamos deslocar metade dos itens da lista uma célula para a direita.

Ou seja, a complexidade de tempo deste método varia de O(1) a O(N), dependendo de onde o elemento está inserido. 2. set(<Index>, <Element>) — grava um elemento na posição especificada na lista. Se um elemento já estiver presente naquela posição, o método o substituirá. A complexidade de tempo desta operação é O(1), pois não envolve nenhuma operação de deslocamento: apenas usamos o índice para calcular o endereço da célula no array, que tem complexidade O(1), e então escrevemos o novo elemento . 3. remove(<index>) — remove um elemento por seu índice no array interno. Ao remover um item que não está no final da lista, todos os itens à direita do excluído devem ser deslocados uma célula para a esquerda para preencher a lacuna resultante da exclusão. Conseqüentemente, a complexidade de tempo será a mesma de add(<Index>, <Element>) quando um elemento é adicionado no meio: O(N/2). Afinal, você precisa deslocar metade dos elementos uma célula para a esquerda. E se estamos falando do começo, então O(N). Ou se estiver no final, então O(1), já que você não precisa mover nada.

87. Qual é a estrutura interna de um LinkedList?

Um ArrayList contém elementos no array interno, mas um LinkedList os armazena em uma lista duplamente vinculada. Isso significa que cada elemento contém um link para o elemento anterior e para o próximo elemento. O primeiro elemento não está vinculado a um elemento anterior (afinal, é o primeiro). Também é considerado o topo da lista, e o objeto LinkedList possui uma referência direta a ele. Da mesma forma, o último elemento não possui o próximo elemento, pois é o final da lista. O objeto LinkedList também faz referência a ele diretamente. Isso significa que a complexidade de tempo de acesso ao início ou ao fim de uma lista é O(1). Em ArrayList , se a lista crescer, o array interno aumentará. Aqui tudo é mais fácil: adicionar uma referência é tão simples quanto alterar alguns links. Vejamos alguns dos métodos LinkedList mais usados: 1. add(<Element>) — adiciona um elemento ao final da lista, ou seja, após o último elemento (5), um link para o novo elemento será adicionado como próximo . A referência anterior no novo elemento apontará para o elemento (5) que agora o precede na lista. A complexidade de tempo desta operação é O(1), já que só precisamos de link para o último elemento, e como você deve lembrar, o objeto LinkedList tem uma referência direta à cauda, ​​e acessá-lo tem complexidade de tempo constante mínima. 2. add(<Index>, <Element>) — adiciona um elemento por índice. Ao adicionar um elemento, digamos, no meio de uma lista, este método primeiro itera sobre os elementos da cabeça e da cauda (em ambas as direções) até que o local desejado seja encontrado. Se adicionarmos um elemento entre o terceiro e o quarto elemento (na imagem acima), o próximo link do terceiro elemento apontará para o novo elemento. E o anterior do elemento recém-adicionado apontará para o terceiro. Por sua vez, o link anterior do antigo quarto elemento apontará agora para o novo elemento, e o próximo link do novo elemento apontará para o novo quarto elemento: A complexidade de tempo deste método depende do índice do novo elemento:

• se estiver próximo do início ou do final, a operação se aproximará de O(1), pois não será realmente necessário iterar sobre os elementos;
• se estiver próximo do meio, então teremos O(N/2), pois o método irá pesquisar desde o início e o final ao mesmo tempo até que o elemento desejado seja encontrado.

3. set(<Index>, <Element>) — grava um elemento na posição especificada na lista. A complexidade de tempo desta operação variará de O(1) a O(N/2), novamente dependendo de quão próximo o novo elemento está da cabeça, cauda ou meio. 4. remove(<index>) — remove um elemento da lista fazendo com que o elemento anterior ao excluído ( anterior ) agora se refira ao elemento após o excluído ( próximo ). E vice-versa, ou seja, o elemento após o excluído agora se refere ao anterior ao excluído: Este processo é o oposto de adicionar por índice ( add(<Index>, <Element>) ).

88. Qual é a estrutura interna de um HashMap?

Esta pode ser uma das perguntas de entrevista mais populares para candidatos a desenvolvedores Java. Um HashMap funciona com pares chave-valor . Como eles são armazenados dentro do próprio HashMap ? Um HashMap possui uma matriz interna de nós:

Node<K,V>[] table

Por padrão, o tamanho do array é 16 e dobra cada vez que é preenchido com elementos (ou seja, quando LOAD_FACTOR é atingido ; ele especifica o limite de quão cheio o array pode ficar - por padrão, é 0,75 ) . Cada um dos nós armazena um hash da chave, a chave, um valor e uma referência ao próximo elemento: Neste caso, a "referência ao próximo elemento" significa que estamos lidando com uma lista vinculada individualmente, onde cada elemento contém um link para o próximo. Em outras palavras, um HashMap armazena seus dados em uma série de listas vinculadas individualmente. Mas deixe-me dizer imediatamente que quando uma célula do array da tabela tem uma lista vinculada individualmente 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 método obtém o hashCode() da chave . Isso implica que para que um HashMap funcione corretamente, as chaves usadas devem ser classes que substituem esse método. Este código hash é então usado no método hash() interno para determinar um índice de alguma célula dentro da matriz da tabela. O índice resultante nos permite acessar uma célula específica do array da tabela. Temos dois casos aqui:

1. A célula está vazia — neste caso, o novo valor do Node está armazenado nela.
2. A célula não está vazia — neste caso, os valores das chaves são comparados. Se forem iguais, o novo valor do Nó substitui o antigo; se não for igual, então o próximo é acessado e sua chave é comparada... E assim por diante, até que o novo valor substitua algum valor antigo ou cheguemos ao final da lista vinculada individualmente e então armazenemos o novo valor lá como o último elemento.

Ao procurar um elemento por chave (usando o método get(<key>) ), o hashCode() da chave é calculado e, em seguida, seu índice dentro do array é calculado usando hash() . O número resultante é o índice de uma célula na matriz da tabela , que então pesquisamos iterando nos nós e comparando a chave do nó desejado com a chave do nó atual. Idealmente, as operações Map têm uma complexidade algorítmica de O(1), porque estamos acessando um array, e, como você deve se lembrar, é O(1), independentemente do número de elementos que ele contém. Mas não estamos lidando com o caso ideal. Quando a célula não está vazia (2) e já armazena alguns nós, então a complexidade algorítmica passa a ser O(N) (linear), pois agora é necessário iterar sobre os elementos antes de encontrar o lugar certo. Não posso deixar de mencionar que a partir do Java 8, se um nó na forma de uma lista vinculada individualmente tiver mais de 8 elementos (colisões), ele será convertido em uma árvore binária. Nesse caso, a complexidade algorítmica não é mais O(N), mas O(log(N)) — e isso é outra questão, não é? HashMap é um tópico importante e as pessoas adoram fazer perguntas sobre ele em entrevistas de emprego. Então, sugiro que você conheça isso como a palma da sua mão. Pessoalmente, nunca tive uma entrevista que não incluísse perguntas sobre o HashMap . Isso é tudo por hoje. Continua...