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 ?
- java.util.Stack
- ArrayDeque, via l'interface Deque ✓
- LinkedList
- 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é ?
- Quand on le retire de la file
- Quand on l'ajoute à la file ✓
- À la fin du parcours
- 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 ?
- Un tas max de taille K
- Un tas min de taille K ✓
- Un tas max de taille n
- 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é ?
- Oui, toujours
- Non : seule la tête est garantie ; l'itérateur parcourt le tableau interne du tas ✓
- Oui, si le comparateur est fourni
- 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