Banque de questions de code pour entretien technique

Pattern : Deux pointeurs·Complexité : Temps O(n), espace O(1)

Placez un pointeur à chaque extrémité du tableau trié. Si la somme est trop petite, avancez le pointeur de gauche ; si elle est trop grande, reculez celui de droite. Le tri garantit que vous ne sautez jamais une paire valide — c’est cet invariant que les recruteurs veulent vous entendre énoncer à voix haute.

Pattern : Table de hachage / comptage·Complexité : Temps O(n), espace O(1) pour un alphabet fixe

Comptez la fréquence des caractères de la première chaîne, décrémentez en parcourant la seconde, et vérifiez que tous les compteurs reviennent à zéro. Évoquez la question de suivi avant qu’on vous la pose : pour tout l’Unicode, un tableau fixe de 26 cases ne suffit plus — utilisez une table de hachage.

Pattern : Pointeurs lent/rapide de Floyd·Complexité : Temps O(n), espace O(1)

Avancez un pointeur d’un nœud et un autre de deux ; s’ils se rencontrent, il y a un cycle. Préparez-vous à la question de suivi classique — trouver l’entrée du cycle : remettez un pointeur en tête et avancez les deux d’un nœud à la fois jusqu’à ce qu’ils se rencontrent à nouveau.

Pattern : Vote de Boyer–Moore·Complexité : Temps O(n), espace O(1)

Gardez un candidat et un compteur : incrémentez en cas de correspondance, décrémentez sinon, et remplacez le candidat quand le compteur tombe à zéro. Comme l’élément majoritaire apparaît plus de n/2 fois, il survit toujours. Expliquer POURQUOI il survit, c’est tout l’entretien.

Pattern : Un seul passage, minimum courant·Complexité : Temps O(n), espace O(1)

Suivez le prix minimum vu jusqu’ici et le meilleur bénéfice si vous vendez aujourd’hui. Un seul parcours, deux variables. C’est le plus petit exemple de l’idée « conserver le meilleur état du préfixe », que l’on retrouve ensuite dans l’algorithme de Kadane — faire ce lien rapporte des points.

Pattern : Tri + balayage linéaire·Complexité : Temps O(n log n), espace O(n)

Triez les intervalles par début, puis balayez : si l’intervalle courant commence après la fin du dernier intervalle fusionné, ajoutez-le ; sinon, étendez la fin fusionnée au maximum des deux. C’est le tri qui fait le vrai travail — dites-le, et traitez correctement les cas limites du comparateur (intervalles qui se touchent).

Pattern : Ensemble haché + débuts de séquence·Complexité : Temps O(n), espace O(n)

Mettez chaque nombre dans un ensemble ; ne commencez à compter qu’à partir des nombres dont le prédécesseur est absent (les débuts de séquence), puis avancez. Chaque élément est visité au plus deux fois : c’est ainsi que vous défendez le O(n) face à l’objection « mais il y a une boucle imbriquée ».

Pattern : Produits préfixes/suffixes·Complexité : Temps O(n), espace supplémentaire O(1) hors sortie

Deux passages sans division : remplissez d’abord chaque case avec le produit de tout ce qui se trouve à sa gauche, puis balayez depuis la droite en multipliant par le produit de tout ce qui se trouve à sa droite. Les réponses avec division échouent sur les zéros — les recruteurs l’interdisent généralement explicitement.

Pattern : Invariant avec une pile auxiliaire·Complexité : O(1) par opération, espace O(n)

À côté de la pile des valeurs, gardez une pile des minimums dont le sommet est toujours le minimum de tout ce qui se trouve en dessous — empilez min(nouvelle valeur, sommet actuel), dépilez les deux en même temps. C’est une question de conception : c’est l’invariant, pas la quantité de code, qui est évalué.

Pattern : Table de hachage + liste doublement chaînée·Complexité : O(1) par get/put, espace O(capacity)

Une table de hachage donne un accès en O(1) aux nœuds d’une liste doublement chaînée triée du plus récemment au moins récemment utilisé ; déplacez un nœud en tête à chaque accès, évincez par la queue en cas de dépassement. Des nœuds sentinelles en tête et en queue suppriment tous les cas limites de pointeurs nuls — mentionnez-les avant de commencer à coder.

Pattern : Remplissage par diffusion (BFS/DFS) sur une grille·Complexité : Temps O(rows × cols)

Parcourez la grille ; chaque case de terre non visitée lance un remplissage (DFS ou BFS) qui marque toute l’île comme visitée, et vous comptez ces départs. Annoncez votre stratégie de marquage (modifier la grille sur place ou utiliser un ensemble séparé) et le risque de profondeur de récursion sur de très grandes grilles — c’est le signal de séniorité.

Pattern : Tri topologique / détection de cycle·Complexité : Temps O(V + E)

Modélisez les prérequis comme un graphe orienté ; la question « peut-on tout terminer ? » revient exactement à « le graphe est-il acyclique ? ». L’algorithme de Kahn (retirer en boucle les nœuds de degré entrant nul) ou un DFS à trois couleurs fonctionnent tous les deux — choisissez-en un et expliquez pourquoi un nœud restant signifie un cycle.

Pattern : BFS avec un relevé par niveau·Complexité : Temps O(n), espace O(width)

Un BFS avec une file, mais en relevant la longueur de la file à chaque tour pour produire une liste par niveau. Cette astuce de la longueur relevée est le cœur réutilisable : le parcours en zigzag et la vue de droite sont la même boucle avec une étape de collecte différente.

