Les entretiens techniques comportent souvent des questions qui testent votre compréhension des collections, en particulier des HashMaps. Un défi courant consiste à compter les occurrences d'éléments dans une liste. Cette question aide les enquêteurs à évaluer votre capacité à gérer efficacement l'agrégation des données et à éviter les pièges comme NullPointerException.

Si vous êtes nouveau sur HashMaps, vous souhaiterez peut-être consulter mon Cracking the Basics of HashMap : Key Concepts for Java Developers pour obtenir des connaissances de base avant de vous plonger dans cet article.

Dans cet article, nous allons :

• Explorez l'énoncé du problème en détail.
• Résolvez-le avec deux approches : une solution if-else traditionnelle et la méthode getOrDefault().
• Discutez de la complexité temporelle et spatiale des deux implémentations.
• Une comparaison des deux solutions, indiquant quand les utiliser.

Énoncé du problème

Vous recevez une liste d'entiers et votre tâche consiste à renvoyer chaque nombre unique ainsi que le nombre de ses occurrences dans la liste. Il s'agit d'un problème typique qui teste votre compréhension de la structure de données HashMap et votre capacité à la mettre en œuvre efficacement.

Voici un exemple :

Saisir:

[1, 2, 3, 5, 2, 1]

Sortir:

{1=2, 2=2, 3=1, 5=1}

Si la liste d'entrée est nulle ou vide, le résultat doit renvoyer un HashMap vide.

Solution 1 : Approche traditionnelle utilisant if-else

Dans cette solution, nous vérifions manuellement si le HashMap contient déjà le numéro comme clé. Si c'est le cas, nous incrémentons la valeur ; si ce n'est pas le cas, nous insérons la clé avec une valeur de 1.

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class CountNumbers {

    private HashMap getCount(List list) {
        // Initialize HashMap to store number counts
        HashMap map = new HashMap();

        // To avoid NullPointerException in case of a null list
        if (list != null) {
           // Iterate through each number in the list
            for (int num : list) {
                // If first occurrence, add number with count 1
                if (!map.containsKey(num)) {
                    map.put(num, 1);
                } else { // If the number already exists, increment its count by 1
                    map.put(num, map.get(num)   1);
                }
            }
        }
        return map;
    }

    public static void main(String[] args) {
        // Using ArrayList Parameterized Constructor with Collection as argument
        List numbers = new ArrayList(Arrays.asList(1, 2, 3, 5, 2, 1));

        CountNumbers nums = new CountNumbers();
        System.out.println(nums.getCount(null)); // Result -> {}
        System.out.println(nums.getCount(numbers)); // Result -> {1=2, 2=2, 3=1, 5=1}
    }
}

Explication

1. Si la liste est nulle : nous évitons une NullPointerException en vérifiant si la liste est nulle avant d'itérer.
2. Itération sur la liste : Pour chaque numéro, s'il existe déjà dans le HashMap, on incrémente sa valeur. Sinon, on l'insère avec la valeur 1.

Complexité temporelle et spatiale

• Complexité temporelle :

  • O(n) – Nous parcourons la liste une fois, où n est le nombre d'éléments.
  • Chaque opération HashMap (put et get) prend O(1) en moyenne, ce qui rend la complexité temporelle globale O(n).

• Complexité spatiale : O(n) – Dans le pire des cas, tous les nombres sont uniques et stockés dans le HashMap.

Solution 2 : approche optimisée à l’aide de la méthode getOrDefault()

La classe Java HashMap fournit une manière plus propre et plus concise de gérer ce problème avec la méthode getOrDefault(). Il élimine le besoin d'une logique if-else en renvoyant une valeur par défaut si la clé n'est pas trouvée dans la carte.

Définition de la méthode

V getOrDefault(Object key, V defaultValue)

• Paramètres :

  • key : La clé dont la valeur associée doit être renvoyée.
  • defaultValue : valeur à renvoyer si la carte ne contient aucun mappage pour la clé.

• Returns : la valeur à laquelle la clé spécifiée est mappée, ou defaultValue si la carte ne contient aucun mappage pour la clé.

Pour plus d'informations, vous pouvez consulter le Javadoc officiel pour HashMap.

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class CountNumbers {

    private HashMap getCount(List list) {
        // Initialize HashMap to store number counts
        HashMap map = new HashMap();

        // To avoid NullPointerException in case of a null list
        if (list != null) {
            // Iterate through each number in the list
            for (int num : list) {
                // Cleaner solution using getOrDefault()
                map.put(num, map.getOrDefault(num, 0)   1);
            }
        }
        return map;
    }

    public static void main(String[] args) {
        // Using ArrayList Parameterized Constructor with Collection as argument
        List numbers = new ArrayList(Arrays.asList(1, 2, 3, 5, 2, 1));

        CountNumbers nums = new CountNumbers();
        System.out.println(nums.getCount(null)); // Result -> {}
        System.out.println(nums.getCount(numbers)); // Result -> {1=2, 2=2, 3=1, 5=1}
    }
}

Explication

1. Utilisation de getOrDefault() : Cette méthode renvoie la valeur de la clé si elle existe. Sinon, il renvoie la valeur par défaut fournie (dans ce cas, 0).
2. Insertion et incrémentation : le code ajoute directement 1 à la valeur par défaut, éliminant ainsi le besoin d'une logique if-else.

Avantages de getOrDefault()

• Code de nettoyage : réduit le passe-partout en supprimant le besoin de if-else.
• Même complexité : O(n) pour le temps et l'espace.

Comparaison des deux approches

Conclusion

Les deux solutions donneront le même résultat, mais l'utilisation de getOrDefault() rend le code plus concis et lisible. Cette question est une question courante lors des entretiens, car elle évalue votre compréhension de HashMaps, de l'itération et de la gestion des valeurs nulles. Il est également étroitement lié aux problèmes liés au comptage de fréquence et à l'agrégation de données.

Si vous avez trouvé cet article utile, assurez-vous de consulter également les autres articles de la série Collections Framework Essentials !

Articles connexes

• Principes de base de Java

• Les essentiels de l'entretien de tableau

• L'essentiel de la mémoire Java

Bon codage !