Do all the things like ++ or -- rants, post your own rants, comment on others' rants and build your customized dev avatarSign Up
C0D44949969dMe: hands interviewer whiteboard marker, then feel free to explain it to me.
NickyBones328369dGiven 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.
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..
> 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.
Root6046569dSell 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"
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')*
Mosesrocks75365dYou would get a Nobel prize if you solve an NP problem
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 ...