Pattern : Propagation de bornes / parcours infixe·Complexité : Temps O(n), espace O(height)

Descendez récursivement avec une fenêtre autorisée (min, max) qui se resserre à chaque étape — ou faites un parcours infixe et vérifiez qu’il est strictement croissant. Le piège classique consiste à ne comparer les enfants qu’à leur parent ; construisez vous-même le contre-exemple avant que le recruteur ne le fasse.

Pattern : Correspondance de hachage dans les deux sens (bijection)·Complexité : Temps O(n), espace O(n)

Associez les caractères du motif aux mots ET les mots aux caractères — dans un seul sens, le motif "ab" serait accepté pour "dog dog". Vérifier la bijection dans les deux sens, c’est toute l’astuce ; prononcez le mot « bijection » et traitez le cas des longueurs différentes avant de coder.

Pattern : Détection de cycle sur une suite cachée·Complexité : O(log n) par étape ; espace O(1) avec Floyd

Remplacer sans cesse un nombre par la somme des carrés de ses chiffres finit soit par atteindre 1, soit par entrer dans une boucle — c’est donc Linked List Cycle déguisé. Détectez la boucle avec un ensemble des valeurs déjà vues, ou impressionnez avec les pointeurs lent/rapide de Floyd pour un espace en O(1). Nommer cette réduction à la détection de cycle, c’est le réflexe senior.

Pattern : Algorithme glouton avec une preuve à fournir·Complexité : Temps O(n), espace O(1)

Si le total d’essence ≥ le coût total, une réponse existe et elle est unique. Balayez une seule fois en suivant le niveau courant du réservoir ; chaque fois qu’il devient négatif, aucune station de la portion ratée ne peut être le départ — repartez de la station suivante. L’entretien porte sur la justification de ce saut, pas sur la boucle elle-même.

Pattern : Glouton / niveaux de BFS implicites·Complexité : Temps O(n), espace O(1)

Considérez les indices atteignables en k sauts comme un niveau de BFS : suivez le bord droit du niveau courant et la portée la plus lointaine observée ; quand vous dépassez le bord, incrémentez le nombre de sauts et étendez le bord jusqu’à cette portée maximale. Présenter cela comme un BFS sans file explique POURQUOI le glouton est optimal ici.

Pattern : Fusion linéaire en trois phases·Complexité : Temps O(n), espace O(n)

Émettez les intervalles qui se terminent avant le début du nouveau, puis absorbez dans le nouveau chaque intervalle qui le chevauche (début minimal, fin maximale), puis émettez le reste. L’entrée triée permet un seul passage sans nouveau tri — faites le parallèle avec Merge Intervals si l’on vous demande pourquoi c’est plus simple.

Pattern : Transformation de matrice sur place·Complexité : Temps O(n²), espace O(1)

Pivoter de 90° dans le sens horaire = transposer, puis inverser chaque ligne. Deux passages propres avec un espace supplémentaire en O(1) valent mieux que de redériver sous pression l’échange cyclique à quatre éléments — mais préparez-vous à expliquer la correspondance des coordonnées (i,j) → (j, n−1−i) si le recruteur va au-delà de l’astuce.

Pattern : Marquage sur place avec stockage emprunté·Complexité : Temps O(m×n), espace O(1)

Utilisez la première ligne et la première colonne pour stocker les indicateurs des lignes et colonnes à mettre à zéro, avec deux booléens qui retiennent leur propre état. Montez l’échelle de l’espace à voix haute — copie en O(mn) → ensembles en O(m+n) → stockage emprunté en O(1) — car c’est cette échelle elle-même qui est évaluée.

Pattern : Tri / comptage par seaux·Complexité : O(n log n) avec tri, O(n) avec des seaux

Triez par ordre décroissant et trouvez le plus grand i tel que citations[i] ≥ i+1 — ou évitez le tri avec des seaux de comptage plafonnés à n, en O(n). Énoncez précisément la définition avant de coder ; la plupart des échecs sur ce problème viennent d’une mauvaise lecture de « h articles avec au moins h citations », pas de l’algorithme.

Pattern : Tri topologique, ordre produit·Complexité : Temps O(V + E)

Même graphe que Course Schedule, mais cette fois l’algorithme de Kahn prend tout son sens : l’ordre dans lequel les nœuds de degré entrant nul sortent de la file EST un ordre de cours valide. Si l’ordre produit est plus court que le nombre de cours, il existe un cycle — renvoyez une liste vide. Mentionnez l’ordre postfixe d’un DFS, inversé, comme alternative.

Pattern : Fenêtre glissante avec compteur de satisfaction·Complexité : Temps O(n), espace O(alphabet)

Étendez le bord droit jusqu’à ce que la fenêtre couvre tous les caractères requis (suivez un compteur « formés / requis », pas une comparaison complète de tables à chaque étape), puis contractez le bord gauche au minimum tant que la fenêtre reste valide, en notant la meilleure. C’est l’optimisation du compteur qui garantit le O(n) — expliquez-la clairement.

Pattern : Deux pointeurs sur des maxima courants·Complexité : Temps O(n), espace O(1)

L’eau au-dessus de chaque barre vaut min(max-gauche, max-droite) − hauteur. Deux pointeurs qui avancent vers l’intérieur depuis les deux extrémités permettent de traiter le côté dont le maximum courant est le plus bas, car la borne de ce côté est déjà définitive. Expliquez pourquoi cette certitude tient — c’est toute la question.