Le scénario qui fait perdre la plupart des candidats n’est pas le problème trop dur : c’est l’énoncé jamais vu devant lequel on ne sait pas par où commencer. On relit, on bloque, le chronomètre tourne. Pourtant, la grande majorité des exercices d’entretien se rangent dans une poignée de familles, et chaque famille a son schéma de résolution. Apprendre à reconnaître ces schémas, c’est transformer un problème inconnu en un problème déjà à moitié résolu.
Dans ce tutoriel, vous allez construire un classeur mental de quatre schémas qui couvrent une part énorme des exercices : les deux pointeurs, la fenêtre glissante, les pointeurs lent et rapide, et le parcours en largeur. Pour chacun, vous verrez l’indice qui le déclenche, le squelette de code, et un problème type résolu en Python. À la fin, vous saurez classer un énoncé en quelques secondes au lieu de partir tête baissée.
Ce que vous allez apprendre
- Identifier, à la lecture d’un énoncé, lequel des quatre schémas s’applique.
- Écrire le squelette de chaque schéma de mémoire, sans hésiter sur les bornes.
- Annoncer la complexité de chaque solution, et expliquer pourquoi elle bat la force brute.
- Éviter les pièges de bornes et de cas limites propres à chaque schéma.
Ce que vous allez construire
Au fil des étapes, vous résoudrez quatre problèmes représentatifs — une paire de somme cible, la plus longue sous-chaîne sans répétition, la détection de cycle dans une liste chaînée, et le comptage d’îlots sur une grille. Le vrai livrable n’est pas ces quatre solutions, mais le réflexe de classement que vous garderez pour tous les exercices suivants.
Prérequis
- Python 3.9 ou plus récent installé (les exemples utilisent une syntaxe standard).
- Être à l’aise avec les boucles, les listes et les dictionnaires.
- Connaître la notation big-O. Si ce n’est pas le cas, lisez d’abord le rappel sur la complexité.
- Temps estimé : environ 35 minutes.
Étape 1 — Adopter le réflexe : classer avant de coder
Avant la moindre ligne de code, prenez l’habitude de poser une question : « à quelle famille ce problème appartient-il ? » Cette seconde de recul oriente toute la suite et vous évite de réinventer une roue qui existe déjà. Les indices sont souvent dans le vocabulaire de l’énoncé. Un tableau trié invite aux deux pointeurs. Une sous-chaîne ou un sous-tableau contigu avec une contrainte invite à la fenêtre glissante. Une liste chaînée où l’on cherche un cycle ou un milieu invite aux pointeurs lent et rapide. Une grille, un réseau ou un plus court chemin en nombre d’étapes invite au parcours en largeur.
Gardez en tête que ces schémas ont un point commun : ils remplacent une exploration coûteuse par un balayage intelligent qui ne visite chaque élément qu’une fois ou deux. C’est exactement ce qui fait passer une solution du temps quadratique au temps linéaire. Voyons-les un par un.
Étape 2 — Les deux pointeurs : converger depuis les extrémités
Le schéma des deux pointeurs place un curseur à chaque extrémité d’un tableau trié, puis les rapproche selon une condition. Il s’applique dès qu’on cherche une paire, un encadrement ou une symétrie dans une séquence ordonnée. Prenons le problème classique : trouver dans un tableau trié deux nombres dont la somme vaut une cible.
La force brute testerait toutes les paires, en temps quadratique. Mais comme le tableau est trié, on peut être plus malin : si la somme des deux bouts est trop petite, on avance le curseur de gauche pour augmenter la somme ; si elle est trop grande, on recule celui de droite. Chaque élément n’est visité qu’une fois.
def paire_somme(nums, cible):
gauche, droite = 0, len(nums) - 1
while gauche < droite:
somme = nums[gauche] + nums[droite]
if somme == cible:
return (gauche, droite)
if somme < cible:
gauche += 1
else:
droite -= 1
return None
print(paire_somme([2, 7, 11, 15], 9)) # (0, 1)Le résultat affiché est (0, 1), car nums[0] + nums[1] vaut bien 9. La boucle s’arrête dès que les curseurs se croisent, ce qui donne un temps linéaire en O(n) et un espace constant en O(1). Le piège à connaître : ce schéma exige un tableau trié ; si l’énoncé fournit des données en vrac, soit on les trie d’abord, soit on bascule sur une table de hachage.
Étape 3 — La fenêtre glissante : un sous-tableau qui respire
La fenêtre glissante maintient un intervalle contigu — la fenêtre — qu’on étend par la droite et qu’on rétracte par la gauche selon une contrainte. Elle brille sur les problèmes de sous-chaîne ou de sous-tableau contigu : plus longue séquence sans répétition, plus petite fenêtre couvrant une condition, somme maximale d’une taille donnée. Le cas emblématique est la plus longue sous-chaîne sans caractère répété.
L’idée : on avance la borne droite caractère par caractère ; dès qu’un caractère déjà présent dans la fenêtre réapparaît, on déplace la borne gauche juste après sa précédente occurrence. Un dictionnaire mémorise la dernière position de chaque caractère.
def plus_longue_sans_repetition(s):
derniere_position = {}
debut = 0
meilleur = 0
for fin, caractere in enumerate(s):
if caractere in derniere_position and derniere_position[caractere] >= debut:
debut = derniere_position[caractere] + 1
derniere_position[caractere] = fin
meilleur = max(meilleur, fin - debut + 1)
return meilleur
print(plus_longue_sans_repetition("abcabcbb")) # 3Sur l’entrée "abcabcbb", la plus longue sous-chaîne sans répétition est "abc", de longueur 3, et c’est bien la valeur retournée. Chaque caractère est traité une seule fois, d’où un temps linéaire en O(n). Le piège classique : oublier de vérifier que la position mémorisée est bien dans la fenêtre courante (le test >= debut), sinon on rétracte la fenêtre à tort.
Il existe en réalité deux variétés de fenêtre glissante, et savoir les distinguer évite bien des erreurs. La fenêtre de taille fixe garde toujours la même largeur : on la fait glisser d’un cran en ajoutant l’élément qui entre et en retirant celui qui sort, comme dans le calcul d’une somme maximale sur k éléments. La fenêtre de taille variable, elle, s’étire et se contracte selon une condition : on étend la borne droite tant que la contrainte tient, et on rétracte la gauche dès qu’elle est violée. Le problème de la plus longue sous-chaîne sans répétition relève de cette seconde variété. Demandez-vous toujours, en lisant l’énoncé, si la taille de la fenêtre est imposée ou si elle dépend d’une condition : la réponse dicte la structure de votre boucle.
Étape 4 — Les pointeurs lent et rapide : détecter un cycle
Ce schéma fait avancer deux curseurs à des vitesses différentes dans une séquence chaînée. Le lent fait un pas, le rapide en fait deux. S’il existe un cycle, le rapide finit toujours par rattraper le lent ; s’il n’y en a pas, le rapide atteint la fin. C’est l’algorithme de détection de cycle de Floyd, et il se reconnaît dès qu’un énoncé parle de boucle dans une liste chaînée ou de recherche du milieu.
class Noeud:
def __init__(self, valeur):
self.valeur = valeur
self.suivant = None
def a_un_cycle(tete):
lent = rapide = tete
while rapide and rapide.suivant:
lent = lent.suivant
rapide = rapide.suivant.suivant
if lent is rapide:
return True
return FalseLa fonction renvoie True dès que les deux curseurs coïncident, ce qui ne peut arriver qu’en présence d’un cycle. L’élégance du procédé tient à son espace constant en O(1) : pas besoin de mémoriser les nœuds visités dans un ensemble, contrairement à l’approche naïve. Le temps reste linéaire. Si vous voulez revoir comment se manipule une structure chaînée, le tutoriel implémenter une liste chaînée en Python pose les bases.
Étape 5 — Le parcours en largeur : explorer une grille
Dès qu’un problème évoque des cases voisines, un réseau ou un plus court chemin en nombre d’étapes, un graphe se cache derrière, et le parcours en largeur est souvent la bonne réponse. Il explore les voisins niveau par niveau à l’aide d’une file. Le problème type est le comptage d’îlots : dans une grille de terres et d’eaux, combien de groupes de terres connectées existe-t-il ?
On parcourt la grille ; chaque fois qu’on tombe sur une terre non encore visitée, on lance un parcours en largeur qui marque toute l’île, et on incrémente le compteur. La file utilise collections.deque, qui offre un retrait en tête en temps constant — un point que la documentation officielle de Python garantit.
from collections import deque
def nombre_ilots(grille):
if not grille:
return 0
lignes, colonnes = len(grille), len(grille[0])
vus = set()
compte = 0
def bfs(depart_r, depart_c):
file = deque([(depart_r, depart_c)])
vus.add((depart_r, depart_c))
while file:
r, c = file.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if (0 <= nr < lignes and 0 <= nc < colonnes
and grille[nr][nc] == "1" and (nr, nc) not in vus):
vus.add((nr, nc))
file.append((nr, nc))
for r in range(lignes):
for c in range(colonnes):
if grille[r][c] == "1" and (r, c) not in vus:
bfs(r, c)
compte += 1
return compte
carte = [
["1", "1", "0", "0"],
["1", "0", "0", "1"],
["0", "0", "1", "1"],
]
print(nombre_ilots(carte)) # 2Le résultat est 2 : un premier îlot en haut à gauche, un second en bas à droite. On marque chaque case visitée dans l’ensemble vus pour ne jamais la recompter, ce qui garantit un temps linéaire en la taille de la grille, soit O(lignes × colonnes). Le piège récurrent est l’oubli du marquage avant l’ajout dans la file : sans lui, une même case entre plusieurs fois et le programme tourne en rond. Pour aller plus loin sur ce schéma, voyez implémenter le parcours en largeur sur un graphe.
Pourquoi un seul balayage suffit
Ces quatre schémas partagent une intuition profonde qui mérite d’être nommée, car elle vous aidera à en inventer de nouveaux. Dans une solution en force brute, on recommence souvent un travail déjà fait : pour chaque élément, on re-parcourt tout le reste. Les schémas efficaces suppriment cette redondance en conservant, d’un pas à l’autre, l’information déjà calculée. Les deux pointeurs ne reviennent jamais en arrière ; la fenêtre glissante réutilise la somme précédente au lieu de la recalculer ; les pointeurs lent et rapide n’ont besoin d’aucune mémoire annexe ; le parcours en largeur marque chaque case pour ne jamais la revisiter.
Cette idée porte un nom en analyse d’algorithmes : l’amortissement. Même si, à un instant donné, une étape semble coûteuse — la borne gauche de la fenêtre peut avancer de plusieurs crans d’un coup — le coût total sur l’ensemble du parcours reste linéaire, parce que chaque élément n’est franchi qu’un nombre constant de fois au total. Quand vous justifiez la complexité d’une de ces solutions à l’examinateur, c’est exactement cet argument qu’il attend : non pas « la boucle interne est constante », ce qui serait faux, mais « chaque élément entre et sort de la fenêtre au plus une fois, donc le total est linéaire ». Savoir formuler ce raisonnement vous distingue nettement.
Étape 6 — Construire son arbre de décision
Vous avez maintenant quatre schémas. La compétence finale consiste à les choisir vite. Entraînez-vous à dérouler ce petit arbre de décision à chaque énoncé : la donnée est-elle une séquence triée où l’on cherche une paire ou un encadrement ? Deux pointeurs. S’agit-il d’un sous-tableau ou d’une sous-chaîne contiguë sous contrainte ? Fenêtre glissante. Manipule-t-on une liste chaînée avec une notion de cycle ou de milieu ? Pointeurs lent et rapide. Parle-t-on de cases voisines, de réseau, de plus court chemin en étapes ? Parcours en largeur. Ce réflexe, répété sur quelques dizaines de problèmes, devient automatique et vous fait gagner les minutes décisives de l’entretien.
Pièges fréquents
| Symptôme | Cause probable | Correctif |
|---|---|---|
| Les deux pointeurs renvoient un résultat faux | Le tableau n’était pas trié | Trier d’abord, ou passer à une table de hachage |
| La fenêtre glissante rétracte trop | Position mémorisée hors de la fenêtre prise en compte | Tester que la position est supérieure ou égale au début |
| Boucle infinie sur la liste chaînée | Condition d’arrêt incomplète | Vérifier à la fois le curseur rapide et son suivant |
| Le parcours visite deux fois la même case | Marquage après ajout dans la file, pas avant | Ajouter à l’ensemble des vus au moment de l’empilement |
| Complexité qui reste quadratique | Un parcours imbriqué caché dans le corps de boucle | Vérifier que chaque élément n’est touché qu’un nombre constant de fois |
S’adapter au contexte ouest-africain
La plupart des entretiens techniques de la région se passent à distance, sur un éditeur de code partagé, parfois sans coloration syntaxique ni autocomplétion. Entraînez-vous donc à écrire ces squelettes de mémoire, sans l’aide de votre environnement habituel : ouvrez un éditeur en ligne minimal et tapez chaque schéma à blanc. Côté entraînement quotidien, beaucoup de plateformes d’exercices fonctionnent correctement même sur une connexion modeste ; téléchargez les énoncés quand le réseau est bon et travaillez hors ligne pendant les coupures. Un forfait data rechargé par mobile money en secours évite la panique si la fibre du quartier lâche en pleine séance.
Récapitulatif
Vous disposez désormais d’un classeur de quatre schémas qui couvrent une large part des exercices d’entretien. Vous savez repérer l’indice qui déclenche chacun, écrire son squelette, et annoncer sa complexité. Surtout, vous avez intégré le réflexe qui fait la différence : classer le problème avant d’écrire la moindre ligne. C’est cette habitude, plus que la mémoire des solutions, qui vous fera avancer face à un énoncé inconnu.
Aide-mémoire
| Indice dans l’énoncé | Schéma | Complexité visée |
|---|---|---|
| Tableau trié, paire ou encadrement | Deux pointeurs | O(n) temps, O(1) espace |
| Sous-tableau ou sous-chaîne contiguë | Fenêtre glissante | O(n) temps |
| Liste chaînée, cycle ou milieu | Pointeurs lent et rapide | O(n) temps, O(1) espace |
| Grille, réseau, plus court chemin en étapes | Parcours en largeur | O(V + E) temps |
À vous de jouer
Voici un défi pour ancrer la fenêtre glissante : écrivez une fonction qui renvoie la somme maximale d’un sous-tableau contigu de taille exactement k. Tentez-la avant de regarder la solution.
Voir une solution
def somme_max_fenetre(nums, k):
if len(nums) < k:
return None
somme = sum(nums[:k])
meilleur = somme
for i in range(k, len(nums)):
somme += nums[i] - nums[i - k]
meilleur = max(meilleur, somme)
return meilleur
print(somme_max_fenetre([2, 1, 5, 1, 3, 2], 3)) # 9On calcule la somme de la première fenêtre, puis on la fait glisser en ajoutant l’élément qui entre et en retirant celui qui sort, sans tout recalculer. Le résultat est 9, la somme de la fenêtre [5, 1, 3]. La complexité reste linéaire en O(n).
Tutoriels frères
- La programmation dynamique en entretien — pour les problèmes où les sous-cas se recouvrent.
- Structurer sa résolution en direct — la méthode qui encadre l’usage de ces schémas.
Pour aller plus loin
- Retour au guide principal : réussir les entretiens techniques.
- Documentation Python — module collections (deque, file).
Foire aux questions
Dois-je connaître d’autres schémas que ces quatre ?
Ces quatre couvrent une part majeure des exercices, mais d’autres existent : récursion avec retour sur trace, recherche binaire sur la réponse, programmation dynamique. Les quatre présentés ici sont les plus rentables à maîtriser en premier.
Comment savoir si ma solution est assez efficace ?
Annoncez sa complexité et comparez-la à la taille de l’entrée. Si l’énoncé évoque des entrées de grande taille et que votre solution est quadratique, cherchez un schéma linéaire — c’est presque toujours le signal qu’il en existe un.
Faut-il apprendre ces squelettes par cœur ?
Apprenez la logique, pas le texte. Réécrivez chaque schéma plusieurs fois à blanc jusqu’à ce que la structure vienne naturellement ; c’est la compréhension du mécanisme qui vous sauvera sur une variante inattendue.