Interviewer: How will you solve the travelling salesman problem?

Me: *explains the solution on whiteboard*

Interviewer: It is slow. Can you do it in linear time at least?

Me: It is NP hard so it is not possible. For a restricted case, it may be possible

Interviewer: You are stupid. Do not apply again.

Me: hands interviewer whiteboard marker, then feel free to explain it to me.

Given that triangle inequality holds, you can have a 2-factor approximation in mlog(n) time, using minimum spanning trees. That's something you learn in algorithms course.
But a linear time algorithm? Seems way too niche. And it would still be an approximation.

@NickyBones such an algo would not only be a scientific breakthrough, every major company would pay way more to get him/her/them just into the company.

@stop Apparently, linear *approximation* algorithms exist, at least for Euclidean TSP. Got a bunch of results on google scholar. Not bored enough to check out any of them.

The fact that it is NP hard just means that it is equivalent to a whole lot of problems to which we have not yet found a fast (aka polynomial time) solution. It does not mean that we are sure that there exists no such algorithm.
If you can prove that no polynomial time algorithm exists for TSP, you can go and claim the reward of 1 million dollars for solving the P vs NP conjecture.

Sell on Ebay instead. That's O(1) effort. 😊

Depends on the job, but for 99% of commercial positions, it's also an extremely useless interview question.

Sure, you can jack off about the fact that you're ubergeek enough to have memorized all kinds of heuristic algorithms, but is that an important trait to have as an employee?

I mean to be honest, even IF you were to encounter a situation where the algorithm has practical applications, your real life solution would most likely not matter THAT much.

Consider you are actually writing a route finder for a food delivery service.

Here's what would happen in practice:

Me: "Hey, PM, how many deliveries does a driver do before taking a break?"

PM: "Eh, about 4 or 5"

Me: "Is it OK if I limit it at 7? That way I can just brute force the perfect route in 360 steps"

PM: "Sure"

3 years later:

PM: "Hey bittersweet, our users would like to up that limit to 10 nodes, can you find a better solution than brute force?"

Me: *1m Google search* -- *require('node-tspsolver')*

@bittersweet This.

You would get a Nobel prize if you solve an NP problem