Algorithms and Data Structures · Senior · Question 25 of 75
An interviewer describes a problem that reduces to the traveling salesman problem. What's a sensible response?
- 1Say it's unsolvable and that no answer exists
- 2Promise an O(n log n) algorithm using sorting by distance
- ✓Correct answer: Note it's NP-hard, then propose heuristics or exact DP for small n
Explanation
No polynomial algorithm is known. Exact bitmask DP is O(n² × 2ⁿ), fine up to about 20 cities. For real routes you use heuristics such as nearest neighbor plus 2-opt, or a solver, and accept a near-optimal answer.