Ranter
Join devRant
Do all the things like
++ or  rants, post your own rants, comment on others' rants and build your customized dev avatar
Sign Up
Comments

NickyBones328369dGiven that triangle inequality holds, you can have a 2factor 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. 
stop558969d@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.

NickyBones328369d@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.

Nanos892869dDidn't I see an analogue solution to that involving, some string and weights through holes..
Slightly related link, since I can't find the video I watched years ago about how to do it..
https://ncbi.nlm.nih.gov/pubmed/...
> An analogue approach to the travelling
> salesman problem using an elastic
> net method. 
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. 
@TempestasLudi that still means it’s a pretty tall order for an interviewer to demand a linear solution that is absolute. Approximations sure that’s a different thing though.

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('nodetspsolver')*
Related Rants

karma11Please make an entire webshop with animated shopping cart in react + redux within a week 👍 We will then re...

dfox3My favorite kind of interview question/challenge is anything that is highly practical for the job. At the curr...

cabbybaby12It was for a job interview, I wouldn't specify what the challenge is but they said I could use any language I ...
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.
rant
wk192