[auxym]

As the linked article in parent post points out, this was an open problem in CS for 12 years before someone came up with the tortoise and hare algorithm. You really expect a candidate to come up with it from the top of their head, in a few minutes, during a stressful interview?

[bjoli]

No not the specific solution, but the concept of having to pointers moving at different speeds did be pretty clear no?

It is really not a hard problem. If you are dealing with cirular lists you will end up having to solve it sooner or later. The "open question in CS for 12 years" is probably easier explained by "nobody could be bothered" than "it is hard".

[codefined]

Considering there are limited use cases for pointers moving at different speeds in other fields, no, I wouldn't say it would be easy.

The idea itself, once you hear it, instantly makes sense. But having the ingenuity to thinking of it during a stressful period shouldn't be used as a measure of how good a candidate would be for a position. Especially considering there are hundreds of different ways of approaching such problems.

[bjoli]

I think the opposite. It is a simple problem. I wouldn't expect someone to write a working solution on a whiteboard, but in a reasoning discussion come up with the answer.

Say if you have one list that might be circular from the "starting" element or not circular at all. You simply save the pointer to the first element an compare every subsequent element to that. If you find the end of the list it is not circular. If you find the first element it is circular.

The step from that to a general approach for finding whether a list contains circular references should be simple.

I am however coming from scheme where linked lists are abundant.

Edit: not to say I think it is a good problem for an interview, but I would expect someone to be able to solve the problem in one way or another it without googling. What I am questioning is that it is a hard problem, or a very hard solution.

[michaelcampbell]

Perhaps it wasn't, for you. It is for the VAST majority.

[michaelcampbell]

> but the concept of having to pointers moving at different speeds did be pretty clear no?

> this was an open problem in CS for 12 years before someone came up with the tortoise and hare algorithm.

So, empirically, "no".