Structures de données : choisir la bonne
La moitié d'un exercice d'entretien se joue au moment où tu choisis la structure de données. Le bon choix rend le code court et rapide.
À retenir
- Tableau : ordre + accès par index en O(1), recherche en O(n).
- Set / Map : appartenance et comptage en O(1) moyen.
- Pile (LIFO) : parenthésage, retour arrière, DFS.
- File (FIFO) : parcours en largeur, traitement par lots.
- Arbre / graphe : hiérarchies et relations.
Le réflexe Map / Set
Dès qu'un énoncé parle de doublons, de fréquences ou de « déjà vu », pense Set ou Map. C'est le passage le plus rentable de O(n²) à O(n).
Pile et file en pratique
Une pile sert à mémoriser un contexte à revisiter (validation de parenthèses, DFS). Une file sert à explorer niveau par niveau (BFS, plus court chemin non pondéré).
// BFS avec une file
const file = [depart];
const vus = new Set([depart]);
while (file.length) {
const n = file.shift();
for (const v of voisins(n)) if (!vus.has(v)) { vus.add(v); file.push(v); }
}Justifier son choix
Le recruteur veut entendre : « j'utilise une Map parce que j'ai besoin de retrouver un élément en temps constant ». La justification vaut autant que le code.
Pièges fréquents
- Utiliser un tableau là où un Set suffit.
- Oublier que shift() sur un tableau JS est O(n).
- Comparer des objets par référence dans un Set.
Questions que le recruteur peut poser
- Pourquoi cette structure plutôt qu'une autre ?
- Que change un jeu de données trié ?
- Comment gères-tu les doublons ?