Do all the things like ++ or -- rants, post your own rants, comment on others' rants and build your customized dev avatarSign Up
From the creators of devRant, Pipeless lets you power real-time personalized recommendations and activity feeds using a simple APILearn More
C0D4657632yMe: 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.
Nanos110312yDidn'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.
Root764562ySell 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')*
You would get a Nobel prize if you solve an NP problem
dfox3My favorite kind of interview question/challenge is anything that is highly practical for the job. At the curr...
karma11Please make an entire webshop with animated shopping cart in react + redux within a week 👍 We will then re...
cabbybaby12It was for a job interview, I wouldn't specify what the challenge is but they said I could use any language I ...