Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › Piles, files et tas

Piles, files et tas — entretien Coding & algorithmique

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

Piles

Quelle classe utiliser pour une pile en Java ?

  1. java.util.Stack
  2. ArrayDeque, via l'interface Deque ✓
  3. LinkedList
  4. PriorityQueue

Pourquoi : `Stack` hérite de `Vector` : méthodes synchronisées inutilement, et itération dans l'ordre inverse d'une pile — source de bugs. La documentation du JDK recommande explicitement ArrayDeque, plus rapide et sans verrouillage.

Niveau junior

Files

Dans un BFS, quand marquer un nœud comme visité ?

  1. Quand on le retire de la file
  2. Quand on l'ajoute à la file ✓
  3. À la fin du parcours
  4. Cela n'a pas d'importance

Pourquoi : Marquer au retrait permet à un même nœud d'entrer plusieurs fois dans la file s'il est atteignable par plusieurs voisins : mémoire qui explose sur un graphe dense, et distances potentiellement faussées. Marquer à l'ajout garantit une entrée unique.

Niveau senior

Tas

Pour garder les K plus grands éléments d'un flux, quel tas ?

  1. Un tas max de taille K
  2. Un tas min de taille K ✓
  3. Un tas max de taille n
  4. Un TreeSet

Pourquoi : Contre-intuitif mais essentiel : avec un tas **min**, la tête est le plus faible des K retenus, donc celui à évincer quand un meilleur arrive. O(n log K) temps et O(K) espace — on ne stocke jamais tout le flux, ce qui permet de traiter un flux infini.

Niveau senior

Parcourir une PriorityQueue avec un for donne-t-il les éléments dans l'ordre de priorité ?

  1. Oui, toujours
  2. Non : seule la tête est garantie ; l'itérateur parcourt le tableau interne du tas ✓
  3. Oui, si le comparateur est fourni
  4. Seulement pour les Integer

Pourquoi : Erreur très fréquente. Pour obtenir les éléments ordonnés, il faut appeler poll() jusqu'à épuisement — ce qui vide la file, donc travailler sur une copie si on en a encore besoin.

Niveau confirme

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