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

Oi! Quantas horas são necessárias para se tornar um mestre em alguma coisa? Muitas vezes ouvi algo como: "Para se tornar um mestre em qualquer coisa, você precisa gastar 10.000 horas nisso." É um número intimidante, não é? Ainda assim, me pergunto se isso é verdade. E estou constantemente tentando descobrir quantas horas já investi no domínio da arte da programação. E quando eu ultrapassar essa linha especial de 10.000 horas e me tornar um mestre, sentirei a diferença? Ou já cruzei essa linha há muito tempo sem perceber? De qualquer forma, você não precisa investir tanto tempo para se tornar um programador. O importante é usar seu tempo com sabedoria. Seu objetivo principal é conseguir uma entrevista. E nas entrevistas, os possíveis desenvolvedores de software são questionados primeiro sobre a teoria, então isso precisa ser um ponto forte. Na verdade, ao se preparar para uma entrevista, sua tarefa é descobrir todas as lacunas no conhecimento da teoria básica de Java e então preenchê-las. Hoje estou aqui para ajudá-lo a fazer exatamente isso, pois hoje continuaremos nossa análise das perguntas mais populares das entrevistas. Bem, vamos continuar!

89. Qual a diferença entre um ArrayList e um LinkedList?

Esta é uma das questões mais populares, juntamente com a questão sobre a estrutura interna de um HashMap . Nenhuma entrevista está completa sem ele, então sua resposta deve sair facilmente da sua língua. Além do óbvio (têm nomes diferentes), diferem na estrutura interna. Anteriormente, discutimos a estrutura interna de ArrayList e LinkedList , portanto não vou me aprofundar nos detalhes de implementação. Vou apenas lembrar que ArrayList é implementado usando um array interno cujo tamanho aumenta dinamicamente de acordo com esta fórmula:

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

Além disso, a implementação de uma LinkedList utiliza uma lista interna duplamente vinculada, ou seja, cada elemento possui uma referência aos elementos anteriores e seguintes, exceto os elementos do início e do final da lista. Os entrevistadores adoram fazer perguntas como esta: "Qual é melhor, ArrayList ou LinkedList ?" esperando pegar você. Afinal, se você disser que um ou outro é melhor, você deu a resposta errada. Em vez disso, você deve esclarecer a situação específica da qual está falando: acessar elementos por índice ou inserir no meio da lista. Então, dependendo da resposta, você pode explicar qual é o melhor. Descrevi anteriormente como ArrayList e LinkedList funcionam em cada situação. Vamos resumir isso colocando-os em uma linha para comparação: Adicionando um elemento (add)

1. Se um índice não for especificado, um novo item será adicionado automaticamente ao final de ambos os tipos de lista. Em um LinkedList , o novo elemento se tornará a nova cauda (apenas um par de referências será reescrito, então a complexidade algorítmica é O(1) ).

   O método add adiciona um elemento à última célula vazia do array ( O(1) ).

2. Adicionar um item por índice geralmente significa inseri-lo em algum lugar no meio da lista. Em um LinkedList , o método primeiro procurará o local desejado iterando sobre os elementos da cauda e da cabeça ( O(n/2) ) e então inserirá o valor substituindo as referências dos elementos em ambos os lados de onde o novo elemento é inserido ( O(1) ). A complexidade algorítmica geral desta operação será O(n/2) .

   Na mesma situação (adição por índice), um ArrayList encontra o local desejado ( O(1) ) e então desloca todos os elementos localizados à direita (incluindo o elemento já armazenado no índice especificado) para a direita em um (o que pode exigir a criação de uma nova matriz interna e a cópia de elementos para ela) ( O(n/2) ). A complexidade geral é O(n/2) .

3. Adicionar um elemento ao início de uma LinkedList é semelhante a adicionar um elemento ao final: o novo elemento se torna o novo cabeçalho ( O(1) ). Mas para um ArrayList, essa operação requer mover todos os elementos para a direita ( O(n) ).

