Explorer les questions et réponses d'un entretien d'embauche pour un poste de développeur Java. Partie 9

Être programmeur n'est pas facile. Il y a toujours quelque chose de nouveau à apprendre. Et comme dans toute entreprise, le plus difficile est de se lancer, de faire le premier pas vers son objectif. Mais puisque vous êtes déjà ici et que vous lisez cet article, vous avez franchi la première étape. Cela signifie que vous devez maintenant vous déplacer délibérément vers votre objectif, sans ralentir ni vous écarter. Je suppose que votre objectif est de devenir développeur Java ou de renforcer vos connaissances si vous êtes déjà développeur. Si tel est le cas, continuons à aborder une longue liste de questions d'entretien pour les développeurs Java. Nous allons continuer!

Collections

84. Parlez-nous des itérateurs et de la façon dont ils sont utilisés

Les collections sont un sujet favori dans toute interview de développeur Java. Lorsqu'ils répondent aux questions sur la hiérarchie des collections, les candidats disent souvent que cela commence par l' interface Collection . Mais ce n’est pas le cas. Il existe une autre interface un niveau au-dessus : Iterable . Cette interface se compose de la méthode iterator() , qui vous permet d'accéder à l' objet Iterator de la collection actuelle. Et quel est exactement cet objet Iterator ? L' objet Iterator offre la possibilité de se déplacer dans une collection et de parcourir ses éléments, et l'utilisateur n'a pas besoin de connaître les détails spécifiques d'implémentation de la collection. En d'autres termes, c'est une sorte de pointeur vers les éléments de la collection, comme s'il jetait un coup d'œil à l'intérieur de l'un d'entre eux. L'itérateur a des méthodes telles que :

• hasNext() — renvoie true si l'itération comporte un autre élément (cette méthode vous permet de savoir quand vous avez atteint la fin de la collection) ;

• next() — renvoie l'élément suivant de l'itération. S'il n'y en a pas, une NoSuchElementException est levée. Cela signifie qu'avant d'utiliser cette méthode, il est préférable d'utiliser la méthode hasNext() pour vous assurer qu'un élément suivant existe ;

• remove() — supprime de la collection le dernier élément reçu à l'aide de la méthode next() . Si next() n'a jamais été appelé, alors l'appel de remove() entraînera la levée d' une IllegalStateException ;

• forEachRemaining(<Consumer>) — exécute l'action passée sur chaque élément de la collection (cette méthode est apparue dans Java 8).

Voici un petit exemple d'itération dans une liste et de suppression de tous ses éléments à l'aide des différentes méthodes d'itération que nous avons examinées :

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());

La console affichera ce qui suit : Cela signifie que les éléments ont été supprimés avec succès. Une fois que vous obtenez un itérateur, vous pouvez utiliser une méthode pour afficher tous les éléments à l’écran :

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

Mais une fois que nous faisons cela, l'itérateur devient impropre à une utilisation ultérieure : il a parcouru toute la liste et un itérateur ordinaire n'a aucune méthode pour itérer en arrière. Et cela constitue une belle transition vers une discussion sur LinkedList , en particulier sur sa méthode listIterator() , qui renvoie un type d'itérateur amélioré : ListIterator . En plus des méthodes d'un itérateur régulier (standard), ce type a les éléments suivants :

• add(<Element>) — ajoute un nouvel élément à la liste ;

• hasPrevious() — renvoie true s'il y a un élément situé avant l'élément suivant (s'il y a un élément précédent) ;

• nextIndex() — renvoie l'index de l'élément suivant ;

• previous() — renvoie l'élément précédent (celui avant l'élément suivant) ;

• previousIndex renvoie l'index de l'élément précédent.

• set(<Element>) — remplace le dernier élément renvoyé par next() ou previous() .

