17 — Exercices : Guide complet et 100 exercices classés

Ce chapitre est le terrain d'entraînement de toute la formation. Il contient une méthodologie de résolution de problèmes (UMPIRE) et 100 exercices répartis en 5 niveaux : facile (20), moyen (25), difficile (25), expert (20) et compétition (10), couvrant les 10 thèmes fondamentaux.

1. Pourquoi s'entraîner sur des exercices ?

La théorie sans pratique s'oublie. Les exercices permettent de :

Automatiser les réflexes : reconnaître un pattern (deux pointeurs, sliding window, fenêtre de hash…) dès la lecture de l'énoncé.
Valider la compréhension : un problème résolu en 30 minutes vaut mieux que 3 chapitres relus.
Construire une bibliothèque mentale de solutions réutilisables (templates).
Se préparer aux entretiens techniques : les exercices de ce chapitre sont le format exact des tests FAANG.
Mesurer sa progression : on reprend un exercice facile un mois plus tard et il doit paraître trivial.

Règle des 20 minutes : si après 20 minutes de réflexion structurée vous êtes bloqué, lisez l'indice. Si l'indice ne suffit pas, regardez le corrigé du chapitre 19, puis recodez seul l'exercice le lendemain de mémoire. Le code recopié sans effort ne forme pas.

2. Méthodologie UMPIRE

Pour chaque problème, suivez ce processus en 6 étapes. Ne sautez aucune étape, même sur un problème facile.

U — Understand (Comprendre)

Reformulez le problème avec vos mots, à voix haute.
Listez les entrées et les sorties avec des exemples concrets.
Identifiez les contraintes : taille de n, bornes des valeurs, mémoire disponible, temps limite.
Posez des questions : entrées vides ? négatifs ? doublons ? valeurs uniques ? graphe connexe ou pas ?

M — Match (Relier)

Associez le problème à un pattern connu :
- Trié + recherche → recherche binaire, deux pointeurs.
- Sous-tableaux contigus + somme → sliding window, prefix sums.
- "Nombre de façons" → DP.
- "Minimum/maximum local" → greedy.
- Énumération de toutes les combinaisons → backtracking.
- "Plus court chemin" → BFS (poids uniformes) ou Dijkstra (poids positifs).
- Comptage de fréquences → hash map, tri comptage.

P — Plan (Planifier)

Écrivez les grandes étapes de l'algorithme en pseudo-code.
Calculez la complexité avant de coder.
Choisissez la structure de données adaptée (voir chapitre 23 pour le cheat sheet).

I — Implement (Implémenter)

Écrivez du code propre, en nommant clairement les variables.
Gérez les cas limites dès le début (tableau vide, n == 1…).
Utilisez des assertions ou des conditions de garde.

R — Review (Relire)

Tracez manuellement l'algorithme sur un petit exemple.
Vérifiez les invariants : la boucle se termine-t-elle ? L'indice de boucle est-il toujours dans les bornes ?
Contrôlez qu'aucune branche n'est oubliée (cas pair/impair, égalité…).

E — Evaluate (Évaluer)

Testez sur plusieurs entrées : nominale, limite (min/max), contrefactuelle (erreur attendue).
Confirmez la complexité asymptotique avec des mesures empiriques (timeit).
Comparez avec la solution du chapitre 19 et notez ce que vous auriez pu améliorer.

3. Conseils de pratique

