Aide-mémoire de reconnaissance des schémas
Associez 15 signaux courants des problèmes (tableau trié, besoin de toutes les combinaisons, maximisation d’une valeur sous contrainte, etc.) aux schémas algorithmiques qui les résolvent le plus rapidement.
Aide-mémoire de reconnaissance des schémas est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Le jeu de reconnaissance des motifs en 60 secondes
Lors d'un véritable entretien, vous disposez d'environ 60 secondes après avoir lu un problème pour identifier le motif algorithmique qui s'applique, avant que l'intervieweur ne s'attende à ce que vous commenciez à coder. C'est la compétence la plus importante à développer : il ne s'agit pas de mémoriser des implémentations, mais de reconnaître l'outil à utiliser.
La reconnaissance des motifs vient de l'association des signaux du problème (les mots et les contraintes de l'énoncé) aux familles d'algorithmes connues. Une fois le motif identifié, l'implémentation devient un exercice de remplissage de modèle. Cette leçon constitue une fiche mémo systématique des 15 signaux de problème les plus courants et de leurs motifs correspondants.
# The recognition process
recognition_steps = [
'1. Read the problem once fully (do not start coding)',
'2. Identify the data structure: array, string, tree, graph, matrix?',
'3. Identify the ask: find min/max, count ways, enumerate, detect cycle...?',
'4. Note the constraint: n<=20 (bitmask), sorted (binary search), DAG (topo sort)?',
'5. Map signal -> pattern',
'6. State the pattern and complexity to the interviewer before coding',
'7. Handle edge cases mentally before writing',
]
for step in recognition_steps:
print(step)Signaux 1 à 3 : motifs des tableaux et des chaînes
Les signaux de problème les plus fréquents pour les tableaux et les chaînes :
- Tableau trié + rechercher une cible → Recherche binaire O(log n)
- Trouver une paire ou un triplet dont la somme est égale à la cible → Deux pointeurs O(n) si le tableau est trié, table de hachage O(n) s'il ne l'est pas
- Plus long ou plus court sous-tableau ou sous-chaîne satisfaisant une condition → Fenêtre glissante O(n)
- Somme maximale ou minimale d'un sous-tableau contigu → Algorithme de Kadane O(n)
- Détection des doublons → Ensemble de hachage O(n) ou sort O(n log n)
Si le tableau est trié, envisagez toujours la recherche binaire en premier. Tableau non trié + somme cible + O(n) = presque toujours une table de hachage pour rechercher le complément.
# Quick recognition: array/string signals
signals = [
('Sorted array, find element', 'Binary search O(log n)'),
('Find two elements summing to K', 'Sort+two-ptr O(n log n) or hash O(n)'),
('Longest subarray with property P', 'Sliding window (variable size) O(n)'),
('Max sum contiguous subarray', 'Kadane algorithm O(n)'),
('Anagram/permutation check', 'Frequency map (Counter) O(n)'),
('Contains duplicate', 'Hash set O(n)'),
('Merge two sorted arrays/lists', 'Two pointers O(n+m)'),
('Rotate / shift array', 'Reverse trick O(n) in-place'),
('Next permutation', 'Find rightmost ascent + swap + reverse'),
('Maximum product subarray', 'Track max and min (handles negatives)'),
]
for signal, pattern in signals:
print(f'{signal:45s} => {pattern}')Signaux 4 à 6 : motifs des arbres et des graphes
Les signaux des problèmes d'arbres et de graphes, ainsi que leurs motifs :
- Parcours niveau par niveau / plus court chemin dans un graphe non pondéré → BFS avec une file à double extrémité O(V+E)
- Explorer tous les chemins / détecter les cycles / ordre de DFS → DFS récursif ou itératif O(V+E)
- BST + propriétés du parcours infixe (k-ième élément, ordre trié) → DFS infixe O(n)
- Plus proche ancêtre commun → Descente récursive avec suivi du chemin O(n)
- Composantes connexes / réunir deux groupes → DSU O(n × alpha(n))
# Tree/graph signal recognition
tree_graph_signals = [
('Level-order / minimum depth / word ladder', 'BFS with deque'),
('All paths / path sum / all permutations tree', 'DFS recursive'),
('Cycle detection (undirected)', 'DFS with parent / DSU'),
('Cycle detection (directed) / course schedule', 'DFS three-color / Kahn topo sort'),
('Shortest path weighted graph', 'Dijkstra (non-neg) / Bellman-Ford (neg)'),
('All-pairs shortest path', 'Floyd-Warshall O(V^3)'),
('Topological order', 'Kahn BFS topo sort'),
('Min spanning tree', 'Kruskal (DSU) / Prim (heap)'),
('Dynamic connectivity / union-find', 'DSU path compression + union by rank'),
('Autocomplete / prefix search', 'Trie'),
('BST kth smallest / range sum', 'In-order DFS'),
]
for signal, pattern in tree_graph_signals:
print(f'{signal:50s} => {pattern}')Signaux 7 à 9 : signaux de programmation dynamique
Les signaux de DP sont les plus difficiles à reconnaître. Recherchez ces mots-clés :
- 'Nombre de façons de...' → DP de comptage (additionner les comptes des sous-problèmes)
- 'Coût minimal ou maximal pour atteindre...' → DP d'optimisation (prendre le minimum ou le maximum des sous-problèmes)
- 'Pouvons-nous atteindre...' (faisabilité) → DP booléenne (OR des sous-problèmes)
- Sous-problème défini par deux indices de chaîne → DP en 2D (LCS, distance d'édition)
- Prendre ou ignorer des éléments sous une contrainte de capacité → DP du sac à dos
- Sous-structure optimale + sous-problèmes qui se chevauchent → Vérifiez l'arbre de récursion pour repérer les appels répétés → DP
# DP signal recognition
dp_signals = [
('Number of ways to climb stairs / decode string', '1D DP (Fibonacci-like)'),
('Minimum cost to reach end / coin change', '1D DP (greedy fails)'),
('Longest increasing subsequence', '1D DP O(n^2) or patience sort O(n log n)'),
('Longest common subsequence of two strings', '2D DP O(mn)'),
('Edit distance between two strings', '2D DP O(mn) (LCS variant)'),
('Partition array into two equal subsets', '0/1 knapsack boolean DP'),
('Fill knapsack with max value under weight limit', '0/1 knapsack optimisation DP'),
('Burst balloons / matrix chain multiplication', 'Interval DP'),
('Palindrome partitioning minimum cuts', 'Interval DP + prefix palindrome'),
('Rob houses in circle', '1D DP × 2 (linear sub-problems)'),
]
for signal, pattern in dp_signals:
print(f'{signal:55s} => {pattern}')Signaux 10 à 12 : signaux liés aux tas, aux piles et aux stratégies gloutonnes
Signaux des problèmes utilisant un tas, une pile monotone ou une stratégie gloutonne :
- Éléments parmi les K meilleurs / k-ième plus grand ou plus petit → Tas (tas-min pour les K plus grands, tas-max pour le k-ième plus petit) O(n log k)
- Médiane en flux → Deux tas (tas-max de la moitié inférieure + tas-min de la moitié supérieure)
- Élément suivant plus grand ou plus petit → Pile monotone O(n)
- Plus grand rectangle / piégeage de l'eau → Pile monotone O(n)
- Ordonnancement d'intervalles / maximiser les intervalles disjoints → Glouton (sort selon l'instant de fin)
# Heap / stack / greedy signals
heap_stack_greedy = [
('Top-K frequent elements', 'Min-heap size K: O(n log k)'),
('Kth largest in array', 'Max-heap pop K times: O(n + k log n)'),
('Streaming median', 'Two heaps (max + min): O(log n) per insert'),
('Merge K sorted lists', 'Min-heap of (val, list_idx): O(n log k)'),
('Next greater element', 'Monotonic decreasing stack: O(n)'),
('Largest rectangle in histogram', 'Monotonic increasing stack: O(n)'),
('Sliding window maximum', 'Monotonic decreasing deque: O(n)'),
('Trapping rain water', 'Two pointers OR monotonic stack: O(n)'),
('Jump game reachability / minimum jumps', 'Greedy range expansion: O(n)'),
('Merge overlapping intervals', 'Sort by start, linear scan: O(n log n)'),
('Gas station circular', 'Greedy: start from reset point: O(n)'),
('Task scheduler with cooldown', 'Greedy: sort by frequency: O(n log n)'),
]
for signal, pattern in heap_stack_greedy:
print(f'{signal:45s} => {pattern}')Signaux 13 à 15 : retour sur trace et manipulation de bits
Signaux du retour sur trace et de la manipulation de bits :
- Générer tous les sous-ensembles / permutations / combinaisons → Retour sur trace O(2^n ou n!)
- Satisfaction de contraintes (problème des N reines, Sudoku) → Retour sur trace avec élagage
- Trouver un élément manquant ou unique → XOR O(n), espace O(1)
- Énumérer tous les sous-ensembles d'un petit ensemble (n ≤ 20) → Énumération par masque de bits 2^n
- Compter les bits à 1 / vérifier si une valeur est une puissance de deux → Astuces binaires (n & (n-1))
- DP avec compression d'état sur un petit ensemble → DP par masque de bits O(2^n × n)
# Backtracking and bit signals
bt_bit_signals = [
('Generate all subsets of array', 'Backtracking O(n * 2^n) / bitmask'),
('Generate all permutations', 'Backtracking O(n * n!)'),
('Combination sum with target', 'Backtracking with pruning'),
('Word search in grid', 'Backtracking DFS on grid O(m*n*4^L)'),
('N-queens placement', 'Backtracking with column/diag sets'),
('Find single unique element (all others x2)', 'XOR all: O(n) O(1)'),
('Missing number in 0..n', 'XOR or sum formula: O(n) O(1)'),
('Count set bits in n', 'n &= n-1 loop or DP O(n)'),
('Check power of two', 'n > 0 and n & (n-1) == 0'),
('Travelling salesman (n<=20)', 'Bitmask DP O(2^n * n^2)'),
('Number with max XOR in array', 'Trie on binary representation'),
]
for signal, pattern in bt_bit_signals:
print(f'{signal:50s} => {pattern}')Analyse des contraintes : ce que N vous indique
La contrainte sur la taille de l'entrée n vous indique directement la complexité temporelle acceptable, et donc la famille d'algorithmes à utiliser :
- n ≤ 20 : O(2^n) ou O(n!) acceptable — DP par masque de bits, retour sur trace
- n ≤ 500 : O(n³) acceptable — Floyd-Warshall, DP par force brute
- n ≤ 5000 : O(n²) acceptable — DP naïve, sort quadratique
- n ≤ 10^6 : O(n log n) nécessaire — sort par fusion, tas, recherche binaire
- n ≤ 10^8 : O(n) nécessaire — deux pointeurs, fenêtre glissante, DP linéaire
Cette analyse des contraintes doit être votre première étape après la lecture du problème, avant de choisir un algorithme.
# Constraint -> acceptable complexity -> algorithm family
complexity_map = [
('n <= 20', 'O(2^n) or O(n!)', 'Bitmask DP, backtracking/permutations'),
('n <= 500', 'O(n^3)', 'Floyd-Warshall, cubic DP, brute force'),
('n <= 5000', 'O(n^2)', 'Quadratic DP, bubble/insertion sort'),
('n <= 100000', 'O(n log n)', 'Merge sort, heap, binary search, topo sort'),
('n <= 1000000', 'O(n)', 'Linear DP, two pointers, sliding window, hash'),
('n <= 10^8', 'O(n) tight', 'Only simplest O(n) — no large constants'),
('n <= 10^18', 'O(log n) or O(1)', 'Math / number theory, binary search on answer'),
]
print(f'{'Constraint':15s} {'Complexity':15s} {'Algorithm Family'}')
print('-'*70)
for constraint, complexity, algorithms in complexity_map:
print(f'{constraint:15s} {complexity:15s} {algorithms}')Problème → motif : entraînement éclair
Entraînez-vous à faire cette association jusqu'à ce qu'elle devienne automatique. Lisez chaque description de problème et identifiez le motif avant de regarder la solution. La rapidité compte : lors d'un entretien, vous devriez identifier le motif en moins de 60 secondes :
- 'Étant donné un tableau trié, déterminer si deux éléments ont une somme égale à K'
- 'Étant donné un arbre, trouver son diamètre (le plus long chemin entre deux nœuds quelconques)'
- 'Étant donné n tâches avec une période de récupération k, trouver le nombre minimal d'intervalles de CPU'
- 'Étant donné une chaîne, trouver la plus longue sous-chaîne palindrome'
- 'Étant donné les nombres de 1 à n dont un est manquant, trouver le nombre manquant'
# Quick-fire pattern recognition answers
problems = [
('Sorted array: two elements sum to K',
'Two pointers (left from start, right from end): O(n)'),
('Tree diameter (longest path)',
'DFS returning (height, max_diameter) pair: O(n)'),
('Task scheduler with cooldown k',
'Greedy: (max_freq - 1)*(k+1) + count_of_max_freq: O(n log n)'),
('Longest palindromic substring',
'Expand around centre OR Manacher: O(n^2) or O(n)'),
('Missing number in 1..n',
'XOR all indices and values: O(n) O(1)'),
('Number of islands in binary grid',
'BFS/DFS flood fill counting connected components: O(m*n)'),
('Decode string like 3[a2[bc]] -> aaabcbcaabcbc',
'Stack to handle nested brackets: O(n)'),
('Valid parentheses [(){[]}]',
'Stack push open, pop+match on close: O(n)'),
]
for problem, solution in problems:
print(f'Q: {problem}\nA: {solution}\n')Signaux d'alerte : quand votre motif échoue
Même les ingénieurs expérimentés choisissent d'abord le mauvais motif. Reconnaissez ces signaux indiquant que votre approche actuelle est incorrecte et changez de direction :
- Votre O(n²) réussit les petits tests, mais dépasse le délai imparti avec les grandes entrées → vous avez besoin d'une table de hachage, d'une recherche binaire ou d'une structure monotone
- Votre stratégie gloutonne échoue sur un contre-exemple → essayez la DP
- L'espace d'états de votre DP est trop grand → recherchez une démonstration gloutonne ou une définition d'état plus intelligente
- Votre BFS produit une réponse incorrecte → vérifiez si vous avez besoin de Dijkstra (pondéré) plutôt que de BFS (non pondéré)
- Vous obtenez des exceptions de pointeur nul → ajoutez les cas de base et les vérifications des cas limites avant l'implémentation
# Red flags and recovery strategies
red_flags = [
('TLE on large n', 'Check complexity; switch from O(n^2) to O(n log n) or O(n)'),
('WA with greedy', 'Find a counter-example; switch to DP or prove exchange arg'),
('DP table huge', 'State compression (bitmask/rolling array) or different state'),
('BFS gives wrong shortest path', 'Check if edges have weights; use Dijkstra instead'),
('Stack overflow in recursion', 'Add memoisation or convert to iterative with explicit stack'),
('Off-by-one in binary search', 'Use half-open intervals [lo, hi); verify with 2-element test'),
('DSU wrong answer', 'Check 0-indexed vs 1-indexed; check union direction'),
('Backtracking TLE', 'Add pruning conditions; ensure undo step is correct'),
]
print('Pattern | Recovery')
print('-'*70)
for flag, recovery in red_flags:
print(f'{flag:40s} => {recovery}')Communiquer la reconnaissance des motifs lors des entretiens
Lors des entretiens, expliquer à voix haute votre reconnaissance du motif démontre votre expertise et donne à l'intervieweur l'occasion de vous guider si vous partez dans la mauvaise direction. Utilisez cette structure de script :
- 'Je remarque que le tableau est trié, donc je pense à une recherche binaire...'
- 'Le problème demande le sous-tableau de somme maximale, ce qui correspond à un problème classique de l'algorithme de Kadane...'
- 'Nous avons besoin de tous les sous-ensembles possibles, ce qui suggère un retour sur trace avec un arbre de récursion...'
- 'La contrainte n ≤ 20 m'indique que 2^n = 1M est acceptable, donc une DP par masque de bits pourrait fonctionner...'
Après avoir indiqué le motif, mentionnez la complexité time et spatiale avant d'écrire la moindre ligne de code. Cela montre que vous réfléchissez à l'efficacité avant l'implémentation.
# Interview communication template
def communicate_approach(problem, pattern, time_complexity, space_complexity, edge_cases):
print(f'Problem: {problem}')
print(f'Pattern: {pattern}')
print(f'Time: {time_complexity}, Space: {space_complexity}')
print(f'Edge cases to handle: {", ".join(edge_cases)}')
print()
# Example communications
communicate_approach(
problem='Find longest substring without repeating characters',
pattern='Sliding window with a set tracking current window characters',
time_complexity='O(n)',
space_complexity='O(min(n, alphabet_size))',
edge_cases=['empty string', 'all same characters', 'all unique characters']
)
communicate_approach(
problem='Given sorted matrix, find if target exists',
pattern='Binary search or staircase search (top-right corner): eliminate row or column each step',
time_complexity='O(m + n)',
space_complexity='O(1)',
edge_cases=['empty matrix', 'single element', 'target at corners']
)Construire votre vocabulaire de reconnaissance des motifs
Le moyen le plus rapide de développer votre reconnaissance des motifs consiste à résoudre des problèmes par séries thématiques, et non au hasard. Consacrez une semaine uniquement aux problèmes de fenêtre glissante. Ensuite, passez aux problèmes à deux pointeurs, puis aux problèmes de DP. Résoudre rapidement 20 problèmes du même type développe l'intuition nécessaire pour reconnaître ce motif d'un seul coup d'œil.
Après chaque problème, écrivez une « note de motif » d'une ligne : le signal du problème et le motif qu'il a déclenché. Construisez votre propre fiche mémo. Après avoir résolu 200 problèmes par séries thématiques, vous reconnaîtrez environ 90 % des problèmes d'entretien en moins de 30 secondes ; les 10 % restants nécessitent une analyse attentive, même pour les ingénieurs expérimentés.
# Personal pattern note template
pattern_notes = [
{'signal': 'sorted array + two sum', 'pattern': 'two pointers', 'example': 'LC 167 Two Sum II'},
{'signal': 'longest X without repeating', 'pattern': 'sliding window + set', 'example': 'LC 3 Longest Substring'},
{'signal': 'max sum subarray', 'pattern': 'Kadane', 'example': 'LC 53 Max Subarray'},
{'signal': 'permutations/subsets', 'pattern': 'backtracking', 'example': 'LC 46 Permutations'},
{'signal': 'tree path sum', 'pattern': 'DFS with accumulator', 'example': 'LC 112 Path Sum'},
{'signal': 'course schedule', 'pattern': 'Kahn topo sort', 'example': 'LC 207 Course Schedule'},
{'signal': 'top-K elements', 'pattern': 'min-heap size K', 'example': 'LC 215 Kth Largest'},
]
print(f'{'Signal':40s} {'Pattern':30s} {'Example'}')
print('-'*90)
for note in pattern_notes:
print(f'{note["signal"]:40s} {note["pattern"]:30s} {note["example"]}')Vérification rapide
Vérifiez votre compréhension des concepts de structures de données et d'algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : la reconnaissance des motifs associe les signaux des problèmes aux familles d'algorithmes : un tableau trié implique une recherche binaire, « tous les sous-ensembles » implique un retour sur trace et « coût minimal » implique la DP ; la contrainte n vous indique la complexité acceptable : n ≤ 20 autorise O(2^n), tandis que n ≤ 10^6 exige O(n log n) ou mieux ; et expliquer le motif et la complexité avant de coder démontre votre expertise et permet à l'intervieweur de vous donner un retour. Nous allons ensuite mettre la reconnaissance des motifs en pratique avec des problèmes d'entretien simulé chronométrés, de difficulté facile et moyenne.
Questions Fréquemment Posées
La leçon « Aide-mémoire de reconnaissance des schémas » est-elle gratuite ?
Oui — le texte complet de « Aide-mémoire de reconnaissance des schémas » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Aide-mémoire de reconnaissance des schémas » ?
Associez 15 signaux courants des problèmes (tableau trié, besoin de toutes les combinaisons, maximisation d’une valeur sous contrainte, etc.) aux schémas algorithmiques qui les résolvent le plus rapi… Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Aide-mémoire de reconnaissance des schémas » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Aide-mémoire de reconnaissance des schémas
- Entretien blanc chronométré : problèmes faciles et intermédiaires
- Gestion des cas limites et communication avec la personne interrogée
- Étude de problèmes difficiles : Word Ladder II et Alien Dictionary