Master travelling salesperson problem interview performance with a 60-second answer: define TSP simply, choose exact vs approximate, then explain Held-Karp.
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.
This article gives you the answer in the order that works: plain-English definition first, then the choice between exact and approximate, then the Held-Karp walkthrough, then the follow-ups. Rehearse that sequence once and the panic spiral stops.
Say What TSP Actually Is Before You Say Anything Clever
What TSP means in plain English
The travelling salesperson problem is this: given a list of cities and the distances between them, find the shortest possible route that visits every city exactly once and returns to the starting point. That's it. One sentence. You should be able to say it in under ten seconds without looking at a whiteboard.
The reason candidates don't say it that cleanly is that they've internalized TSP as a graph theory concept rather than as a problem statement. When you internalize it as a concept, you reach for the machinery — NP-hardness, dynamic programming, bitmask DP — before you've told the interviewer what you're optimizing. That's backwards. The definition is not a formality you get through on the way to the real answer. It is the foundation the rest of your answer sits on.
According to the formal treatment in Introduction to Algorithms (Cormen et al.), TSP is classified as NP-hard, meaning no polynomial-time algorithm is known that finds the optimal solution for all inputs. That classification matters, but it comes after the definition, not before it.
Why interviewers ask it at all
The travelling salesperson problem interview isn't a memory test. Interviewers who ask TSP are watching for something more specific: can this person translate a hard optimization problem into clean assumptions before they start solving it? Can they make a deliberate choice between exactness and practicality based on constraints, rather than defaulting to the most impressive-sounding algorithm they know?
In coaching sessions, the most common failure mode I've seen is candidates jumping straight to dynamic programming before they've said what the DP is solving. They'll say "so we use bitmask DP over subsets of visited cities" and the interviewer nods politely, then asks "but what's the actual problem?" — and the candidate is suddenly explaining the definition from inside the solution, which is much harder. The definition should come first, stated calmly, as if you've explained it to a colleague over lunch. Everything after that is cleaner.
Give the 60-Second TSP Answer You Can Actually Say Out Loud
The memorized script that sounds natural
A strong TSP interview answer has four moves, in order. You don't need more than 90 seconds for all four.
First, define the problem: "TSP is the problem of finding the shortest route that visits every node exactly once and returns to the origin." One sentence.
Second, name the hard part: "The difficulty is that the number of possible routes grows factorially with the number of cities, so brute-force search stops being viable very quickly."
Third, choose your solution based on constraints: "For small inputs — say, fewer than 20 cities — we can use exact dynamic programming with Held-Karp, which runs in O(n² 2ⁿ) time. For larger inputs, we'd use an approximation or heuristic — greedy nearest-neighbor, or Christofides' algorithm if we need a provable bound."
Fourth, invite the follow-up: "Do you want me to go deeper on the DP approach, or would it be more useful to talk through the heuristic side?"
That last move is the one most candidates skip. It signals that you understand there are two valid paths and you're not going to force the interviewer to sit through the one they don't need. According to research on technical interview performance published by Harvard Business Review, structured communication and explicit trade-off framing are among the strongest signals hiring managers use to distinguish senior from mid-level candidates.
What this looks like in practice
Imagine you're at the whiteboard. The interviewer says: "Tell me about the travelling salesperson problem." A common TSP interview answer mistake is to immediately draw a graph with five nodes and start labeling edges. Don't. Say the definition out loud first, then draw the graph. The graph should illustrate the definition, not replace it.
In practice, candidates who rehearse a four-move script sound markedly less rehearsed than candidates who wing it, because structure removes the cognitive load of deciding what to say next. One candidate I coached had a strong conceptual understanding of TSP but would ramble through three or four competing framings before settling on one. After drilling the four-move script twice, the answer became sharp enough that the interviewer moved directly to follow-ups — which is exactly what you want, because follow-ups are where you demonstrate depth.
Choose Between Exact DP and a Heuristic Instead of Pretending There Is One Right Answer
When exact dynamic programming is the right move
Held-Karp is the right answer when the interviewer signals they want rigor, when the input size is small, or when the problem is framed as a classroom exercise. The method is exact — it finds the optimal route — and it's the standard DP approach for TSP in academic and interview settings. The state encodes which cities have been visited and where the route currently ends, and the transition builds up optimal sub-routes until the full route is reconstructed.
The structural limit is clear: Held-Karp runs in O(n² 2ⁿ) time and O(n 2ⁿ) space. At n = 20, that's about 20 million states, which is tractable. At n = 30, it's over a billion. Exactness is useful until the state space stops being practical, and the honest answer names that boundary rather than pretending DP scales forever.
When a heuristic is the smarter answer
Heuristics are not second-class answers. For approximation for TSP problems in real-world settings, they are often the only honest answer. Greedy nearest-neighbor is fast and simple: start at a city, always move to the nearest unvisited city, return to the start. It doesn't guarantee optimality, but it runs in O(n²) and produces routes that are often within 20–25% of optimal.
Christofides' algorithm is the more principled option: it guarantees a route no worse than 1.5× the optimal for metric TSP (where distances satisfy the triangle inequality). For many production systems, a 1.5× bound with polynomial runtime is far more valuable than an exact answer that takes exponential time to compute.
What this looks like in practice
Consider two scenarios. In the first, you're in an interview and the problem is stated as "twelve cities, find the optimal tour." Held-Karp is the right answer. The input is small, the interviewer wants to see the DP structure, and exactness is achievable.
In the second scenario, the problem is "12,000 delivery stops, optimize the route for a same-day courier fleet." No one is running Held-Karp on 12,000 nodes. The answer is a heuristic or a metaheuristic — simulated annealing, genetic algorithms, or a commercial solver. Circuit board routing and vehicle routing systems used in logistics, for example, have relied on approximation algorithms since the 1970s precisely because the input sizes make full optimality a trap. The NIST Dictionary of Algorithms and Data Structures documents the scaling behavior of exact TSP algorithms and explains why approximation methods dominate in practice.
The candidate who can name this transition — from exact to approximate, and why — is the one who sounds like they've thought about the problem beyond the classroom.
Walk Through Held-Karp Like You're At a Whiteboard
The state, the transition, and the ugly part
The Held-Karp algorithm interview explanation works best when you anchor it to the state definition before you write any transitions. The state is `dp[S][i]`, where `S` is a bitmask representing the set of cities visited so far, and `i` is the city where the current route ends. The value stored is the minimum cost to visit exactly the cities in `S`, ending at city `i`, starting from a fixed origin.
The transition is: to extend the route to a new city `j` not yet in `S`, compute `dp[S | (1 << j)][j] = min(dp[S][i] + dist[i][j])` over all valid `i`. You're asking: what's the cheapest way to reach city `j` after visiting exactly the cities in `S`, given that we just came from city `i`?
The part people usually forget — and the part interviewers notice when it's missing — is the final step: completing the tour. After filling the DP table, the answer is `min over all i of (dp[(1<<n)-1][i] + dist[i][0])`, which closes the loop back to the origin. Without that step, you've solved the Hamiltonian path problem, not TSP.
What this looks like in practice
Take four cities: 0, 1, 2, 3. Start at city 0.
- `dp[{0}][0] = 0` (at the origin, cost is zero)
- `dp[{0,1}][1] = dist[0][1]` (traveled from 0 to 1)
- `dp[{0,2}][2] = dist[0][2]` (traveled from 0 to 2)
- `dp[{0,1,2}][2] = min(dp[{0,1}][1] + dist[1][2], dp[{0,2}][2] + dist[2][2])` — but `dist[2][2] = 0` doesn't help, so we take the first: cost of reaching city 1, then moving to 2.
Drawing this table on a whiteboard — even sketching two or three rows — shows the interviewer that you understand how the DP builds routes incrementally rather than just knowing the formula.
Complexity without hand-waving
Held-Karp runs in O(n² 2ⁿ) time and O(n 2ⁿ) space. The reason it gets expensive so fast is that the number of subsets of n cities is 2ⁿ, and for each subset you track n possible ending cities, giving n · 2ⁿ states. Filling each state requires checking up to n transitions, hence the n² · 2ⁿ time. According to the canonical treatment in Bellman's original 1962 paper and the later Held-Karp formulation, this is the best known exact algorithm for TSP in terms of asymptotic complexity.
Knowing the complexity matters less than being able to explain why it gets expensive. "We have exponentially many subsets and for each one we're tracking where we are" is a sentence an interviewer remembers. "O(n² 2ⁿ)" without that explanation is just a formula.
Explain NP-hardness Like a Competent Engineer, Not a Lecture Hall
Why TSP is hard in the first place
NP-hardness, in plain language, means there is no known algorithm that always finds the optimal route in polynomial time as the number of cities grows. It doesn't mean the problem is unsolvable. It means the best known exact methods scale exponentially, and for large inputs, that exponential growth makes them impractical. The Stanford Encyclopedia of Philosophy's entry on computational complexity distinguishes NP-hard from NP-complete clearly: TSP (decision version) is NP-complete; the optimization version is NP-hard.
The consequence is what matters for travelling salesman problem interview performance: you can't brute-force TSP at scale, and you can't solve it exactly in polynomial time with any known method. That's the reason the algorithm choice exists.
How to say it without overexplaining
A useful one-line explanation: "TSP is NP-hard, meaning the best known exact algorithms scale exponentially with the number of cities, so for large inputs we use approximations instead." That's it. You don't need to sketch a reduction from 3-SAT. You don't need to explain the Cook-Levin theorem.
The distinction between "hard" and "impossible" matters. Candidates who say "TSP is unsolvable" lose points — not because the interviewer is being pedantic, but because it signals imprecision. TSP is solvable for small inputs. It's exactly solved by Held-Karp for n up to about 20. "Hard" means "no polynomial-time exact algorithm is known," not "we give up."
What this looks like in practice
When an interviewer asks "so why not brute force?", the answer connects factorial growth to the practical break point: "Brute force checks all (n-1)! permutations. At 10 cities that's 362,880 routes — manageable. At 20 cities it's over 60 trillion. That's the reason exact search breaks down and why we need DP or approximations."
That answer is three sentences. It's precise, it's not dramatic, and it gives the interviewer exactly the information they were looking for.
Separate TSP From the Problems People Keep Mixing It Up With
TSP vs shortest path vs traveling postman problem
TSP vs shortest path is a distinction that trips up more candidates than it should. Shortest path — Dijkstra's algorithm, Bellman-Ford — finds the minimum-cost route between two specific nodes. TSP finds the minimum-cost route that visits all nodes exactly once and returns to the start. The goal is completely different: one is point-to-point, the other is a complete tour.
The traveling postman problem (also called the Chinese postman problem) is different again: it asks for the minimum-cost route that traverses every edge at least once, not every node. Think of a mail carrier who needs to walk every street, versus a salesperson who needs to visit every customer once. Same graph, completely different objective.
Why triangle inequality and asymmetry matter
Metric TSP adds the constraint that distances satisfy the triangle inequality: the direct distance between two cities is never more than the distance through a third city. This constraint is what makes Christofides' algorithm's 1.5× approximation guarantee possible. Without it, no constant-factor approximation is known unless P = NP.
Asymmetric TSP drops the assumption that the distance from city A to city B equals the distance from B to A. One-way roads, directed flight routes, and time-dependent costs all create asymmetric instances. The problem is strictly harder: many approximation results that hold for symmetric TSP don't carry over.
What this looks like in practice
Consider a city graph where road A→B takes 10 minutes but B→A takes 25 minutes due to one-way streets. That's asymmetric TSP. Now consider a graph where the triangle inequality holds — every shortcut is at least as good as going through an intermediate city. That's metric TSP, and Christofides applies. Knowing which version you're looking at changes both the algorithm choice and the approximation guarantees you can claim.
Answer the Follow-Up Questions Without Getting Tricked by the Format
The assumptions interviewers want you to state out loud
Before you commit to an algorithm, ask: is the graph complete? Are all pairwise distances known? Are distances symmetric? Is there a time constraint that makes an approximate answer acceptable? These aren't stalling tactics — they're the questions that separate a candidate who knows one TSP algorithm from a candidate who understands the problem space.
Interviewers use follow-up questions to probe whether you're answering the problem in front of you or the problem you studied. A candidate who asks "is this metric TSP or asymmetric?" before choosing an algorithm is demonstrating exactly the kind of assumption-setting that distinguishes senior from mid-level thinking.
The mistakes that make a good answer sound weak
The most common failure mode: a candidate memorizes "NP-hard" and "dynamic programming" but can't connect them to the constraints in the prompt. They say "TSP is NP-hard so we use DP" as if that's a complete sentence. It isn't. NP-hardness explains why brute force fails. DP is one response to that, valid for small n. The connection between the two requires naming the constraint — input size — that determines which response is appropriate.
The structural reason this hurts candidates is that it sounds like they've memorized the answer to a different question. The interviewer asked about a specific problem with specific constraints; the candidate answered the abstract version. That gap is visible, and experienced interviewers notice it immediately.
What this looks like in practice
A strong follow-up sequence looks like this. Interviewer: "How does this scale?" Candidate: "Held-Karp is O(n² 2ⁿ), so it's tractable for small n — say, up to 20 cities — but it breaks down quickly beyond that." Interviewer: "What would you do with a larger input?" Candidate: "I'd move to a heuristic — greedy nearest-neighbor for speed, or Christofides if I need a provable approximation bound." Interviewer: "What's the complexity of Christofides?" Candidate: "O(n³) for the minimum spanning tree and matching steps, polynomial overall, with a 1.5× optimality guarantee for metric TSP."
The candidate doesn't reset to the definition after each follow-up. They stay inside the problem and move through the layers. That's what a strong TSP interview answer looks like under pressure.
FAQ
Q: How do you explain the travelling salesperson problem in plain English in an interview?
Say it in one sentence: find the shortest route that visits every city exactly once and returns to the start. Don't reach for the graph theory vocabulary until you've said that sentence clearly. The definition is the foundation — everything else depends on it landing first.
Q: What makes TSP hard, and how should you describe NP-hardness without sounding pedantic?
NP-hardness means no known algorithm solves TSP optimally in polynomial time as input grows. The practical consequence is that brute force checks (n-1)! routes — manageable at 10 cities, catastrophic at 20. Say that consequence out loud rather than reciting the theoretical classification. "Hard" means exponential scaling, not "impossible."
Q: When should you mention dynamic programming versus a heuristic or approximation?
Use Held-Karp DP when the input is small (roughly n ≤ 20) and the interviewer wants the exact optimal answer. Use a heuristic or approximation when the input is large, time constraints are real, or the interviewer asks what you'd do in production. Naming the boundary — not just the algorithm — is what makes the answer strong.
Q: How do you walk an interviewer through the Held-Karp state, transition, and complexity?
Define the state as `dp[S][i]`: minimum cost to visit exactly the cities in bitmask S, ending at city i. The transition extends the route to an unvisited city j. The final answer closes the loop back to the origin. Complexity is O(n² 2ⁿ) time and O(n 2ⁿ) space. Always explain why it scales that way — exponentially many subsets, n possible endpoints — not just what the formula is.
Q: What trade-offs are interviewers looking for when they ask about TSP?
They want to see you weigh exactness against scalability, choose an algorithm based on stated constraints rather than habit, and acknowledge what you're giving up. Choosing Held-Karp without noting its exponential cost, or choosing a heuristic without noting it's approximate, both signal that you haven't thought through the trade-off. The trade-off is the answer.
Q: How is TSP different from a shortest-path problem or the traveling postman problem?
Shortest path finds the cheapest route between two specific nodes. TSP finds the cheapest complete tour through all nodes. The traveling postman problem covers every edge at least once — think mail carrier covering every street, versus salesperson visiting every customer. Same graph structure, completely different objective.
Q: What are the most common mistakes candidates make when discussing TSP?
Three mistakes dominate: jumping to the algorithm before defining the problem, saying "NP-hard" without connecting it to why brute force fails, and answering the abstract version of TSP instead of the constrained version in the prompt. The fourth, less obvious mistake: saying TSP is "unsolvable" rather than "hard" — which signals imprecision to anyone who knows the problem.
Q: How can a recruiter use this question to judge problem-solving and communication skill?
TSP is a clean signal for several dimensions at once: does the candidate define before solving, do they name assumptions before choosing an algorithm, can they explain complexity consequences rather than just recite them, and do they stay steady under follow-up pressure? A candidate who delivers a structured answer — definition, hard part, algorithm choice, complexity — and then fields follow-ups without resetting is demonstrating exactly the kind of thinking that transfers to real engineering problems.
How Verve AI Can Help You Prepare for Your Interview With the Travelling Salesperson Problem
The structural problem with TSP prep is that knowing the algorithm and being able to deliver it clearly under live pressure are two different skills. Most candidates have the knowledge. What breaks down in the room is the sequence — definition before algorithm, constraint-check before solution choice, complexity explanation before the interviewer has to ask — and that sequence only becomes reliable through repetition with real feedback.
Verve AI Interview Copilot is built for exactly that gap. It listens in real-time to your answer as you give it, not to a typed summary after the fact, and it responds to what you actually said — including the parts you glossed over or the follow-up you didn't anticipate. If you delivered the Held-Karp explanation but skipped the final tour-completion step, Verve AI Interview Copilot catches that. If you said "NP-hard" without connecting it to factorial growth, it surfaces the gap. The feedback is specific to your answer, not to a generic TSP rubric. Verve AI Interview Copilot runs mock interviews that replicate the follow-up pressure of a real technical screen — the "why not brute force," the "what would you do at scale," the "what's the complexity" — so the sequence becomes automatic rather than effortful.
Conclusion
TSP is less scary when you answer it in the right order. Definition first, hard part second, algorithm choice third, complexity fourth. That sequence removes the spiral because each step has a clear next move, and the interviewer can follow you the whole way.
Rehearse the 60-second script once — out loud, not in your head. Then walk through the Held-Karp explanation once with a four-city example. Those two passes are usually enough to stop the panic and turn a question that felt like a trap into one that feels like an opportunity to show structured thinking.
James Miller
Career Coach
