Accueil › Coding & algorithmique › Reconnaître le motif en dix secondes
Reconnaître le motif en dix secondes
Réussir l'épreuve de codeavance
En entretien, le temps de réflexion est court. Savoir reconnaître le motif à partir de l'énoncé est la compétence décisive.
| Signal dans l'énoncé | Motif |
|---|---|
| « trié » | deux pointeurs, recherche binaire |
| « contigu », « consécutifs » + « le plus long / court » | fenêtre glissante |
| « déjà vu », « doublon », « unique » | HashSet |
| « combien de fois », « le plus fréquent » | table de fréquences |
| « les K plus… » | tas de taille K |
| « le prochain plus grand » | pile monotone |
| « imbriqué », « parenthèses », « annuler » | pile |
| « le plus court chemin », « nombre minimal d'étapes » | BFS |
| « toutes les combinaisons / permutations » | backtracking |
| « de combien de façons », « minimum / maximum de » | programmation dynamique |
| « en O(1) en espace » | deux pointeurs, XOR, en place |
| « flux », « on ne peut pas tout stocker » | tas, ou comptage |
La taille de l'entrée est un indice, souvent délibéré :
| n | Complexité visée |
|---|---|
| ≤ 20 | exponentielle acceptable (2ⁿ) |
| ≤ 500 | O(n³) |
| ≤ 5 000 | O(n²) |
| ≤ 10⁶ | O(n log n) ou O(n) |
| ≤ 10⁹ | O(log n), ou une formule |
Si l'énoncé annonce n ≤ 20 et demande toutes les combinaisons, il autorise l'exponentiel. S'il annonce 10⁵, il exclut le O(n²).
Les termes à connaître
- Motif algorithmique
Une technique réutilisable — deux pointeurs, fenêtre glissante, table de fréquences — qui couvre une famille entière d'énoncés. En reconnaître une, c'est avoir résolu la moitié du problème.
- Signal dans l'énoncé
Le mot qui trahit le motif : « contigu » (fenêtre), « trié » (deux pointeurs ou binaire), « déjà vu » (Set), « le plus grand suivant » (pile monotone), « de combien de façons » (programmation dynamique).
- Contrainte de taille
L'ordre de grandeur de n indique la complexité attendue : n ≤ 20 autorise l'exponentiel, n ≤ 10⁵ impose O(n log n), n ≤ 10⁹ exige O(log n) ou une formule.
- Espace imposé
« En O(1) en espace » exclut les structures auxiliaires : la réponse passe par deux pointeurs, du XOR, ou une modification en place.
- Entraînement délibéré
Refaire un exercice sans regarder la solution, à quelques jours d'intervalle, vaut mieux que d'en survoler dix. L'objectif est la reconnaissance automatique, pas la mémorisation.
- Révision espacée
Revoir un motif à J+1, J+7, J+30. C'est ce que fait le glossaire de cette application avec les termes clés.
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.