Quantité ciblée : 2 à 4 exercices par jour, en alternant les thèmes (jamais 3 DP d'affilée).
Délai de réflexion : 20 à 45 minutes maximum par exercice, chrono en main pour le niveau compétition.
Journal de bord : notez pour chaque exercice le thème, le pattern identifié, la complexité et une ligne de leçon apprise.
Recodez de mémoire : 2 jours après un exercice, refaites-le sans regarder votre solution.
Variations : modifiez les contraintes (passer de n ≤ 10^5 à n ≤ 10^9) et adaptez l'algorithme.
Multilangage : résolvez le même exercice en Python (rapide à itérer) puis en C++ ou Go (performance).

4. Légende des exercices

Difficulté : ★☆☆ facile · ★★☆ moyen · ★★★ difficile · ★★★★ expert · ★★★★★ compétition.
Thèmes : arrays · strings · linked lists · hash · trees · graphs · DP · greedy · backtracking · math.
Contraintes : limites de n et des valeurs pour choisir le bon algorithme.
Indice : piste de départ, à consulter après 20 minutes de réflexion.
Les corrigés multi-langages se trouvent dans le chapitre 19-Corrections (référence E17-NN).

5. Niveau 1 : 20 exercices faciles

Objectif : automatiser les réflexes de base — parcours, comptage, tri, recherche. Chaque exercice se résout en moins de 20 lignes.

Arrays

E17-01 · Somme et maximum ★☆☆ · arrays — Étant donné un tableau d'entiers, écrire une fonction qui renvoie la somme et le maximum en un seul parcours. Contraintes : n ≤ 10^5. Indice : une seule boucle, deux variables accumulateurs.
E17-02 · Inverser un tableau ★☆☆ · arrays — Inverser le tableau en place, sans structure auxiliaire. Contraintes : n ≤ 10^6. Indice : deux pointeurs qui convergent.

Strings

E17-03 · Palindrome ★☆☆ · strings — Vérifier si une chaîne est un palindrome (en ignorant casse et caractères non-alphanumériques). Contraintes : |s| ≤ 10^5. Indice : deux pointeurs gauche/droite.
E17-04 · Compter les voyelles ★☆☆ · strings — Compter les voyelles (a e i o u) d'une chaîne, en ignorant la casse. Contraintes : |s| ≤ 10^5. Indice : un set de voyelles, une boucle.

Linked Lists

E17-05 · Longueur d'une liste chaînée ★☆☆ · linked lists — Parcourir la liste et retourner le nombre de nœuds. Contraintes : n ≤ 10^5. Indice : itérer jusqu'à null en incrémentant un compteur.
E17-06 · Rechercher une valeur ★☆☆ · linked lists — Renvoyer l'indice (0-based) de la première occurrence d'une valeur, ou -1. Contraintes : n ≤ 10^5. Indice : parcours avec compteur d'indice.

Hash

E17-07 · Élément le plus fréquent ★☆☆ · hash — Trouver l'élément apparaissant le plus souvent. Contraintes : n ≤ 10^5, valeurs ≤ 10^9. Indice : compteur avec hash map, puis max.
E17-08 · Doublons présents ★☆☆ · hash — Retourner true si un tableau contient au moins deux fois le même élément. Contraintes : n ≤ 10^5. Indice : hash set, premier doublon détecté.

Trees

E17-09 · Taille d'un arbre binaire ★☆☆ · trees — Compter le nombre de nœuds d'un arbre binaire. Contraintes : n ≤ 10^5, profondeur ≤ 10^4. Indice : récursif 1 + taille(gauche) + taille(droite).
E17-10 · Maximum d'un arbre binaire ★☆☆ · trees — Trouver la valeur maximale d'un arbre binaire. Contraintes : valeurs quelconques. Indice : parcours récursif en conservant un max.

Graphs

E17-11 · Degré d'un nœud ★☆☆ · graphs — Étant donné une liste d'adjacence, retourner le degré d'un nœud donné. Contraintes : n ≤ 10^5. Indice : len(adj[node]).
E17-12 · Nombres de sommets et d'arêtes ★☆☆ · graphs — Compter sommets et arêtes d'un graphe orienté. Contraintes : n, m ≤ 10^5. Indice : arêtes = somme des longueurs des listes d'adjacence.

DP

E17-13 · Fibonacci (récursif) ★☆☆ · DP — Calculer fib(n) pour n ≤ 30. Contraintes : n ≤ 30 (récursion naïve acceptable). Indice : cas de base 0 et 1, récurrence simple.
E17-14 · Escalier à 1 ou 2 pas ★☆☆ · DP — Nombre de façons de monter n marches en prenant 1 ou 2 marches à la fois. Contraintes : n ≤ 40. Indice : c'est Fibonacci décalé ; utilisez deux variables glissantes.

Greedy

E17-15 · Rendu de monnaie simple ★☆☆ · greedy — Rendre une somme avec un nombre minimal de pièces, monnaie {1, 5, 10, 25}. Contraintes : somme ≤ 10^6. Indice : toujours prendre la plus grosse pièce possible (système canonique).
E17-16 · Maximiser la somme de k éléments ★☆☆ · greedy — Choisir k éléments pour maximiser la somme. Contraintes : n ≤ 10^5, k ≤ n. Indice : trier et prendre les k plus grands.

Backtracking

E17-17 · Sous-ensembles de {1..n} (petits) ★☆☆ · backtracking — Énumérer tous les sous-ensembles pour n ≤ 8. Contraintes : n ≤ 8. Indice : récursion inclure/exclure, ou masque binaire.
E17-18 · Permutations de 3 éléments ★☆☆ · backtracking — Générer les permutations de [1,2,3]. Contraintes : n = 3 fixé. Indice : backtracking avec tableau used.

Math

E17-19 · PGCD de deux entiers ★☆☆ · math — Calculer le PGCD par l'algorithme d'Euclide. Contraintes : valeurs ≤ 10^9. Indice : gcd(a,b) = gcd(b, a % b).
E17-20 · Parité et multiples ★☆☆ · math — Compter les nombres pairs et les multiples de 7 dans un tableau. Contraintes : n ≤ 10^5. Indice : tests de modulo dans une boucle.

6. Niveau 2 : 25 exercices moyens

Objectif : combiner plusieurs techniques — deux pointeurs, sliding window, hash map, BFS/DFS simples, DP classique.

Arrays

E17-21 · Deux sommes (Two Sum) ★★☆ · arrays — Trouver deux indices dont les valeurs somment à une cible. Contraintes : n ≤ 10^5, une solution garantie. Indice : hash map valeur → indice pendant le parcours.
E17-22 · Meilleur moment pour acheter/vendre ★★☆ · arrays — Un seul achat et une seule vente, maximiser le profit. Contraintes : n ≤ 10^5. Indice : suivre le minimum vu jusqu'à maintenant.
E17-23 · Produit des autres éléments ★★☆ · arrays — Tableau out[i] = produit de tous les éléments sauf arr[i], sans division. Contraintes : n ≤ 10^5, produit ≤ 2^53. Indice : prefix products et suffix products.

Strings

E17-24 · Anagrammes ★★☆ · strings — Vérifier si deux chaînes sont des anagrammes. Contraintes : |s| ≤ 10^5, alphabet 26 lettres. Indice : tableau de comptage de taille 26.
E17-25 · Compression de chaîne ★★☆ · strings — Compresser "aaabbc" en "a3b2c1" ; retourner la chaîne originale si la compression est plus longue. Contraintes : |s| ≤ 10^5. Indice : parcours avec compteur de répétitions consécutives.
E17-26 · Première occurrence (implémentation de indexOf) ★★☆ · strings — Trouver la première occurrence d'un motif dans un texte sans utiliser de fonction de recherche. Contraintes : |text| ≤ 10^5, |pattern| ≤ 10^3. Indice : force brute par décalage, ou KMP du chapitre 13.

Linked Lists

E17-27 · Retirer le n-ième nœud depuis la fin ★★☆ · linked lists — Supprimer le nœud à n positions de la fin, en un seul parcours. Contraintes : n ≤ 10^5, n valide. Indice : pointeur avancé de n pas puis deux pointeurs.
E17-28 · Détecter un cycle ★★☆ · linked lists — Déterminer si la liste contient un cycle. Contraintes : n ≤ 10^5. Indice : tortue et lièvre (Floyd) : lent +2, rapide +1.

Hash

E17-29 · Sous-tableau avec somme k ★★☆ · hash — Compter les sous-tableaux dont la somme vaut exactement k. Contraintes : n ≤ 2×10^4, valeurs négatives incluses. Indice : prefix sums + comptage des différences dans une hash map.
E17-30 · Premier caractère unique ★★☆ · hash — Trouver l'indice du premier caractère non répété. Contraintes : |s| ≤ 10^5. Indice : deux passes — comptage puis premier caractère avec compte 1.
E17-31 · Grouper les anagrammes ★★☆ · hash — Grouper les chaînes anagrammes entre elles. Contraintes : n ≤ 10^4, |s| ≤ 100. Indice : signature = chaîne triée ou tuple de comptes (26).

Trees

E17-32 · Vérifier qu'un arbre est trié (BST) ★★☆ · trees — Valider qu'un arbre binaire est un ABR. Contraintes : n ≤ 10^5. Indice : plage (min, max) propagée récursivement.
E17-33 · Parcours par niveaux ★★☆ · trees — Retourner les valeurs par niveau (BFS). Contraintes : n ≤ 10^5. Indice : file FIFO + boucle par niveau.

Graphs

E17-34 · Nombre d'îles ★★☆ · graphs — Compter les composantes connexes de 1 dans une grille binaire. Contraintes : n×m ≤ 10^5. Indice : BFS/DFS en marquant les cellules visitées.
E17-35 · Cycle dans un graphe non orienté ★★☆ · graphs — Détecter un cycle à l'aide de DFS itératif. Contraintes : n, m ≤ 10^5. Indice : suivre le parent pour ne pas revenir en arrière.

DP

E17-36 · Sous-séquence croissante la plus longue (LIS) ★★☆ · DP — Longueur de la plus longue sous-séquence strictement croissante. Contraintes : n ≤ 2500 (O(n²) acceptable). Indice : dp[i] = 1 + max(dp[j]) pour j < i et arr[j] < arr[i].
E17-37 · Somme maximale de sous-tableau (Kadane) ★★☆ · DP — Sous-tableau contigu de somme maximale. Contraintes : n ≤ 10^5, valeurs négatives autorisées. Indice : best = max(arr[i], best + arr[i]).
E17-38 · Nombre de chemins dans une grille ★★☆ · DP — Chemins de (0,0) à (n-1,m-1) en allant bas/droite. Contraintes : n×m ≤ 10^6. Indice : dp[i][j] = dp[i-1][j] + dp[i][j-1], lignes compressées en 1D.

Greedy

E17-39 · Assigner des cookies ★★☆ · greedy — Maximiser le nombre d'enfants satisfaits : un enfant avec besoin g accepte un cookie de taille s ≥ g. Contraintes : n, m ≤ 3×10^4. Indice : trier les deux listes et avancer les deux pointeurs.
E17-40 · Réunion (merge intervals) ★★☆ · greedy — Fusionner tous les intervalles qui se chevauchent. Contraintes : n ≤ 10^4. Indice : trier par début puis étendre la fin courante.

Backtracking

E17-41 · Générer les parenthèses valides ★★☆ · backtracking — Générer toutes les combinaisons de n paires de parenthèses. Contraintes : n ≤ 8. Indice : n'ajouter ) que si closed < open.
E17-42 · Combinaison somme ★★☆ · backtracking — Trouver toutes les combinaisons d'entiers (réutilisables) qui somment à une cible. Contraintes : cible ≤ 40, candidats ≤ 40. Indice : tri + backtracking avec somme cumulée.

Math

E17-43 · Nombre premier (test) ★★☆ · math — Déterminer si n est premier. Contraintes : n ≤ 10^9. Indice : tester les diviseurs jusqu'à √n, en gérant 2 et les pairs.
E17-44 · Exponentiation modulaire ★★☆ · math — Calculer a^b mod m en O(log b). Contraintes : a, b ≤ 10^18, m ≤ 10^9. Indice : exponentiation rapide (exponentiation par carré).
E17-45 · Crible d'Ératosthène ★★☆ · math — Lister tous les nombres premiers ≤ n. Contraintes : n ≤ 10^6. Indice : tableau booléen, marquer les multiples du plus petit premier courant.

7. Niveau 3 : 25 exercices difficiles

Objectif : maîtriser les algorithmes non triviaux — fenêtres avancées, arbres auto-équilibrés, Dijkstra/BFS multi-sources, DP à 2 dimensions, backtracking avec contraintes fortes.

Arrays

E17-46 · Médiane de deux tableaux triés ★★★ · arrays — Médiane en O(log(min(n, m))). Contraintes : n, m ≤ 10^5. Indice : partition par recherche binaire sur le plus petit tableau.
E17-47 · Trapping Rain Water ★★★ · arrays — Eau totale piégée entre les barres. Contraintes : n ≤ 2×10^4. Indice : max à gauche, max à droite, eau[i] = min(L[i], R[i]) - h[i], avec deux pointeurs.
E17-48 · Plus long sous-tableau avec au plus k entiers distincts ★★★ · arrays — Longueur maximale d'une fenêtre contenant ≤ k valeurs distinctes. Contraintes : n ≤ 10^5, k ≤ n. Indice : sliding window + compteur de fréquences ; rétrécir tant que distincts > k.

Strings

E17-49 · Minimum window substring ★★★ · strings — Plus petite fenêtre de s contenant tous les caractères de t. Contraintes : |s| ≤ 10^5, |t| ≤ 10^5. Indice : deux pointeurs + compteur de besoins restants.
E17-50 · Palindrome le plus long ★★★ · strings — Longueur du plus long sous-étirement palindrome. Contraintes : |s| ≤ 1000. Indice : expansion autour du centre (2n-1 centres) ou DP O(n²).
E17-51 · Décoder une chaîne imbriquée ★★★ · strings — Décoder 3[a2[bc]] → abcbcabcbcabcbc. Contraintes : profondeur ≤ 10, |s| ≤ 10^5. Indice : pile de (chaîne, nombre) ou récursion sur l'indice courant.

Linked Lists

E17-52 · Réorganiser une liste (1→n→2→n-1→…) ★★★ · linked lists — Réorganiser la liste en alternant premier et dernier. Contraintes : n ≤ 10^5. Indice : milieu de liste (slow/fast) → inverser la seconde moitié → entrelacer.
E17-53 · Additionner deux nombres (listes) ★★★ · linked lists — Somme de deux nombres représentés par des listes chaînées (chiffres en ordre normal). Contraintes : n, m ≤ 10^5. Indice : inverser les deux listes, additionner avec retenue, réinverser.

Hash

E17-54 · Plus longue séquence consécutive ★★★ · hash — Longueur de la plus longue suite de nombres consécutifs (ordre non requis). Contraintes : n ≤ 10^5. Indice : hash set, ne démarrer une séquence que si x-1 n'existe pas.
E17-55 · Anagrammes de longueur k dans une fenêtre ★★★ · hash — Compter les occurrences de fenêtres de longueur k qui sont des anagrammes d'une cible. Contraintes : |s| ≤ 10^5. Indice : sliding window + comparaison de vecteurs de comptes (26).

Trees

E17-56 · Sérialiser / désérialiser un arbre binaire ★★★ · trees — Convertir un arbre en chaîne et inversement. Contraintes : n ≤ 10^5. Indice : préordre avec marqueurs null, reconstruction récursive.
E17-57 · Maximum path sum ★★★ · trees — Chemin de somme maximale entre deux nœuds quelconques (chemin dans l'arbre, valeurs pouvant être négatives). Contraintes : n ≤ 3×10^4. Indice : DFS renvoyant le gain de la branche, en mettant à jour un max global.
E17-58 · K-ième plus petit élément d'un BST ★★★ · trees — Trouver le k-ième plus petit en O(h + k). Contraintes : n ≤ 10^4. Indice : parcours inorder itératif avec compteur, ou comptage des nœuds par sous-arbre.

Graphs

E17-59 · Plus court chemin dans un labyrinthe ★★★ · graphs — Distance minimale de S à E dans une grille (murs, 4 directions). Contraintes : n×m ≤ 10^6. Indice : BFS 4-directions, distances dans une matrice.
E17-60 · Rotting Oranges ★★★ · graphs — Temps pour que toutes les oranges mûrissent (multi-source BFS). Contraintes : n×m ≤ 10^4. Indice : initialiser la file avec toutes les oranges pourries, BFS en couches.
E17-61 · Numéroter les composantes fortement connexes (Kosaraju/Tarjan) ★★★ · graphs — Compter les SCC d'un graphe orienté. Contraintes : n, m ≤ 10^5. Indice : deux DFS (ordre de fin) ou Tarjan avec indices et low-link.

DP

E17-62 · Edit distance ★★★ · DP — Distance de Levenshtein entre deux chaînes. Contraintes : |s|, |t| ≤ 500. Indice : DP O(n·m) sur les préfixes, trois transitions (insert/supp/remplacer).
E17-63 · Coin Change (nombre minimal de pièces) ★★★ · DP — Nombre minimal de pièces pour une somme, pièces quelconques (système non canonique). Contraintes : somme ≤ 10^4. Indice : dp[s] = min(dp[s], dp[s - coin] + 1), initialisé à l'infini.
E17-64 · Partition égal ★★★ · DP — Peut-on partitionner le tableau en deux sous-ensembles de somme égale ? Contraintes : n ≤ 200, somme ≤ 2×10^4. Indice : subset sum booléen avec tableau 1D.

Greedy

E17-65 · Saut minimal pour atteindre la fin ★★★ · greedy — Nombre minimal de sauts (arr[i] = distance max). Contraintes : n ≤ 10^4. Indice : jumps, end de la fenêtre courante, farthest ; greedy en O(n).
E17-66 · Stations-service ★★★ · greedy — Boucle de stations avec coûts et gains, trouver l'unique point de départ possible. Contraintes : n ≤ 10^5. Indice : si le total est négatif, pas de solution ; sinon tester les départs avec somme partielle < 0.

Backtracking

E17-67 · N-Queens ★★★ · backtracking — Placer n reines sans qu'elles s'attaquent. Contraintes : n ≤ 12. Indice : colonnes + diagonales suivies par hash set (r-c et r+c).
E17-68 · Sudoku solver ★★★ · backtracking — Résoudre une grille 9×9. Contraintes : grille partiellement remplie, 81 cases. Indice : backtracking case par case, contraintes lignes/colonnes/3×3, espaces de choix réduits.

Math

E17-69 · Compter les nombres premiers ≤ n (optimisé) ★★★ · math — Compter les premiers sous n en O(n log log n) ou mieux. Contraintes : n ≤ 5×10^6. Indice : crible optimisé ne marquant que les impairs, ou factorisation progressive.
E17-70 · PGCD d'une liste et lcm de deux nombres ★★★ · math — Calculer le PGCD de tout un tableau et le PPCM de deux nombres via a*b/gcd. Contraintes : n ≤ 10^5, valeurs ≤ 10^9. Indice : gcd itératif + propriété lcm(a,b) = |a*b| / gcd(a,b) (attention aux dépassements).

8. Niveau 4 : 20 exercices experts

Objectif : algorithmes avancés et optimisation extrême — graphes pondérés, DP 3D, structures sophistiquées, mathématiques avancées.

Arrays

E17-71 · Inversion count (fusion) ★★★★ · arrays — Compter les paires (i<j) telles que arr[i] > arr[j]. Contraintes : n ≤ 10^5. Indice : comptage pendant le tri fusion.
E17-72 · Sliding window maximum ★★★★ · arrays — Maximum de chaque fenêtre de taille k. Contraintes : n ≤ 10^5. Indice : deque monotone décroissante.

Strings

E17-73 · Recherche par KMP ★★★★ · strings — Implémenter KMP pour toutes les occurrences d'un motif. Contraintes : |text| ≤ 10^6, |pattern| ≤ 10^5. Indice : tableau pi (prefix-function) puis glissement amorti O(1).
E17-74 · Rabin-Karp avec hash roulant ★★★★ · strings — Compter les occurrences via hash modulaire roulant. Contraintes : chaînes ≤ 10^6, base et modulo premiers. Indice : hash = (hash*base + c) mod p, prétraitement des puissances.

Linked Lists

E17-75 · Copie d'une liste avec pointeur aléatoire ★★★★ · linked lists — Cloner une liste dont chaque nœud possède un pointeur random. Contraintes : n ≤ 1000. Indice : hash map ancien → nouveau, deux passes.
E17-76 · Fusionner k listes triées ★★★★ · linked lists — Fusionner k listes triées en une seule. Contraintes : k ≤ 10^4, total ≤ 10^5. Indice : tas (priority queue) de k têtes, ou fusionner deux par deux (divide & conquer).

Hash

E17-77 · Randomisé d'un deck (Fisher-Yates) ★★★★ · hash — Mélanger uniformément un tableau en O(n). Contraintes : n ≤ 10^5. Indice : pour i de n-1 à 1, échanger avec un indice aléatoire dans [0, i].
E17-78 · Conception d'un LRU cache ★★★★ · hash — Implémenter get et put en O(1). Contraintes : capacité ≤ 10^4, clés quelconques. Indice : hash map + liste doublement chaînée (ordre d'accès).

Trees

E17-79 · AVL : insertion et rotation ★★★★ · trees — Implémenter l'insertion avec rotations pour rester équilibré (facteur |≤1|). Contraintes : n ≤ 10^5. Indice : mettre à jour les hauteurs, appliquer les 4 rotations (LL, RR, LR, RL).
E17-80 · Segment tree : somme de plage + mise à jour ponctuelle ★★★★ · trees — Requêtes sum(l, r) et update(i, val) en O(log n). Contraintes : n ≤ 10^5, q ≤ 10^5. Indice : arbre 4n, construction récursive, push de mise à jour.

Graphs

E17-81 · Dijkstra avec tas binaire ★★★★ · graphs — Plus courts chemins depuis une source, poids non négatifs. Contraintes : n, m ≤ 10^5. Indice : priority queue, relaxation classique, complexité O((V+E) log V).
E17-82 · Détection de cycle + tri topologique (Kahn) ★★★★ · graphs — Trier topologiquement un DAG et détecter l'absence de cycle. Contraintes : n, m ≤ 10^5. Indice : file des nœuds de degré 0, décrémenter les degrés entrants.

DP

E17-83 · Plus longue sous-séquence palindromique ★★★★ · DP — Longueur de la plus longue sous-séquence palindromique. Contraintes : |s| ≤ 1000. Indice : DP 2D sur les indices, dp[i][j] = dp[i+1][j-1] + 2 si égal, sinon max des deux voisins.
E17-84 · Sac à dos 0/1 ★★★★ · DP — Valeur maximale avec contrainte de poids. Contraintes : n ≤ 500, poids ≤ 10^5. Indice : DP 1D par poids décroissant pour 0/1.

Greedy

E17-85 · Ordonnancement avec échéances (job scheduling) ★★★★ · greedy — Maximiser le profit en respectant les échéances. Contraintes : n ≤ 10^5. Indice : trier par profit décroissant, union-find sur les créneaux de temps.
E17-86 · Huffman coding ★★★★ · greedy — Construire l'arbre de codage optimal et produire les codes binaires. Contraintes : alphabet ≤ 256. Indice : tas de min, fusionner les deux plus petites fréquences.

Backtracking

E17-87 · Word search II (grille de mots) ★★★★ · backtracking — Trouver tous les mots du dictionnaire dans une grille de lettres. Contraintes : grille ≤ 12×12, mots ≤ 10^4. Indice : Trie + DFS avec backtracking pour limiter l'exploration.
E17-88 · Expression Add Operators ★★★★ · backtracking — Insérer +, -, * pour atteindre une cible. Contraintes : |s| ≤ 10, cible ≤ 10^9. Indice : backtracking avec valeur cumulée, dernier opérande et multiplication (correction de la précédente).

Math

E17-89 · Théorème des restes chinois (CRT) ★★★★ · math — Résoudre un système de congruences. Contraintes : modules deux à deux premiers entre eux. Indice : produit des modules, inverses modulaires (exponentiation rapide).
E17-90 · Dénombrement : coefficient binomial mod p ★★★★ · math — C(n,k) mod p avec factorielles précalculées. Contraintes : n ≤ 10^6, p premier. Indice : factorielles + inverses factoriels + théorème de Fermat pour l'inverse modulaire.

9. Niveau 5 : 10 exercices compétition

Objectif : problèmes de type Codeforces Div. 1 / AtCoder — raisonnement combinatoire, structures puissantes, recherche optimale. Un chrono de 45 minutes par problème est réaliste.

E17-91 · Fenêtre glissante avec multi-ensembles ★★★★★ · arrays — Maintien d'un multi-ensemble glissant pour répondre à des requêtes de k-ième plus petit en O(log n) par requête. Contraintes : n, q ≤ 10^5. Indice : deux heaps (min + max) ou un Fenwick indexé par valeurs compressées.
E17-92 · Chaîne minimale en KMP sur préfixes ★★★★★ · strings — Construire la plus courte chaîne contenant deux motifs donnés en tant que préfixes/suffixes. Contraintes : |s|, |t| ≤ 10^5. Indice : fonction préfixe sur motif + '#' + texte pour trouver le chevauchement.
E17-93 · Interception de collision (liste) ★★★★★ · linked lists — Détecter le nœud d'entrée du cycle (extension de Floyd). Contraintes : n ≤ 10^5. Indice : après rencontre tortue/lièvre, remettre un pointeur au départ et avancer pas à pas.
E17-94 · Count of range sum ★★★★★ · hash — Compter les sommes de sous-tableaux dans [low, high] en O(n log n). Contraintes : n ≤ 10^5. Indice : prefix sums + fenêtre glissante sur un arbre équilibré (ou BIT après compression).
E17-95 · Diamètre d'un arbre ★★★★★ · trees — Deux DFS pour obtenir la paire de sommets la plus éloignée. Contraintes : n ≤ 10^5. Indice : DFS depuis un sommet arbitraire → le plus loin est A → DFS depuis A → distance max.
E17-96 · K-th shortest path (Yen's algorithm) ★★★★★ · graphs — Trouver les k plus courts chemins. Contraintes : n ≤ 10^3, k ≤ 100. Indice : A* ou Dijkstra répété avec "candidate spur paths".
E17-97 · DP bitmask sur petits états ★★★★★ · DP — TSP en O(n²·2^n) avec masques. Contraintes : n ≤ 16. Indice : dp[mask][i] = coût min pour visiter mask et terminer en i.
E17-98 · Maximiser la distance minimale (greedy + binary search) ★★★★★ · greedy — Placer k points avec distance minimale maximale. Contraintes : n ≤ 10^5. Indice : recherche binaire sur la distance, validation greedy (prendre chaque point si d ≥ mid).
E17-99 · Backtracking avec contraintes par colonnes/diagonales optimisées ★★★★★ · backtracking — N-Queens pour n = 16 avec bitmasks. Contraintes : n ≤ 16. Indice : masques binaires pour colonnes, diagonales / et \, récursion en O(n!) améliorée.
E17-100 · Convolution et transformée rapide (FFT/NTT) ★★★★★ · math — Multiplier deux polynômes de degré ≤ 10^5 en O(n log n). Contraintes : n, m ≤ 10^5, coefficients ≤ 10^5. Indice : FFT (Cooley–Tukey) ou NTT modulo un premier NTT-friendly.

10. Plan d'entraînement sur 10 semaines

Semaine	Contenu	Volume
1	Exercices faciles E17-01 à E17-10	10 exercices
2	Exercices faciles E17-11 à E17-20	10 exercices
3	Moyens E17-21 à E17-30	10 exercices
4	Moyens E17-31 à E17-40	10 exercices
5	Moyens E17-41 à E17-45 + reprise de 3 exercices moyens ratés	8 exercices
6	Difficiles E17-46 à E17-55	10 exercices
7	Difficiles E17-56 à E17-65	10 exercices
8	Difficiles E17-66 à E17-70 + reprise de 3 exercices ratés	8 exercices
9	Experts E17-71 à E17-90 (au choix)	8 exercices
10	Compétition E17-91 à E17-100 (chronométrés)	8 exercices

Règle de reprise : tout exercice raté doit être recommencé de mémoire sous 48 h. La moitié des progrès vient de la relecture de vos propres erreurs.

11. Critères d'évaluation

Pour chaque exercice, évaluez votre solution sur une échelle de 1 à 5 :

Correction : la solution passe tous les tests, y compris les cas limites.
Complexité : asymptotiquement optimale (ou justifiée par les contraintes).
Clarté : code lisible, nommage explicite, sans duplication.
Rigueur : analyse de complexité fournie avant l'implémentation.
Robustesse : gestion des entrées vides, valeurs limites, dépassements.

Barème :

Moyenne ≥ 4,5 sur les 100 exercices → prêt pour un entretien senior / FAANG.
Moyenne ≥ 3,5 → prêt pour un entretien standard.
Moyenne < 3 → reprendre les chapitres 01 à 16 puis refaire les exercices de niveau 1 et 2.

Prochain chapitre : validez ces compétences avec les 100 QCM du chapitre 18, puis comparez vos solutions aux corrigés du chapitre 19.