Accueil › Coding & algorithmique › Maps, Sets et regroupements
Maps, Sets et regroupements — entretien Coding & algorithmique
5 questions posées en entretien sur 4 sujets, avec la bonne réponse et son explication.
HashMap
Pourquoi faut-il redéfinir `hashCode` dès qu'on redéfinit `equals` ?
- Par convention de style
- Parce que la HashMap localise le seau par hashCode : deux objets égaux mais de hachages différents ne se retrouvent jamais ✓
- Parce que equals appelle hashCode
- Ce n'est requis que pour TreeMap
Pourquoi : L'objet est rangé dans le seau de son hashCode ; un objet égal avec un hachage différent est cherché dans un autre seau et reste introuvable — sans erreur, juste un null inexpliqué. Un record génère les deux correctement.
Niveau confirme
Que se passe-t-il si l'on modifie un objet servant de clé de HashMap après l'avoir inséré ?
- La Map se réorganise automatiquement
- L'entrée devient introuvable : son hashCode a changé, on la cherche dans le mauvais seau ✓
- Une ConcurrentModificationException est levée
- Rien, les clés sont copiées
Pourquoi : L'entrée reste physiquement dans la Map mais devient inaccessible par get. D'où la règle : les clés doivent être immuables — String, Integer, ou un record sans composant mutable.
Niveau senior
Regroupements
L'algorithme de vote de Boyer-Moore trouve l'élément majoritaire en O(1) espace. Que faut-il ajouter ?
- Rien, il est complet
- Un second passage pour vérifier que le candidat est bien majoritaire, sauf si l'énoncé garantit son existence ✓
- Un tri préalable
- Une HashMap de secours
Pourquoi : L'algorithme renvoie toujours un candidat, même quand aucun élément n'est majoritaire : sur [1,2,3] il renvoie 3. Le second passage est omis par la plupart des candidats — c'est précisément ce que l'examinateur vérifie.
Niveau senior
Sets
Quel est le problème de `for (String x : a) if (b.contains(x)) …` où `b` est une `ArrayList` ?
- Aucun
- `contains` sur une List est en O(n) : la boucle est donc en O(n·m), un O(n²) invisible ✓
- contains ne fonctionne pas sur les String
- Il faut trier b d'abord
Pourquoi : C'est la cause la plus fréquente d'un O(n²) accidentel : le code paraît linéaire. Convertir b en HashSet avant la boucle ramène chaque test à O(1), donc l'ensemble à O(n + m).
Niveau confirme
Maps ordonnées
Quelle structure pour « le plus grand palier inférieur ou égal à 3200 points » ?
- HashMap avec une boucle sur les clés
- TreeMap et floorEntry(3200) ✓
- LinkedHashMap
- PriorityQueue
Pourquoi : floorEntry répond en O(log n). Une HashMap ignore l'ordre de ses clés : il faudrait parcourir toutes les entrées à chaque requête. C'est la navigation — floor, ceiling, subMap — qui justifie le coût logarithmique du TreeMap.
Niveau confirme