3 ms·
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 everyon
by lawn 8y ago
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.
- 13of40 8y agoNo, 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.
- JonathanMerklin 8y agoThere 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 https://news.ycombinator.com/item?id=7953725
- YorkshireSeason 8y agoThe 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_Tortoise_and_Hare https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoi... [2] https://en.wikipedia.org/wiki/Robert_W._Floyd https://en.wikipedia.org/wiki/Robert_W._Floyd