Comme vous pouvez le constater, cet itérateur a des fonctionnalités bien plus intéressantes : il permet de marcher dans les deux sens et offre une liberté considérable dans le travail avec les éléments. Il faut également savoir que lorsque les gens parlent d’itérateurs, ils font parfois référence au modèle de conception lui-même.

85. Quelle hiérarchie de collection existe dans Java Collection Framework ?

Il existe deux hiérarchies de collections en Java. La première hiérarchie est la hiérarchie Collection, qui a la structure suivante : Elle est divisée en sous-collections suivantes :

• Set est une interface qui décrit un ensemble, une structure de données qui contient des éléments uniques (non répétitifs) non ordonnés. Cette interface a quelques implémentations standards : TreeSet , HashSet et LinkedHashSet .

• List est une interface décrivant une structure de données qui stocke une séquence ordonnée d'objets. Les objets d'une liste peuvent être insérés et supprimés par leur index dans la liste (comme un tableau, mais avec un redimensionnement dynamique). Cette interface a également quelques implémentations standards : ArrayList , Vector ( obsolète et non réellement utilisé ) et LinkedList .

• La file d'attente est une interface décrivant une structure de données qui stocke les éléments dans une file d'attente Premier entré, premier sorti (FIFO) . Cette interface a les implémentations standards suivantes : LinkedList (c'est vrai, elle implémente également Queue ) et PriotityQueue .

La deuxième hiérarchie de collections est la hiérarchie Map , qui a la structure suivante : Cette hiérarchie de collections n'a pas de divisions en sous-collections (puisque la hiérarchie Map elle-même est en quelque sorte une sous-collection qui se distingue par elle-même). Les implémentations Map standard sont Hashtable (obsolète), LinkedHashMap et TreeMap . En pratique, lorsque les gens posent des questions sur les Collections , ils parlent généralement des deux hiérarchies.

86. Quelle est la structure interne d’une ArrayList ?

Une ArrayList est comme un tableau, mais elle peut se développer dynamiquement. Qu'est-ce que cela signifie? Sous le capot, ArrayList utilise un tableau ordinaire, c'est à dire qu'il stocke ses éléments dans un tableau interne dont la taille par défaut est de 10 cellules. Une fois le tableau interne plein, un nouveau tableau est créé. La taille du nouveau tableau est déterminée par cette formule :

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

Ainsi, si la taille de notre tableau est de 10, alors la taille du nouveau sera : 10 * 3 / 2 + 1 = 16. Ensuite, toutes les valeurs de l' (ancien) tableau d'origine y sont copiées à l'aide du haut- System.arraycopy() et le tableau d'origine est supprimé. En un mot, c'est ainsi qu'ArrayList implémente le redimensionnement dynamique. Considérons les méthodes ArrayList les plus populaires : 1. add(<Element>) — ajoute un élément à la fin du tableau (dans la dernière cellule vide), après avoir d'abord vérifié s'il y a une cellule disponible dans le tableau. Sinon, un nouveau tableau est créé et les éléments y sont copiés. La complexité temporelle de cette opération est O(1). Il existe une méthode add(<Index>, <Element>) similaire . Il ajoute un élément non pas à la fin de la liste (tableau), mais à la cellule spécifique indiquée par l'index entré en argument. Dans ce cas, la complexité temporelle variera selon l'endroit où vous ajoutez :

• si l'ajout est proche du début de la liste, alors la complexité temporelle sera proche de O(N), car tous les éléments situés à droite du nouveau devront être déplacés d'une cellule vers la droite ;
• si l'élément est inséré au milieu, alors ce sera O(N/2), puisque nous n'avons besoin que de décaler la moitié des éléments de la liste d'une cellule vers la droite.

Autrement dit, la complexité temporelle de cette méthode va de O(1) à O(N), selon l'endroit où l'élément est inséré. 2. set(<Index>, <Element>) — écrit un élément à la position spécifiée dans la liste. Si un élément est déjà présent à cette position, la méthode l'écrase. La complexité temporelle de cette opération est O(1), car elle n'implique aucune opération de décalage : nous utilisons simplement l'index pour calculer l'adresse de la cellule dans le tableau, qui a une complexité O(1), puis écrivons le nouvel élément . 3. remove(<index>) — supprime un élément par son index dans le tableau interne. Lors de la suppression d'un élément qui ne se trouve pas à la fin de la liste, tous les éléments à droite de celui supprimé doivent être décalés d'une cellule vers la gauche afin de combler l'espace résultant de la suppression. En conséquence, la complexité temporelle sera la même que pour add(<Index>, <Element>) lorsqu'un élément est ajouté au milieu : O(N/2). Après tout, vous devez décaler la moitié des éléments d'une cellule vers la gauche. Et si nous parlons du début, alors O(N). Ou si à la fin, alors O(1), puisque vous n'avez rien à déplacer.

87. Quelle est la structure interne d’une LinkedList ?

Une ArrayList contient des éléments dans le tableau interne, mais une LinkedList les stocke dans une liste doublement liée. Cela signifie que chaque élément contient un lien vers l' élément précédent et vers l' élément suivant . Le premier élément n’est pas lié à un élément précédent (après tout, c’est le premier). Il est également considéré comme la tête de liste et l' objet LinkedList y fait directement référence. De même, le dernier élément n’a pas l’élément suivant, puisqu’il s’agit de la queue de la liste. L' objet LinkedList y fait également référence directement. Cela signifie que la complexité temporelle de l'accès à la tête ou à la queue d'une liste est O(1). Dans ArrayList , si la liste s'agrandit, le tableau interne s'agrandit. Ici, tout est plus simple : ajouter une référence est aussi simple que de modifier quelques liens. Examinons quelques-unes des méthodes LinkedList les plus utilisées : 1. add(<Element>) — ajoute un élément à la fin de la liste, c'est-à-dire après le dernier élément (5), un lien vers le nouvel élément sera ajouté comme suit. . La référence précédente dans le nouvel élément pointera vers l'élément (5) qui le précède désormais dans la liste. La complexité temporelle de cette opération est O(1), puisque nous n'avons besoin que d'un lien vers le dernier élément, et comme vous vous en souviendrez, l'objet LinkedList a une référence directe à la queue, et y accéder a une complexité temporelle constante minimale. 2. add(<Index>, <Element>) — ajoute un élément par index. Lors de l'ajout d'un élément, disons au milieu d'une liste, cette méthode parcourt d'abord les éléments depuis la tête et la queue (dans les deux sens) jusqu'à ce que l'endroit souhaité soit trouvé. Si nous ajoutons un élément entre le troisième et le quatrième élément (dans l'image ci-dessus), alors le lien suivant du troisième élément pointera vers le nouvel élément. Et le précédent de l’élément nouvellement ajouté pointera vers le troisième. À son tour, le lien précédent de l'ancien quatrième élément pointera désormais vers le nouvel élément, et le lien suivant du nouvel élément pointera vers le nouveau quatrième élément : La complexité temporelle de cette méthode dépend de l'index du nouvel élément :

