Re:Microsoft changed how it interviews software developers
by JonathanMerklin on Sunday December 30, 2018 @03:23PM
(#18791114)
There was a blog post shared a while ago on HN where the author ranted that it was his least favorite interview question because the solution (fast/slow pointers) was - if I recall correctly - literally somebody's PhD thesis. There was a years-long window where anyone "clever enough" could have waltzed in with a one page paper.
If you've never seen the pattern before, there is a very good chance that you're hosed.
Edit: found it [1]
Re:Microsoft changed how it interviews software developers
by YorkshireSeason on Sunday December 30, 2018 @06:37PM
(#18792009)
The tortoise & hare algorithm [1] was not just discovered by some random PhD student, but by Robert Floyd, who won a Turing award.
[1] https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoi...
Re:Microsoft changed how it interviews software developers
by 13of40 on Sunday December 30, 2018 @03:23PM
(#18791113)
No, I meant O(n) but used the wrong word for it.
Marking items visited can actually work, because on any(?) modern OS the memory for the elements in the list would be allocated at even addresses, meaning the low order bit of the Next pointer is always zero and can be reused as a marker.
I too got this question at an interview once, and failed. For fun I asked everyone at work and predictably nobody came close to figuring it out.