O resultado final é que, para um LinkedList, a complexidade algorítmica variará de O(1) a O(n/2) . Outra observação é que quanto mais próxima a inserção estiver do final ou início da lista, mais rápida ela será. Para ArrayList , a complexidade algorítmica varia de O(1) a O(n) , e quanto mais próxima a inserção estiver do final da lista, mais rápida ela será. Configurando um elemento (conjunto) Esta operação grava um elemento na posição especificada na lista, substituindo qualquer elemento existente. Em um LinkedList , esta operação é semelhante à adição, pois o maior desafio aqui é encontrar a localização do elemento. O elemento existente é sobrescrito atualizando um par de referências, então novamente temos uma complexidade algorítmica que varia de O(1) a O(n/2) , dependendo da distância da posição desejada do final ou início da lista. Mas para um ArrayList , esta operação encontra a célula desejada por índice e escreve o novo elemento ali. Assim como a operação set, a busca por índice tem uma complexidade algorítmica de O(1) . Obtendo um elemento por índice (get) Obter um elemento de uma LinkedList segue o mesmo princípio de pesquisa usado em outras operações. A complexidade depende da distância do final ou do início, ou seja, varia de O(1) a O(n/2) . Conforme observado anteriormente, para um ArrayList , encontrar um elemento por índice na matriz interna tem uma complexidade de O(1) . Removendo um elemento por índice (remove) Para LinkedList , o mesmo princípio se aplica novamente. Primeiro o elemento é localizado e depois as referências são reescritas, os vizinhos do elemento excluído agora se referem entre si, eliminando as referências ao elemento excluído, que posteriormente será limpo pelo coletor de lixo. Em outras palavras, a complexidade algorítmica ainda é a mesma — varia de O(1) a O(n/2) . Para ArrayList , esta operação é mais como adicionar um novo elemento (add). Primeiro, o método encontra o elemento desejado ( O(1) ), remove-o e, em seguida, todos os elementos localizados à direita são deslocados um passo para a esquerda para fechar a lacuna criada pela remoção. A remoção de um elemento tem a mesma complexidade algorítmica que a operação de adição - de O(1) a O(n). Quanto mais próximo o elemento removido estiver do final da lista, menor será a complexidade algorítmica desta operação. E agora cobrimos todas as operações principais. Deixe-me lembrá-lo de que, ao comparar esses dois tipos de listas, você precisa esclarecer a situação específica em que estão sendo utilizadas. Só então você poderá responder de forma inequívoca à pergunta do entrevistador.

90. Qual a diferença entre um ArrayList e um HashSet?

Se pudéssemos comparar ArrayList e LinkedList operação por operação para determinar qual é o melhor, não acharíamos tão fácil fazer tal comparação entre ArrayList e HashSet , porque são coleções completamente diferentes. Você pode comparar uma sobremesa com outra, mas comparar uma sobremesa e um prato saboroso é um desafio – eles são dolorosamente diferentes. Ainda assim, tentarei apontar algumas das diferenças entre eles:

• ArrayList implementa a interface List enquanto HashSet implementa a interface Set .

• ArrayList permite acessar um elemento por índice: a operação get tem complexidade algorítmica O(1) , mas HashSet só permite acessar um elemento desejado por iteração, o que produz complexidade algorítmica variando de O(1) a O(n) .

• ArrayList permite elementos duplicados. Em um HashSet , todos os elementos são únicos: qualquer tentativa de adicionar um elemento que já esteja presente em um HashSet falhará (as duplicatas são verificadas por hashcode, daí o nome desta coleção).

• ArrayList é implementado usando um array interno, mas HashSet é implementado usando um HashMap interno .

• ArrayList mantém a ordem de inserção dos elementos, mas HashSet é um conjunto não ordenado e não mantém a ordem dos elementos.

• ArrayList permite qualquer número de valores nulos, mas você só pode adicionar um valor nulo a um HashSet (afinal, os elementos devem ser únicos).

91. Por que Java tem tantas implementações de array dinâmico diferentes?

Esta é mais uma questão filosófica. Poderíamos também perguntar por que eles apresentam tantas tecnologias novas e variadas? Por conveniência. E o mesmo se aplica a um grande número de implementações de array dinâmico. Nenhuma delas pode ser considerada a implementação melhor ou ideal. Cada um tem suas vantagens em situações específicas. Nosso trabalho é conhecer suas diferenças e seus pontos fortes/fracos para poder utilizar a coleção mais adequada para cada situação.

92. Por que Java tem tantas implementações diferentes de armazenamento de valores-chave?

Aqui a situação é a mesma das implementações de array dinâmico. Definitivamente, não há nenhum que seja universalmente melhor que os outros: cada um tem pontos fortes e fracos. E devemos aproveitar ao máximo os seus pontos fortes, é claro. Exemplo: o pacote concorrente, que possui muitas classes multithread, possui suas próprias coleções Concurrent . A classe ConcurrentHashMap tem uma vantagem sobre o HashMap padrão em termos de segurança ao trabalhar com dados em um ambiente multithread, mas isso tem o custo de um desempenho mais lento. E implementações que não são a melhor escolha em qualquer situação deixam gradualmente de ser utilizadas. Por exemplo: Hashtable , que foi originalmente planejado para ser um HashMap seguro para threads , foi esquecido e caiu em desuso, porque ConcurrentHashMap é ainda melhor que Hashtable ao trabalhar em um ambiente multithread.

