Maîtrisez le TSP en entretien avec une réponse claire, Held-Karp, heuristiques et pièges à éviter. Gagnez en précision et convainquez vite.
Most candidates who struggle with travelling salesperson problem interview performance aren't struggling because they don't know what TSP is. They struggle because they know it too well — they've read the Wikipedia page, they've seen the DP table, and when the question comes up in an interview, they immediately start talking about bitmask state spaces before they've said what problem they're actually solving. The interviewer loses the thread. The candidate loses the room.
Cet article vous donne la réponse dans l’ordre qui fonctionne : d’abord une définition en langage simple, puis le choix entre exact et approximatif, ensuite le déroulé de Held-Karp, et enfin les questions de suivi. Répétez cette séquence une fois, et l’engrenage de panique s’arrête.
Dites ce qu’est réellement le TSP avant de dire quoi que ce soit d’intelligent
Ce que signifie TSP en langage simple
Le travelling salesperson problem est ceci : étant donné une liste de villes et les distances entre elles, trouvez l’itinéraire le plus court qui visite chaque ville exactement une fois et revient au point de départ. C’est tout. Une seule phrase. Vous devriez pouvoir l’expliquer en moins de dix secondes sans regarder un tableau blanc.
Si les candidats ne le formulent pas aussi clairement, c’est parce qu’ils ont intégré le TSP comme un concept de théorie des graphes plutôt que comme un énoncé de problème. Quand on l’intériorise comme un concept, on se tourne vers la « machinerie » — NP-hardness, programmation dynamique, DP sur bitmask — avant même d’avoir dit à l’intervieweur ce que l’on cherche à optimiser. C’est l’inverse qu’il faut faire. La définition n’est pas une formalité que l’on expédie en route vers la vraie réponse. C’est le socle sur lequel repose le reste de votre réponse.
Selon le traitement formel présenté dans Introduction to Algorithms (Cormen et al.), le TSP est classé NP-hard, ce qui signifie qu’aucun algorithme en temps polynomial n’est connu pour trouver la solution optimale pour toutes les entrées. Cette classification est importante, mais elle vient après la définition, pas avant.
Pourquoi les intervieweurs posent cette question
L’entretien sur le travelling salesperson problem n’est pas un test de mémoire. Les intervieweurs qui posent une question de TSP cherchent quelque chose de plus précis : cette personne sait-elle transformer un problème d’optimisation difficile en hypothèses claires avant de commencer à résoudre ? Peut-elle faire un choix délibéré entre exactitude et praticité en fonction des contraintes, plutôt que de se rabattre sur l’algorithme le plus impressionnant qu’elle connaisse ?
Dans mes séances de coaching, le mode d’échec le plus fréquent que j’ai observé est celui des candidats qui passent directement à la programmation dynamique avant même d’avoir dit ce que la DP est censée résoudre. Ils disent : « donc on utilise une DP sur bitmask des sous-ensembles de villes visitées », l’intervieweur hoche poliment la tête, puis demande : « mais quel est le problème exact ? » — et le candidat se retrouve alors à expliquer la définition depuis l’intérieur de la solution, ce qui est bien plus difficile. La définition doit venir en premier, posée calmement, comme si vous l’expliquiez à un collègue pendant le déjeuner. Tout ce qui suit devient plus limpide.
Donnez la réponse TSP en 60 secondes que vous pouvez réellement dire à voix haute
Le script mémorisé qui sonne naturel
Une bonne réponse d’entretien sur le TSP comporte quatre étapes, dans cet ordre. Vous n’avez pas besoin de plus de 90 secondes pour les quatre.
D’abord, définissez le problème : « Le TSP consiste à trouver l’itinéraire le plus court qui visite chaque nœud exactement une fois et revient à l’origine. » Une phrase.
Ensuite, nommez la difficulté : « Le problème, c’est que le nombre d’itinéraires possibles croît de façon factorielle avec le nombre de villes, donc la recherche exhaustive devient très vite impraticable. »
Troisièmement, choisissez votre solution en fonction des contraintes : « Pour de petites entrées — par exemple moins de 20 villes — on peut utiliser une programmation dynamique exacte avec Held-Karp, qui s’exécute en O(n² 2ⁿ). Pour des instances plus grandes, on utiliserait une approximation ou une heuristique — nearest-neighbor gloutonne, ou l’algorithme de Christofides si l’on a besoin d’une borne garantie. »
Quatrièmement, ouvrez la porte à la suite : « Voulez-vous que j’aille plus loin sur l’approche DP, ou serait-il plus utile de détailler l’aspect heuristique ? »
C’est cette dernière étape que la plupart des candidats omettent. Elle montre que vous comprenez qu’il existe deux chemins valables et que vous n’allez pas imposer à l’intervieweur celui dont il n’a pas besoin. Selon une recherche sur la performance en entretien technique publiée par Harvard Business Review, la communication structurée et le cadrage explicite des arbitrages font partie des signaux les plus forts utilisés par les responsables du recrutement pour distinguer un candidat senior d’un candidat intermédiaire.
À quoi cela ressemble en pratique
Imaginez-vous au tableau blanc. L’intervieweur dit : « Parlez-moi du travelling salesperson problem. » Une erreur fréquente en entretien TSP consiste à dessiner immédiatement un graphe avec cinq nœuds et à commencer à annoter les arêtes. Ne le faites pas. Dites d’abord la définition à voix haute, puis dessinez le graphe. Le graphe doit illustrer la définition, pas la remplacer.
En pratique, les candidats qui répètent un script en quatre étapes paraissent nettement moins récités que ceux qui improvisent, parce que la structure élimine la charge cognitive liée au choix de ce qu’il faut dire ensuite. Un candidat que j’ai coaché avait une excellente compréhension conceptuelle du TSP, mais il tournait autour de trois ou quatre cadrages concurrents avant d’en choisir un. Après avoir répété le script en quatre étapes deux fois, sa réponse est devenue suffisamment nette pour que l’intervieweur passe directement aux questions de suivi — ce qui est exactement ce que vous voulez, car ce sont ces questions qui permettent de montrer votre profondeur.
Choisissez entre DP exacte et heuristique au lieu de faire semblant qu’il n’existe qu’une seule bonne réponse
Quand la programmation dynamique exacte est le bon choix
Held-Karp est la bonne réponse lorsque l’intervieweur signale qu’il veut de la rigueur, lorsque la taille de l’entrée est petite, ou lorsque le problème est présenté comme un exercice de cours. La méthode est exacte — elle trouve l’itinéraire optimal — et c’est l’approche DP standard pour le TSP dans les contextes académiques et d’entretien. L’état encode les villes déjà visitées et la ville à laquelle le trajet se termine, et la transition construit des sous-itinéraires optimaux jusqu’à reconstituer l’itinéraire complet.
La limite structurelle est claire : Held-Karp s’exécute en O(n² 2ⁿ) en temps et O(n 2ⁿ) en espace. À n = 20, cela représente environ 20 millions d’états, ce qui reste gérable. À n = 30, on dépasse le milliard. L’exactitude est utile jusqu’au moment où l’espace d’états cesse d’être praticable, et une réponse honnête nomme cette frontière au lieu de prétendre que la DP passe à l’échelle indéfiniment.
Quand une heuristique est la réponse la plus intelligente
Les heuristiques ne sont pas des réponses de seconde catégorie. Pour l’approximation des problèmes de TSP dans des contextes réels, elles sont souvent la seule réponse honnête. Le nearest-neighbor glouton est rapide et simple : on part d’une ville, on va toujours vers la ville non visitée la plus proche, puis on revient au départ. Il ne garantit pas l’optimalité, mais il s’exécute en O(n²) et produit souvent des itinéraires à 20–25 % de l’optimum.
L’algorithme de Christofides est l’option la plus fondée : il garantit un trajet au plus 1,5 fois l’optimum pour le TSP métrique (où les distances satisfont l’inégalité triangulaire). Pour de nombreux systèmes de production, une borne à 1,5× avec un temps polynomial est bien plus précieuse qu’une réponse exacte dont le calcul prend un temps exponentiel.
À quoi cela ressemble en pratique
Considérez deux scénarios. Dans le premier, vous êtes en entretien et le problème est formulé ainsi : « douze villes, trouvez la tournée optimale. » Held-Karp est la bonne réponse. L’entrée est petite, l’intervieweur veut voir la structure de la DP, et l’exactitude est atteignable.
Dans le second scénario, le problème est : « 12 000 points de livraison, optimisez l’itinéraire pour une flotte de coursiers en livraison le jour même. » Personne n’exécute Held-Karp sur 12 000 nœuds. La réponse est une heuristique ou une métaheuristique — recuit simulé, algorithmes génétiques, ou solveur commercial. Le routage de circuits imprimés et les systèmes de tournées de véhicules utilisés en logistique, par exemple, s’appuient sur des algorithmes d’approximation depuis les années 1970 précisément parce que les tailles d’entrée rendent l’optimalité complète illusoire. Le NIST Dictionary of Algorithms and Data Structures documente le comportement de montée en échelle des algorithmes exacts pour le TSP et explique pourquoi les méthodes d’approximation dominent en pratique.
Le candidat capable de nommer cette transition — de l’exact à l’approximatif, et d’expliquer pourquoi — est celui qui donne l’impression d’avoir réfléchi au problème au-delà du cadre scolaire.
Déroulez Held Karp comme si vous étiez devant un tableau blanc
L’état, la transition et la partie laide
L’explication de l’algorithme Held-Karp en entretien fonctionne mieux si vous l’ancrez d’abord dans la définition de l’état avant d’écrire la moindre transition. L’état est `dp[S][i]`, où `S` est un bitmask représentant l’ensemble des villes déjà visitées, et `i` est la ville où se termine le trajet courant. La valeur stockée est le coût minimal pour visiter exactement les villes de `S`, en terminant à la ville `i`, en partant d’une origine fixée.
La transition consiste à prolonger l’itinéraire vers une nouvelle ville `j` qui n’est pas encore dans `S`, en calculant `dp[S | (1 << j)][j] = min(dp[S][i] + dist[i][j])` sur tous les `i` valides. Vous demandez : quel est le moyen le moins coûteux d’atteindre la ville `j` après avoir visité exactement les villes de `S`, en supposant que l’on vient de la ville `i` ?
La partie que les gens oublient généralement — et celle que les intervieweurs remarquent quand elle manque — est l’étape finale : la fermeture de la tournée. Une fois la table de DP remplie, la réponse est `min over all i of (dp[(1<<n)-1][i] + dist[i][0])`, ce qui referme la boucle vers l’origine. Sans cette étape, vous avez résolu le problème du chemin hamiltonien, pas le TSP.
À quoi cela ressemble en pratique
Prenons quatre villes : 0, 1, 2, 3. On commence à la ville 0.
- `dp[{0}][0] = 0` (à l’origine, le coût est nul)
- `dp[{0,1}][1] = dist[0][1]` (trajet de 0 à 1)
- `dp[{0,2}][2] = dist[0][2]` (trajet de 0 à 2)
- `dp[{0,1,2}][2] = min(dp[{0,1}][1] + dist[1][2], dp[{0,2}][2] + dist[2][2])` — mais `dist[2][2] = 0` n’aide pas, donc on retient la première : coût pour atteindre la ville 1, puis aller à 2.
Dessiner ce tableau au tableau blanc — même en esquissant deux ou trois lignes — montre à l’intervieweur que vous comprenez comment la DP construit les trajets de manière incrémentale, au lieu de simplement connaître la formule.
La complexité sans enfumage
Held-Karp s’exécute en O(n² 2ⁿ) en temps et O(n 2ⁿ) en espace. La raison pour laquelle cela devient si coûteux si vite est que le nombre de sous-ensembles de n villes est 2ⁿ, et que pour chaque sous-ensemble on suit n villes de fin possibles, ce qui donne n · 2ⁿ états. Remplir chaque état nécessite de vérifier jusqu’à n transitions, d’où le temps en n² · 2ⁿ. Selon le traitement canonique dans l’article original de Bellman en 1962 et la formulation ultérieure de Held-Karp, il s’agit du meilleur algorithme exact connu pour le TSP du point de vue de la complexité asymptotique.
Connaître la complexité est moins important que de savoir expliquer pourquoi elle explose. « Nous avons un nombre exponentiel de sous-ensembles et, pour chacun, nous suivons l’endroit où l’on se trouve » est une phrase dont un intervieweur se souvient. « O(n² 2ⁿ) » sans cette explication n’est qu’une formule.
Expliquez la NP hardness comme un ingénieur compétent, pas comme un cours magistral
Pourquoi le TSP est difficile au départ
NP-hardness, en langage simple, signifie qu’aucun algorithme connu ne trouve toujours l’itinéraire optimal en temps polynomial quand le nombre de villes augmente. Cela ne veut pas dire que le problème est insoluble. Cela signifie que les meilleures méthodes exactes connues croissent de façon exponentielle, et que pour de grandes entrées, cette croissance exponentielle les rend impraticables. L’entrée du Stanford Encyclopedia of Philosophy sur la complexité computationnelle distingue clairement NP-hard et NP-complete : le TSP (version décisionnelle) est NP-complete ; la version d’optimisation est NP-hard.
La conséquence est ce qui compte pour la performance en entretien sur le travelling salesperson problem : vous ne pouvez pas faire de brute force sur le TSP à grande échelle, et vous ne pouvez pas le résoudre exactement en temps polynomial avec les méthodes connues. C’est la raison pour laquelle le choix de l’algorithme existe.
Comment le dire sans trop en faire
Une explication utile en une ligne : « Le TSP est NP-hard, ce qui veut dire que les meilleurs algorithmes exacts connus ont une complexité exponentielle avec le nombre de villes, donc pour de grandes entrées on utilise des approximations. » Voilà. Vous n’avez pas besoin de dérouler une réduction depuis 3-SAT. Vous n’avez pas besoin d’expliquer le théorème de Cook-Levin.
La distinction entre « difficile » et « impossible » compte. Les candidats qui disent « le TSP est insoluble » perdent des points — non pas parce que l’intervieweur chipote, mais parce que cela signale un manque de précision. Le TSP est soluble pour de petites entrées. Il est résolu exactement par Held-Karp jusqu’à environ 20 villes. « Difficile » signifie « aucun algorithme exact en temps polynomial n’est connu », pas « on abandonne ».
À quoi cela ressemble en pratique
Quand un intervieweur demande « alors pourquoi ne pas faire une brute force ? », la réponse relie la croissance factorielle au point de rupture pratique : « La recherche exhaustive teste toutes les permutations (n-1)!. À 10 villes, cela fait 362 880 itinéraires — gérable. À 20 villes, on dépasse 60 000 milliards. C’est la raison pour laquelle la recherche exacte s’effondre et pourquoi nous avons besoin de DP ou d’approximations. »
Cette réponse tient en trois phrases. Elle est précise, elle n’est pas dramatique, et elle donne à l’intervieweur exactement l’information qu’il cherchait.
Distinguez le TSP des problèmes qu’on lui confond sans cesse
TSP vs plus court chemin vs problème du facteur chinois
TSP vs plus court chemin est une distinction qui piège plus de candidats qu’elle ne le devrait. Le plus court chemin — Dijkstra, Bellman-Ford — cherche l’itinéraire de coût minimal entre deux nœuds spécifiques. Le TSP cherche l’itinéraire de coût minimal qui visite tous les nœuds exactement une fois et revient au point de départ. L’objectif est complètement différent : l’un est un trajet point à point, l’autre une tournée complète.
Le traveling postman problem (aussi appelé Chinese postman problem) est encore différent : il demande l’itinéraire de coût minimal qui parcourt chaque arête au moins une fois, et non chaque nœud. Pensez à un facteur qui doit parcourir chaque rue, versus un vendeur qui doit visiter chaque client une fois. Même graphe, objectif totalement différent.
Pourquoi l’inégalité triangulaire et l’asymétrie comptent
Le TSP métrique ajoute la contrainte que les distances satisfont l’inégalité triangulaire : la distance directe entre deux villes n’est jamais supérieure à la distance en passant par une troisième ville. C’est cette contrainte qui rend possible la garantie d’approximation à 1,5× de l’algorithme de Christofides. Sans elle, aucun facteur d’approximation constant n’est connu, sauf si P = NP.
Le TSP asymétrique abandonne l’hypothèse selon laquelle la distance de la ville A vers la ville B est égale à celle de B vers A. Les routes à sens unique, les liaisons aériennes dirigées et les coûts dépendant du temps créent tous des instances asymétriques. Le problème est nettement plus difficile : beaucoup de résultats d’approximation valables pour le TSP symétrique ne s’appliquent pas.
À quoi cela ressemble en pratique
Imaginez un graphe urbain où la route A→B prend 10 minutes, mais B→A en prend 25 à cause de rues à sens unique. C’est du TSP asymétrique. Maintenant imaginez un graphe où l’inégalité triangulaire est vérifiée — tout raccourci est au moins aussi bon que le passage par une ville intermédiaire. C’est du TSP métrique, et Christofides s’applique. Savoir quelle version vous avez sous les yeux change à la fois le choix de l’algorithme et les garanties d’approximation que vous pouvez avancer.
Répondez aux questions de suivi sans vous faire piéger par le format
Les hypothèses que les intervieweurs veulent vous voir énoncer à voix haute
Avant de vous engager sur un algorithme, demandez-vous : le graphe est-il complet ? Toutes les distances par paires sont-elles connues ? Les distances sont-elles symétriques ? Y a-t-il une contrainte de temps qui rende acceptable une réponse approximative ? Ce ne sont pas des tactiques pour gagner du temps — ce sont les questions qui séparent un candidat qui connaît un seul algorithme TSP d’un candidat qui comprend l’espace du problème.
Les intervieweurs utilisent les questions de suivi pour vérifier si vous répondez au problème posé, ou au problème que vous avez étudié. Un candidat qui demande « s’agit-il d’un TSP métrique ou asymétrique ? » avant de choisir un algorithme montre exactement le type de cadrage des hypothèses qui distingue une pensée senior d’une pensée intermédiaire.
Les erreurs qui font paraître faible une bonne réponse
Le mode d’échec le plus courant : un candidat mémorise « NP-hard » et « programmation dynamique », mais ne parvient pas à les relier aux contraintes de l’énoncé. Il dit : « le TSP est NP-hard donc on utilise la DP », comme si c’était une phrase complète. Ce ne l’est pas. La NP-hardness explique pourquoi la brute force échoue. La DP est une réponse à cela, valable pour de petits n. Le lien entre les deux exige de nommer la contrainte — la taille de l’entrée — qui détermine quelle réponse est appropriée.
La raison structurelle pour laquelle cela pénalise les candidats est que cela donne l’impression qu’ils ont mémorisé la réponse à une autre question. L’intervieweur a posé une question sur un problème précis avec des contraintes précises ; le candidat a répondu à la version abstraite. L’écart est visible, et les intervieweurs expérimentés le remarquent immédiatement.
À quoi cela ressemble en pratique
Une bonne séquence de questions de suivi ressemble à ceci. Intervieweur : « Comment cela évolue-t-il à l’échelle ? » Candidat : « Held-Karp est en O(n² 2ⁿ), donc c’est praticable pour de petits n — disons jusqu’à 20 villes — mais cela s’effondre rapidement au-delà. » Intervieweur : « Que feriez-vous avec une entrée plus grande ? » Candidat : « Je passerais à une heuristique — nearest-neighbor glouton pour la vitesse, ou Christofides si j’ai besoin d’une borne d’approximation démontrable. » Intervieweur : « Quelle est la complexité de Christofides ? » Candidat : « O(n³) pour l’arbre couvrant de poids minimal et les étapes de couplage, donc polynomiale au total, avec une garantie d’optimalité à 1,5× pour le TSP métrique. »
Le candidat ne repart pas de la définition après chaque relance. Il reste dans le problème et progresse par couches. C’est à cela qu’une bonne réponse d’entretien sur le TSP ressemble sous pression.
FAQ
Q : Comment expliquer le travelling salesperson problem en langage simple en entretien ?
Dites-le en une phrase : trouvez l’itinéraire le plus court qui visite chaque ville exactement une fois et revient au point de départ. N’allez pas chercher le vocabulaire de théorie des graphes avant d’avoir formulé cette phrase clairement. La définition est le fondement — tout le reste dépend du fait qu’elle soit comprise d’emblée.
Q : Qu’est-ce qui rend le TSP difficile, et comment décrire la NP-hardness sans paraître pédant ?
NP-hardness signifie qu’aucun algorithme connu ne résout le TSP de manière optimale en temps polynomial quand l’entrée grandit. La conséquence pratique est que la recherche exhaustive teste (n-1)! itinéraires — gérable à 10 villes, catastrophique à 20. Dites cette conséquence à voix haute plutôt que de réciter la classification théorique. « Difficile » veut dire croissance exponentielle, pas « impossible ».
Q : Quand faut-il mentionner la programmation dynamique plutôt qu’une heuristique ou une approximation ?
Utilisez la DP Held-Karp lorsque l’entrée est petite (environ n ≤ 20) et que l’intervieweur attend la réponse optimale exacte. Utilisez une heuristique ou une approximation lorsque l’entrée est grande, que les contraintes de temps sont réelles, ou que l’intervieweur demande ce que vous feriez en production. Nommer la frontière — pas seulement l’algorithme — est ce qui rend la réponse solide.
Q : Comment expliquer à un intervieweur l’état, la transition et la complexité de Held-Karp ?
Définissez l’état comme `dp[S][i]` : le coût minimal pour visiter exactement les villes du bitmask S, en terminant à la ville i. La transition prolonge l’itinéraire vers une ville j non visitée. La réponse finale referme la boucle vers l’origine. La complexité est de O(n² 2ⁿ) en temps et O(n 2ⁿ) en espace. Expliquez toujours pourquoi cela croît ainsi — un nombre exponentiel de sous-ensembles, n extrémités possibles — plutôt que de vous contenter de la formule.
Q : Quels arbitrages les intervieweurs cherchent-ils lorsqu’ils posent une question sur le TSP ?
Ils veulent voir si vous comparez l’exactitude à la scalabilité, si vous choisissez un algorithme en fonction des contraintes énoncées plutôt que par habitude, et si vous reconnaissez ce que vous abandonnez. Choisir Held-Karp sans mentionner son coût exponentiel, ou choisir une heuristique sans préciser qu’elle est approximative, indique dans les deux cas que vous n’avez pas vraiment réfléchi à l’arbitrage. L’arbitrage, c’est la réponse.
Q : En quoi le TSP diffère-t-il d’un problème de plus court chemin ou du problème du facteur chinois ?
Le plus court chemin trouve l’itinéraire le moins coûteux entre deux nœuds spécifiques. Le TSP trouve la tournée complète la moins coûteuse à travers tous les nœuds. Le problème du facteur chinois couvre chaque arête au moins une fois — pensez à un facteur qui parcourt chaque rue, versus un vendeur qui visite chaque client. Même structure de graphe, objectif complètement différent.
Q : Quelles sont les erreurs les plus courantes des candidats lorsqu’ils parlent du TSP ?
Trois erreurs dominent : passer à l’algorithme avant de définir le problème, dire « NP-hard » sans relier cela à l’échec de la brute force, et répondre à la version abstraite du TSP au lieu de la version contrainte dans l’énoncé. Quatrième erreur, moins évidente : dire que le TSP est « insoluble » plutôt que « difficile » — ce qui signale un manque de précision à quiconque connaît le problème.
Q : Comment un recruteur peut-il utiliser cette question pour évaluer la résolution de problèmes et la communication ?
Le TSP est un signal propre sur plusieurs dimensions à la fois : le candidat définit-il avant de résoudre, énonce-t-il les hypothèses avant de choisir un algorithme, peut-il expliquer les conséquences en termes de complexité plutôt que de simplement les réciter, et reste-t-il stable sous la pression des questions de suivi ? Un candidat qui donne une réponse structurée — définition, difficulté, choix d’algorithme, complexité — puis répond aux relances sans repartir de zéro démontre exactement le type de raisonnement qui se transfère aux vrais problèmes d’ingénierie.
Comment Verve AI peut vous aider à préparer votre entretien sur le travelling salesperson problem
Le problème structurel de la préparation au TSP est simple : connaître l’algorithme et être capable de le présenter clairement sous pression réelle sont deux compétences différentes. La plupart des candidats possèdent les connaissances. Ce qui se dégrade en entretien, c’est la séquence — définition avant algorithme, vérification des contraintes avant choix de solution, explication de la complexité avant même que l’intervieweur n’ait à la demander — et cette séquence ne devient fiable qu’avec la répétition et un retour réel.
Verve AI Interview Copilot est conçu précisément pour combler cet écart. Il écoute en temps réel votre réponse pendant que vous la donnez, et non un résumé saisi a posteriori, puis il réagit à ce que vous avez réellement dit — y compris aux parties que vous avez survolées ou à la relance que vous n’aviez pas anticipée. Si vous avez donné l’explication de Held-Karp mais omis l’étape finale de fermeture de la tournée, Verve AI Interview Copilot le repère. Si vous avez dit « NP-hard » sans le relier à la croissance factorielle, il fait ressortir l’écart. Le retour est spécifique à votre réponse, et non à une grille générique du TSP. Verve AI Interview Copilot propose des entretiens blancs qui reproduisent la pression des relances d’un vrai entretien technique — le « pourquoi pas une brute force », le « que feriez-vous à grande échelle », le « quelle est la complexité » — afin que la séquence devienne automatique plutôt que laborieuse.
Conclusion
Le TSP fait moins peur quand vous y répondez dans le bon ordre. Définition d’abord, difficulté ensuite, choix de l’algorithme en troisième, complexité en quatrième. Cette séquence élimine l’emballement parce que chaque étape a un prochain mouvement clair, et l’intervieweur peut vous suivre tout du long.
Répétez le script de 60 secondes une fois — à voix haute, pas dans votre tête. Puis déroulez une fois l’explication de Held-Karp avec un exemple à quatre villes. Ces deux passages suffisent généralement à faire retomber la panique et à transformer une question qui semblait être un piège en une occasion de montrer une pensée structurée.
Jordan Ellis
Archives