Lire le code pour les taux de croissance
Examen du code pour la correction par rapport à l'examen du code pour la complexité
L'examen du code pour la correction détecte les erreurs de logique : conditions erronées, index décalés d'un cran, vérifications null manquantes. L'examen du code tenant compte de la complexité détecte une classe différente de défaut : code qui fonctionne correctement à N = 100 mais croît de façon catastrophique à N = 100 000.
Cette leçon se connecte à une investigation plus profonde dans le cours unhamming : Le chapitre manquant : complexité algorithmique couvre Big O dans le contexte des défauts de production, & MOAD-0001 : le défaut sédimentaire mappe le modèle dans 60+ écosystèmes logiciels.
Deux heuristiques d'examen
Les boucles imbriquées multiplient la complexité. Deux boucles imbriquées sur N éléments produisent O(N²). Trois produisent O(N³). Lors de l'examen : comptez d'abord la profondeur d'imbrication des boucles.
Conteneur séquentiel à l'intérieur d'une boucle chaude. Toute vérification .contains(), .includes(), .find(), ou in list à l'intérieur d'une boucle coûte O(N) par vérification. Sur N itérations : O(N²) au total. Ce modèle apparaît dans le code de production dans des dizaines d'écosystèmes — le compilateur GHC Haskell, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. Même erreur, bases de code différentes.
Examen : find_duplicates
Examinez la fonction Python suivante pour la complexité :
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001 : le défaut sédimentaire
Le même défaut, soixante écosystèmes
Le modèle if x not in list: list.append(x) à l'intérieur d'une boucle apparaît — a apparu — dans le code de production dans des dizaines d'écosystèmes logiciels :
- GHC (compilateur Haskell) : solveur de dépendances, O(N²) à N = 50 000 paquets, 17 minutes de compilation
- Python pip : résolution des conflits de dépendances
- Apache Maven : déduplication du classpath
- Rust Cargo : unification des fonctionnalités
- Compilateur TypeScript : résolution des modules
- Moteur Godot / Redot : traversée du graphique des nœuds
Aucune de ces équipes n'a fait une erreur. Elles ont écrit du code correct à petit N. N a grandi. Le code s'est calcifié. Le modèle a un nom : MOAD-0001, le défaut sédimentaire. Sédiment : correct, inoffensif en couches minces. Avec le temps, les couches s'accumulent et se durcissent.
Le correctif
Dans tous les cas : remplacez le conteneur séquentiel par un conteneur de hachage. Une ligne. Aucun changement comportemental aux entrées correctes. Accélération 100–1 000× à N réel.
Le correctif fonctionne parce que deux opérations doivent rester rapides :
1. Vérification d'appartenance : cet élément a-t-il déjà été vu ?
2. Sortie ordonnée : retourner les éléments dans l'ordre où ils ont été trouvés (parfois requis, parfois non).
Un ensemble gère (1) en O(1). Si (2) compte aussi, conservez une liste séparée pour la sortie ordonnée et un ensemble pour la vérification d'appartenance. Deux structures de données, chacune faisant un travail.
Répondre à un examinateur
Une demande de tirage corrige MOAD-0001 dans la fonction de traversée du graphique d'un projet. Un examinateur commente :
> "Les ensembles ne préservent pas l'ordre d'insertion — cela change le comportement."
Le modèle d'analyse d'entretien
Le format attendu
L'analyse de la complexité algorithmique apparaît dans les entretiens d'ingénierie logicielle. Une réponse forte suit un modèle en quatre parties :
1. Énoncez la complexité actuelle — O(?) pour le temps, O(?) pour l'espace.
2. Expliquez pourquoi — identifiez la construction spécifique responsable (boucle imbriquée, analyse linéaire dans une boucle, branchement récursif).
3. Proposez une optimisation — nommez la modification et la structure de données ou l'algorithme qu'elle introduit.
4. Énoncez la nouvelle complexité — après le correctif, quelle est la complexité en temps et en espace ?
Exemple :
Code: [fonction qui vérifie l'appartenance dans une liste à l'intérieur d'une boucle]
Actuel : O(N²) — `item in seen_list` est O(N) par vérification × N itérations
Optimisation : remplacer seen_list par seen_set (ensemble de hachage)
Après : O(N) — la vérification d'appartenance d'ensemble est O(1)Cette compétence s'étend au-delà des entretiens : examen du code tenant compte de la complexité, conception d'architecture, débogage de performance, audits de sécurité. Tout système qui traite des entrées de taille variable en bénéficie.
Cette leçon se connecte en avant au cours unhamming, qui applique ce exact modèle à l'investigation des défauts de production dans 60+ projets open source.
Entretien : analyser has_common_element
Appliquez le format d'entretien en quatre parties à cette fonction :
def has_common_element(list_a, list_b):
for item in list_a:
for other in list_b:
if item == other:
return True
return False