• s'il est proche de la tête ou de la queue, l'opération se rapprochera de O(1), puisqu'il ne sera pas réellement nécessaire d'itérer sur les éléments ;
• s'il est proche du milieu, alors nous aurons O(N/2), puisque la méthode recherchera à partir de la tête et de la queue en même temps jusqu'à ce que l'élément souhaité soit trouvé.

3. set(<Index>, <Element>) — écrit un élément à la position spécifiée dans la liste. La complexité temporelle de cette opération s'étendra de O(1) à O(N/2), encore une fois en fonction de la proximité du nouvel élément par rapport à la tête, à la queue ou au milieu. 4. remove(<index>) — supprime un élément de la liste en faisant en sorte que l'élément précédant celui supprimé ( previous ) fasse désormais référence à l'élément suivant celui supprimé ( next ). Et vice versa, c'est à dire que l'élément après celui supprimé fait désormais référence à celui avant celui supprimé : ce processus est l'opposé de l'ajout par index ( add(<Index>, <Element>) ).

88. Quelle est la structure interne d’un HashMap ?

C'est peut-être l'une des questions d'entretien les plus populaires à poser aux candidats développeurs Java. Un HashMap fonctionne avec des paires clé-valeur . Comment sont-ils stockés dans le HashMap lui-même ? Un HashMap possède un tableau interne de nœuds :

