Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › Raisonner sur la complexité

Raisonner sur la complexité — entretien Coding & algorithmique

5 questions posées en entretien sur 3 sujets, avec la bonne réponse et son explication.

Complexité

Sur un million d'éléments, combien d'étapes pour une recherche binaire ?

  1. 1 000 000
  2. 1 000
  3. Environ 20 ✓
  4. Cela dépend de la valeur cherchée

Pourquoi : log₂(1 000 000) ≈ 20 : chaque étape élimine la moitié des candidats. C'est l'exemple qui fait comprendre pourquoi trier d'abord (O(n log n)) peut valoir le coup quand on cherche de nombreuses fois.

Niveau junior

Quelle affirmation sur `HashMap.get()` est exacte ?

  1. C'est toujours O(1)
  2. C'est O(1) en moyenne ; dans le pire cas O(n), ramené à O(log n) depuis Java 8 si les clés sont comparables ✓
  3. C'est O(log n)
  4. Cela dépend de la taille initiale

Pourquoi : Avec beaucoup de collisions, un seau dégénère. Depuis Java 8, un seau trop chargé est converti en arbre lorsque les clés implémentent Comparable. Savoir énoncer cette nuance distingue nettement d'une réponse récitée.

Niveau senior

Structures de données

Quelle structure pour trouver « la plus grande clé inférieure ou égale à x » ?

  1. HashMap
  2. TreeMap, avec floorKey(x) ✓
  3. ArrayList triée
  4. PriorityQueue

Pourquoi : TreeMap maintient ses clés ordonnées et offre floorKey, ceilingKey, higherKey et subMap en O(log n). Une HashMap ignore l'ordre de ses clés ; une ArrayList triée imposerait une recherche binaire manuelle et des insertions en O(n).

Niveau confirme

Rigueur

Pourquoi écrire `bas + (haut - bas) / 2` plutôt que `(bas + haut) / 2` ?

  1. C'est plus lisible
  2. Parce que `bas + haut` peut dépasser Integer.MAX_VALUE et devenir négatif ✓
  3. Parce que la division est plus rapide
  4. Les deux sont strictement équivalents

Pourquoi : Avec des index proches de 2 milliards, la somme déborde et l'index calculé sort du tableau. Ce bug a subsisté des années dans des bibliothèques standard — c'est pour cela qu'il est devenu un classique d'entretien.

Niveau senior

Sans compilateur, comment vérifier un algorithme avant de le proposer ?

  1. Le relire deux fois attentivement
  2. Le dérouler à la main sur trois éléments, en notant les variables à chaque tour ✓
  3. Ajouter des logs
  4. Écrire des tests unitaires

Pourquoi : La relecture voit ce qu'on voulait écrire. Le déroulé manuel révèle les erreurs de décalage et les invariants faux — et, fait à voix haute, il montre à l'examinateur exactement comment vous raisonnez.

Niveau confirme

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