Re:Microsoft changed how it interviews software developers
by cc81 on Sunday December 30, 2018 @07:33PM
(#18792207)
I don't think it is a very good thought problem because I think very few would figure it out unless they have encountered the algorithm or a similar one before.
It is one that a lot of people will go "Aha, of course" when they hear about it but not figure out themselves.
Re:Microsoft changed how it interviews software developers
by chillacy on Monday December 31, 2018 @02:25AM
(#18793507)
I understand the reasoning now since I know the answer but I still don’t think I would arrive at the answer even with the reasoning. I don’t use it as an interview question so I don’t know if people ever genuinely solve it or just memorize the solution.
In constant memory there's not that many things to do, a single pointer clearly won't be enough as you can't recall if you already visited the node or not, so `K>1` pointers must be used. If any two pointers moved at the same pace they would be duplicated and the second won't give any information. That and the fact that you can only move forward leaves a pretty constraint situation and acts as a guide.
It's not a bad thought problem, but I guess the fact that it's really unlikely to happen in a real world scenario plays against it (the memory on a hash table is probably way cheaper than the extra reasoning this takes). Also, knowing a bit about the answer is an unfair advantage, it might be more of a test on memory than on reasoning, which makes the problem bad for interviews.