Accueil › Coding & algorithmique › Tableaux et parcours
Tableaux et parcours — entretien Coding & algorithmique
4 questions posées en entretien sur 3 sujets, avec la bonne réponse et son explication.
Parcours
De nombreuses requêtes « somme des éléments entre i et j ». Quelle préparation ?
- Trier le tableau
- Construire un tableau de sommes préfixes : préparation O(n), puis chaque requête en O(1) ✓
- Une HashMap des sommes
- Recalculer à chaque requête
Pourquoi : Avec `p[0] = 0` et `p[i+1] = p[i] + t[i]`, la somme de t[i..j] vaut `p[j+1] - p[i]`. La case supplémentaire évite un cas particulier pour i = 0 — c'est la convention à adopter systématiquement.
Niveau confirme
Quel idiome pour supprimer ou déplacer des éléments d'un tableau en place ?
- Une boucle qui appelle `remove` sur chaque index
- Deux indices, un en lecture et un en écriture ✓
- Un tableau temporaire puis une copie
- Trier d'abord le tableau
Pourquoi : L'indice de lecture explore, celui d'écriture marque la prochaine position à remplir. O(n) temps, O(1) espace, et aucune position n'est décalée par erreur. C'est le motif de « déplacer les zéros », « supprimer les doublons d'un tableau trié » et de tout filtrage en place.
Niveau confirme
Deux pointeurs
Pourquoi la technique du lièvre et de la tortue détecte-t-elle un cycle ?
- Parce que le rapide atteint la fin en premier
- Parce que dans un cycle, le rapide gagne un pas sur le lent à chaque tour : ils se rencontrent nécessairement ✓
- Parce qu'elle compare les valeurs des nœuds
- Parce qu'elle mémorise les nœuds visités
Pourquoi : L'écart diminue d'une unité par itération jusqu'à s'annuler. Son intérêt face à un Set de visités : O(1) en espace au lieu de O(n). Sert aussi à trouver le milieu d'une liste en un seul parcours.
Niveau senior
Fenêtre glissante
Pour « le plus petit sous-tableau de somme ≥ S », où enregistrer le résultat ?
- Après la boucle while, quand la fenêtre est redevenue invalide
- À l'intérieur du while, tant que la fenêtre est encore valide ✓
- Avant d'étendre la fenêtre
- À la fin de l'algorithme
Pourquoi : « Plus courte » : on enregistre pendant que la fenêtre est valide, juste avant de la réduire encore. « Plus longue » : on enregistre après le while, une fois l'invariant rétabli. Inverser les deux produit un code qui compile et répond à une autre question.
Niveau confirme