Accueil › Coding & algorithmique › Tri, recherche et Streams
Tri, recherche et Streams — entretien Coding & algorithmique
3 questions posées en entretien sur 2 sujets, avec la bonne réponse et son explication.
Tri
Pourquoi `(a, b) -> a - b` est-il un mauvais comparateur d'entiers ?
- Il est moins lisible
- La soustraction peut déborder : le signe s'inverse sur de grandes valeurs ✓
- Il ne compile pas
- Il rend le tri instable
Pourquoi : Avec un grand positif et un grand négatif, la soustraction déborde et inverse l'ordre. Le comparateur passe tous les tests sur de petites valeurs et casse en production. `Integer::compare` ou `Comparator.comparingInt` sont sûrs.
Niveau junior
Que signifie « le tri d'objets du JDK est stable » ?
- Il ne lève jamais d'exception
- Il conserve l'ordre relatif des éléments considérés comme équivalents ✓
- Sa complexité est toujours la même
- Il ne consomme pas de mémoire supplémentaire
Pourquoi : Timsort est stable, ce qui permet de trier en plusieurs passes. Le tri de primitifs (quicksort double pivot) ne l'est pas — mais la question est sans objet, deux int égaux étant indiscernables.
Niveau confirme
Recherche binaire
Que renvoie `Arrays.binarySearch(new int[]{10,20,30}, 25)` ?
- -1
- 2
- -3, soit -(point d'insertion) - 1 ✓
- 0
Pourquoi : L'encodage négatif permet de distinguer « trouvé à l'index 0 » de « absent, insertion en 0 ». On retrouve le point d'insertion par -(retour) - 1.
Niveau confirme