Node<K,V>[] table

Par défaut, la taille du tableau est de 16 et elle double à chaque fois qu'il est rempli d'éléments (c'est-à-dire lorsque le LOAD_FACTOR est atteint ; il spécifie le seuil de remplissage du tableau - par défaut, il est de 0,75 ). . Chacun des nœuds stocke un hachage de la clé, la clé, une valeur et une référence à l'élément suivant : Dans ce cas, la "référence à l'élément suivant" signifie que nous avons affaire à une liste à lien unique, où chaque élément contient un lien vers le suivant. En d’autres termes, un HashMap stocke ses données dans un tableau de listes à lien unique. Mais permettez-moi de dire tout de suite que lorsqu'une cellule du tableau contient une liste à lien unique composée de plusieurs éléments, ce n'est pas bon. Ce phénomène s'appelle une collision . Mais tout d’abord. Voyons comment une nouvelle paire est enregistrée à l'aide de la méthode put . Tout d’abord, la méthode récupère le hashCode() de la clé . Cela implique que pour qu'un HashMap fonctionne correctement, les clés que vous utilisez doivent être des classes qui remplacent cette méthode. Ce code de hachage est ensuite utilisé dans la méthode interne hash() pour déterminer l'index d'une cellule du tableau. L'index résultant nous permet d'accéder à une cellule spécifique du tableau. Nous avons ici deux cas :

1. La cellule est vide — dans ce cas, la nouvelle valeur Node y est stockée.
2. La cellule n'est pas vide — dans ce cas, les valeurs des clés sont comparées. S'ils sont égaux, la nouvelle valeur du nœud écrase l'ancienne ; s'il n'est pas égal, alors le suivant est accédé et sa clé est comparée... Et ainsi de suite, jusqu'à ce que la nouvelle valeur écrase une ancienne valeur ou que nous atteignions la fin de la liste à chaînage unique, puis y stockons la nouvelle valeur en tant que dernier élément.

Lors de la recherche d'un élément par clé (à l'aide de la méthode get(<key>) ), le hashCode() de la clé est calculé, puis son index dans le tableau est calculé à l'aide de hash() . Le nombre résultant est l'index d'une cellule du tableau , que nous recherchons ensuite en itérant sur les nœuds et en comparant la clé du nœud souhaité avec la clé du nœud actuel. Idéalement, les opérations Map ont une complexité algorithmique de O(1), car nous accédons à un tableau et, comme vous vous en souviendrez, est O(1), quel que soit le nombre d'éléments qu'il contient. Mais nous ne sommes pas confrontés au cas idéal. Lorsque la cellule n'est pas vide (2) et stocke déjà quelques nœuds, alors la complexité algorithmique devient O(N) (linéaire), car maintenant il faut itérer sur les éléments avant de trouver le bon endroit. Je ne peux m'empêcher de mentionner qu'à partir de Java 8, si un nœud sous la forme d'une liste à lien unique contient plus de 8 éléments (collisions), il est alors converti en arbre binaire. Dans ce cas, la complexité algorithmique n'est plus O(N), mais O(log(N)) — et c'est une toute autre affaire, n'est-ce pas ? HashMap est un sujet important et les gens adorent poser des questions à ce sujet lors des entretiens d'embauche. Je vous suggère donc de le connaître comme votre poche. Personnellement, je n'ai jamais eu d'entretien sans questions sur HashMap . C'est tout pour aujourd'hui. À suivre...