2 ms·
I think there was an error in his analysis of the naive solution for finding loops in linked lists (at http://20bits.com/2008/04/17/interview-questions-loops-in
by smanek 18y ago
I think there was an error in his analysis of the naive solution for finding loops in linked lists (at http://20bits.com/2008/04/17/interview-questions-loops-in-linked-lists/ http://20bits.com/2008/04/17/interview-questions-loops-in-li...)
I don't know Ruby, so correct me if I'm mistaken, but I believe the naive solution presented runs in O(n) space and O(n^2) time (not O(n) time, as the author suggests).
If you used a hash table to keep track of nodes seen so far, you could do O(n) time and space.
The tortoise and the hare solution is quite elegant though.
- cperciva 18y agoThe tortoise and the hare solution is quite elegant though. This approach is more correctly known as Floyd's cycle-finding algorithm, and while it is suboptimal, it comes within a constant factor of the optimum for logspace algorithms.
- smanek 18y agoJust for my own edification, what is the optimal solution? I haven't yet seen a proof on the lower bound of cycle detection, so I don't know if other quicker solutions (like Brent's algorithm) are optimal or are just the best we've found. And I don't think there is anything incorrect with referring to Floyd's cycle-finding algorithm as the tortoise and the hare algorithm. Most literature I've seen mentions the alias too.
- utnick 18y agoHow many of you could have came up with the tortoise and hare solution on your own without seeing this problem previously? Its an elegant solution, but extremely non obvious. I'm kind of bitter about this question cause Microsoft asked me that question when I interviewed... and I only came up with the naive solution :) and then the interviewer smugly explained the tortoise and hare one haha