Ce qu'ils pourraient demander lors d'un entretien : Structures de données en Java. Partie 1

Bonjour! Quel que soit votre point de vue, vous ne pouvez pas devenir développeur sans réussir un entretien d’entrée technique. Il existe de nombreuses technologies liées à Java, et il est impossible de tout apprendre. En règle générale, quelque chose de spécifique est demandé lors des entretiens uniquement s'ils recherchent un développeur ayant une bonne expérience dans un cadre important pour le projet. Si tel est le cas, vous serez pourchassés à toute vitesse dans ce cadre, vous n’en doutez pas. Mais nous parlons maintenant de la base que tout développeur Java devrait connaître. À propos de ce savoir classique à partir duquel tout commence. Aujourd'hui, je voudrais aborder l'un des sujets fondamentaux de toute interview : les structures de données en Java . Alors, au lieu de tourner autour du pot, commençons. Trouvez une liste de questions qui pourraient vous être posées sur ce sujet lors d'un entretien.

1. Parlez-nous un peu des structures de données

Une structure de données est un magasin de données contenant des informations structurées d'une certaine manière. Ces structures sont conçues pour la réalisation efficace de certaines opérations. Des exemples typiques de structures de données sont :

• des tableaux,
• des piles,
• les files d'attente,
• listes associées,
• des graphiques,
• des arbres,
• arbres de préfixes,
• table de hachage.

Vous pouvez en savoir plus à leur sujet ici et ici . Les données sont un élément clé d'un programme et les structures permettent de stocker ces données sous une forme spécifique et clairement structurée. Quoi que fasse votre application, cet aspect y sera toujours présent : s'il s'agit d'une boutique en ligne, alors les informations sur les produits seront stockées, s'il s'agit d'un réseau social, les données sur les utilisateurs et les fichiers, etc.

2. Que savez-vous des tableaux ?

Un tableau est un conteneur permettant de stocker des valeurs du même type, dont le nombre a été précisé à l'avance. Un exemple de création d'un tableau avec des valeurs de chaîne :

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

Lors de la création d'un tableau, la mémoire est allouée pour tous ses éléments : plus il y a de cellules pour les éléments initialement spécifiées, plus de mémoire sera allouée. Si un tableau vide avec un certain nombre de cellules est créé, tous les éléments du tableau se verront attribuer des valeurs par défaut. Par exemple:

int[] arr = new int[10];

