News for hackers. Stuff that matters.
Re:Microsoft changed how it interviews software developers by lawn on Sunday December 30, 2018 @03:00PM (#18791003)
He meant constant memory. It's to invalidate solutions marking items visited.

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.

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]

[1] https://news.ycombinator.com/item?id=7953725

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

[2] https://en.wikipedia.org/wiki/Robert_W._Floyd

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.

Re:Microsoft changed how it interviews software developers by dmitrygr on Sunday December 30, 2018 @05:03PM (#18791624)
Your solution isn't thread safe :)
Re:Microsoft changed how it interviews software developers by 13of40 on Sunday December 30, 2018 @05:25PM (#18791717)
It's in a critical section. (Which you pretty much have to do with the canonical one too, since it can run off the rails if another thread modifies the list.)