Formations — 1 037 leçons en français

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` ?

  1. Par convention de style
  2. Parce que la HashMap localise le seau par hashCode : deux objets égaux mais de hachages différents ne se retrouvent jamais ✓
  3. Parce que equals appelle hashCode
  4. 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é ?

  1. La Map se réorganise automatiquement
  2. L'entrée devient introuvable : son hashCode a changé, on la cherche dans le mauvais seau ✓
  3. Une ConcurrentModificationException est levée
  4. 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 ?

  1. Rien, il est complet
  2. Un second passage pour vérifier que le candidat est bien majoritaire, sauf si l'énoncé garantit son existence ✓
  3. Un tri préalable
  4. 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` ?

  1. Aucun
  2. `contains` sur une List est en O(n) : la boucle est donc en O(n·m), un O(n²) invisible ✓
  3. contains ne fonctionne pas sur les String
  4. 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 » ?

  1. HashMap avec une boucle sur les clés
  2. TreeMap et floorEntry(3200) ✓
  3. LinkedHashMap
  4. 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

S'entraîner sur ces questions, chronométré →