Formations — 1 037 leçons en français

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 ?

  1. Trier le tableau
  2. Construire un tableau de sommes préfixes : préparation O(n), puis chaque requête en O(1) ✓
  3. Une HashMap des sommes
  4. 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 ?

  1. Une boucle qui appelle `remove` sur chaque index
  2. Deux indices, un en lecture et un en écriture ✓
  3. Un tableau temporaire puis une copie
  4. 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 ?

  1. Parce que le rapide atteint la fin en premier
  2. Parce que dans un cycle, le rapide gagne un pas sur le lent à chaque tour : ils se rencontrent nécessairement ✓
  3. Parce qu'elle compare les valeurs des nœuds
  4. 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 ?

  1. Après la boucle while, quand la fenêtre est redevenue invalide
  2. À l'intérieur du while, tant que la fenêtre est encore valide ✓
  3. Avant d'étendre la fenêtre
  4. À 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

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