Questions d'entretien DSA

Vous avez résolu quelques centaines de problèmes et vous vous sentez encore mal préparé, ce qui signifie généralement que vous vous êtes entraîné sur la mauvaise moitié de l'exercice. Cette section identifie ce qui est réellement noté, afin que l'entraînement puisse s'y ajuster.

Un entretien en direct sur les structures de données et les algorithmes mesure quatre choses à la fois : si vous reconnaissez à quel schéma appartient le problème, si vous pouvez énoncer l'approche avant d'écrire le code, si l'implémentation est correcte aux limites, et si vous pouvez raisonner à voix haute sur la complexité. Les candidats optimisent le troisième point et négligent le deuxième, puis sont pénalisés pour une solution correcte arrivée sans explication.

Cette étape de reconnaissance explique pourquoi la pratique des schémas l'emporte sur le volume. Les problèmes sont rarement inédits ; ce sont des recombinaisons. Dès que vous pouvez dire ceci est une fenêtre glissante sur une carte de fréquences dans la première minute, le reste n'est que de l'exécution. Les banques de questions associées, classées par langage et par poste, se trouvent sur le hub des questions d'entretien.

Ces schémas représentent la majorité de ce qui est demandé. Apprenez à reconnaître le signal qui pointe vers chacun d'eux.

• Deux pointeurs. Entrée triée, sommes de paires, partitionnement en place, vérification de palindromes.
• Fenêtre glissante. Sous-tableau contigu le plus long ou le plus court sous une contrainte.
• Comptage par table de hachage. Anagrammes, doublons, comparaisons de fréquences, premier élément unique.
• Recherche binaire. Tableaux triés, et recherche sur l'espace des réponses quand le tableau n'est pas trié.
• Parcours en largeur et en profondeur. Arbres, grilles, composantes connexes, plus court chemin non pondéré.
• Tas et file de priorité. Problèmes du top-k, fusion de flux triés, médianes glissantes.
• Intervalles. Fusion, insertion et détection de chevauchement après tri par le début.
• Programmation dynamique. Sous-problèmes qui se chevauchent : monter des escaliers, rendu de monnaie, distance d'édition, sous-séquences.
• Retour sur trace. Permutations, combinaisons, sous-ensembles, casse-têtes à contraintes.
• Algorithmes de graphes. Tri topologique, union-find, plus court chemin pondéré.

Des énoncés représentatifs, formulés comme le font les examinateurs :

• Trouver deux nombres d'un tableau dont la somme vaut une cible, puis le faire sans espace supplémentaire.
• Retourner la longueur de la plus longue sous-chaîne sans caractère répété.
• Étant donné un tableau trié puis pivoté, trouver une cible en temps logarithmique.
• Fusionner des intervalles qui se chevauchent et expliquer pourquoi le tri en vaut le coût.
• Inverser un arbre binaire, puis trouver sa profondeur maximale.
• Valider un arbre binaire de recherche, et dire ce qu'une vérification naïve manque.
• Compter les îles dans une grille, puis dire comment traiter une grille trop grande pour la mémoire.
• Trouver les k éléments les plus fréquents et justifier la structure de données choisie.
• Calculer le nombre minimal de pièces pour un montant, et énoncer la récurrence.
• Détecter un cycle dans une liste chaînée, puis retourner le nœud où il commence.
• Sérialiser puis désérialiser un arbre binaire.
• Étant donné des prérequis de cours, déterminer si le planning est réalisable.

Un jeune diplômé qui passe un entretien pour un poste backend reçoit le problème de la sous-chaîne et se met à taper immédiatement. Le code est presque juste, mais l'examinateur passe l'entretien à demander ce qu'il fait, et la note reflète le silence plutôt que le bug. Un candidat qui passe quarante secondes à dire fenêtre sur une carte de caractères, on agrandit à droite, on rétrécit à gauche en cas de doublon, on garde trace du maximum a déjà réussi la partie la plus difficile à rattraper.

Résoudre en silence construit le mauvais réflexe. L'entretien en direct exige de commenter et de coder en même temps, ce qui est une compétence distincte de chacune d'elles prise isolément.

Changez l'exercice plutôt que la liste de problèmes. Avant d'écrire quoi que ce soit, énoncez à voix haute le schéma, l'approche et la complexité attendue. Écrivez le code tout en continuant à commenter. Une fois terminé, énoncez à nouveau la complexité et citez un cas limite que vous avez traité et un autre que vous poseriez en question. Faire cela sur dix problèmes développe plus de compétence pour l'entretien que d'en résoudre cinquante en silence.

Une session d'entretien simulé fournit les questions de suivi, la partie qu'on ne peut pas répéter seul, et vous laisse un enregistrement de votre propre commentaire à revoir. Une limite honnête s'applique tout du long : une évaluation de code écrite dans le navigateur, avec surveillance, n'est pas une conversation, et aucun assistant en direct n'a sa place dans ce contexte. Le hub des types d'entretien précise quels formats de code sont en direct et lesquels sont automatisés.