Ainsi, pour un tableau avec des éléments de type booléen , les valeurs initiales ( par défaut ) seront false , pour des tableaux avec des valeurs numériques - 0, avec des éléments de type char - \u0000 . Pour un tableau de type de classe (objets) - null (pas de chaînes vides - "" mais spécifiquement null ). Autrement dit, dans l'exemple ci-dessus, toutes les valeurs du tableau arr seront 0 jusqu'à ce qu'elles soient directement spécifiées. Contrairement aux collections, les tableaux ne sont pas dynamiques. Une fois qu'un tableau d'une certaine taille est déclaré, la taille elle-même ne peut plus être modifiée. Pour ajouter un nouvel élément à un tableau, vous devez créer un nouveau tableau plus grand et y copier tous les éléments de l'ancien (c'est ainsi que fonctionne ArrayList). Il y a un point que tout le monde ne connaît pas et sur lequel on peut assez bien se rendre compte. Il existe deux types de variables en Java : les types simples et les références à des objets à part entière. Parmi ces éléments, lesquels sont des tableaux ? Par exemple, ici :

int[] arr = new int[10];

Il semble que tout soit simple - ce sont 10 éléments int . Alors, on peut dire que c'est un type simple ? Peu importe comment c'est. En Java, les tableaux sont des objets, sont créés dynamiquement et peuvent être affectés à des variables de type Objet. Toutes les méthodes de la classe Object peuvent être appelées sur un tableau. On peut donc même écrire :

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

Lors de la sortie vers la console, vous pourriez obtenir quelque chose comme : En savoir plus sur les fonctionnalités des tableaux en Java dans cet article sur Java Array . Pour consolider vos connaissances, vous pouvez résoudre plusieurs problèmes de cette collection .

3. Expliquer la hiérarchie des collections

Les collections sont utilisées dans les situations où vous avez besoin de flexibilité lorsque vous travaillez avec des données. Les collections peuvent ajouter un élément, supprimer un élément et effectuer de nombreuses autres opérations. Il existe de nombreuses implémentations différentes en Java, et il nous suffit de choisir la bonne collection pour la situation actuelle. Généralement, lorsque vous mentionnez l' interface Collection , il vous est demandé de lister certaines de ses implémentations et sa relation avec Map . Eh bien, découvrons-le. Ainsi, Collection et Map sont deux hiérarchies différentes pour les structures de données. À quoi ressemble la hiérarchie Collection : L' interface Collection est le lien supérieur clé avec une liste de méthodes de base, à partir de laquelle proviennent trois types de base de structures de données - Set , List , Queue . Set<T> est une interface qui représente une collection d'objets dans laquelle chaque objet est unique. List<T> est une interface qui représente une séquence ordonnée d'objets appelée liste. Queue<T> est une interface responsable des structures organisées en file d'attente (stockage séquentiel des éléments). Comme mentionné précédemment, Map est une hiérarchie distincte : Map<K, V> est une interface représentant un dictionnaire dans lequel les éléments sont contenus sous forme de paires clé-valeur. De plus, toutes les clés (K) sont uniques au sein de l' objet Map . Ce type de collection permet de retrouver plus facilement un élément si l'on connaît la clé - l'identifiant unique de l'objet.

4. Que savez-vous de Seth ?

Comme indiqué précédemment, cette collection comporte de nombreux éléments uniques. En d’autres termes, le même objet ne peut pas apparaître plus d’une fois dans un Java Set . Je voudrais également souligner que nous ne pouvons pas extraire un élément d' un Set par numéro (index) - uniquement par force brute. L'important est que différentes implémentations de Set ont différentes manières de structurer les données. Nous examinerons plus en détail des implémentations spécifiques. Ainsi, les principales implémentations de Set : HashSet est un ensemble basé sur une table de hachage, qui à son tour facilite la recherche. Utilise une fonction de hachage qui améliore les performances lors des recherches et des insertions. Quel que soit le nombre d'éléments, en général, l'insertion et la recherche (parfois la suppression) sont effectuées dans un temps presque constant - O(1). Nous examinerons la fonction de hachage plus en détail un peu plus tard. Je voudrais également noter que le HashSet contient un HashMap , où toute la magie se produit. Voici un article détaillé sur HashSet en Java . LinkedHashSet - cette classe étend HashSet sans ajouter de nouvelles méthodes. Comme LinkedList , cette classe maintient une liste chaînée des éléments d'un ensemble dans l'ordre dans lequel ils ont été insérés. Cela vous permet d'organiser l'ordre nécessaire dans une implémentation Set donnée . La classe TreeSet crée un ensemble basé sur un arbre rouge-noir pour organiser la structure de stockage des éléments. En d’autres termes, dans un ensemble donné, nous pouvons trier les éléments par ordre croissant. Si nous utilisons des objets standard de la « boîte », par exemple Integer , alors nous n'avons rien à faire pour organiser l'ensemble des Integers par ordre croissant :

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

System.out.println(set);

Et dans la console, nous obtiendrons le résultat : Autrement dit, dans cet ensemble, les nombres sont stockés sous forme triée. Si nous utilisons des éléments String dans un TreeSet , ils seront triés, mais par ordre alphabétique. Et si nous avions une classe standard (personnalisée) ? Comment les objets de cette classe structureront- ils le TreeSet ? Si nous essayons d'attribuer un objet arbitraire à ce 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);

Nous recevrons une ClassCastException car le TreeSet ne sait pas comment trier les objets de ce type. Dans ce cas, nous avons besoin de notre objet personnalisé pour implémenter l' interface Comparable et sa méthode 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 + '\'' +
               '}';
   }
}

Comme vous l'avez remarqué, la méthode compareTo renvoie un int :

• 1 si l'objet actuel (cet) est considéré comme grand ;
• -1 si l'objet courant est considéré comme plus petit que celui venu en argument ;
• 0 si les objets sont égaux (nous ne l'utilisons pas dans ce cas).

Dans ce cas, notre TreeSet fonctionnera correctement et affichera le résultat : Une autre façon consiste à créer une classe de tri distincte qui implémente l' interface du comparateur et sa méthode de comparaison :

public class CatComparator implements Comparator {

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

Dans ce cas, pour l'utiliser, il faut définir un objet de cette classe au constructeur TreeSet :

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

Après cela, tous les objets de la classe Cat inclus dans le TreeSet seront triés à l'aide de la classe Cat Comparator . Vous pouvez en savoir plus sur Comparator et Comparable en Java à partir de cet article .

5. Parlez-nous de la file d'attente

La file d'attente est une interface responsable des structures organisées en file d'attente - une structure de données qui stocke les éléments de manière séquentielle. Par exemple, dans une file de personnes, la première personne à entrer sera celle qui est arrivée plus tôt que les autres, et la dernière sera celle qui est arrivée plus tard que tous les autres. Cette méthode est appelée FIFO , c'est-à-dire First in First Out . Les méthodes de file d'attente uniques se concentrent sur le travail avec le premier ou le dernier élément, par exemple :

• add et offer - insère un élément à la fin de la file d'attente,
• supprimer - récupère et supprime l'en-tête de cette file d'attente,
• peek - Récupère mais ne supprime pas l'en-tête de la file d'attente.

PARTIE 2