93. Como classifico uma coleção de elementos?

A primeira coisa a dizer é que a classe que representa os elementos da coleção deve implementar a interface Comparable , que consiste no método compareTo . Ou você precisa de uma classe que implemente a interface Comparator , incluindo seu método compare . Ambos os métodos indicam como comparar objetos de um determinado tipo. Isso é fundamental durante a classificação, porque o algoritmo de classificação precisa entender qual princípio usar para comparar os elementos. Isso é feito principalmente implementando Comparable diretamente na classe que você deseja classificar. Usar o Comparator é menos comum. Suponha que você esteja usando uma classe de alguma biblioteca e ela não implemente Comparable , mas você precisa ordenar uma coleção de seus objetos. Como você não pode alterar o código desta classe (exceto estendendo-o), você pode escrever uma implementação de Comparator que indique como comparar objetos da classe. E mais um exemplo. Se você precisar classificar objetos do mesmo tipo de maneiras diferentes, poderá escrever várias implementações do Comparator para usar em situações diferentes. Como regra, muitas classes prontas para uso, por exemplo String , já implementam a interface Comparable . Isso significa que você não precisa se preocupar em como comparar essas classes. Você pode simplesmente ir em frente e usá-los. A primeira e mais óbvia maneira é usar a classe TreeSet ou TreeMap . Essas classes armazenam elementos em ordem de classificação com base no comparador implementado pelos elementos da classe. Não esqueça que o TreeMap classifica chaves, não valores. Se você usar Comparator em vez de Comparable , precisará passar um objeto Comparator para o construtor da coleção ao criá-la:

TreeSet treeSet = new TreeSet(customComparator);

Mas e se você tiver um tipo diferente de coleção? Como você classifica isso? Nesse caso, a segunda maneira da classe de utilitário Collections — o método sort() — é adequada. O método é estático, então tudo que você precisa é acrescentar o nome da classe e depois passar a lista para ser classificada. Por exemplo:

Collections.sort(someList);

Se você estiver usando uma implementação de Comparator em vez de Comparable , será necessário passá-lo como segundo argumento:

Collections.sort(someList, customComparator);

Esta operação irá alterar a ordem interna dos elementos da lista passada: a lista será ordenada utilizando o comparador. Observe que a lista passada deve ser mutável, caso contrário, o método falhará e lançará uma UnsupportedOperationException . Uma terceira opção é usar o método classificado da classe Stream , que classifica os elementos da coleção. Se estivermos usando Comparable :

someList = someList.stream().sorted().collect(Collectors.toList());

Se estivermos usando Comparator :

someList = someList.stream().sorted(customComparator).collect(Collectors.toList());

A quarta maneira é implementar manualmente um algoritmo de classificação, por exemplo, classificação por bolha ou classificação por mesclagem .

Classe de objeto. equals() e hashCode()

94. Dê uma breve descrição da classe Object em Java.

Na segunda parte da revisão já discutimos os métodos da classe Object . Aqui vou lembrá-lo de que a classe Object é ancestral de todas as classes em Java. Possui 11 métodos, que por sua vez são herdados por todas as classes.

95. Para que servem equals() e hashCode() em Java?

hashCode() é um método da classe Object que é herdado por todas as classes. Sua função é gerar um número que represente um objeto específico. Um exemplo desse método em ação pode ser encontrado em HashMap , onde ele é chamado em objetos-chave para obter o hashcode local, que determinará em qual bucket (célula do array interno) o par chave-valor será armazenado. este método é geralmente usado no método equals() como uma de suas principais formas de identificar objetos. equals() é um método da classe Object cuja função é comparar objetos e determinar se eles são iguais. Este método é usado em todos os lugares em que precisamos comparar objetos, porque o operador de comparação padrão == não é adequado para objetos, pois apenas compara referências de objetos.

96. Conte-nos sobre o contrato entre equals() e hashCode() em Java?

Primeiro, deixe-me dizer que para que os métodos equals() e hashCode() funcionem corretamente, eles devem ser substituídos corretamente. Suas novas implementações devem seguir estas regras:

• Objetos idênticos para os quais igual retorna verdadeiro devem ter os mesmos códigos hash.
• Objetos com os mesmos códigos hash não são necessariamente iguais.

Agora parece um bom lugar para fazer uma pausa até a próxima parte da revisão!