Linked List Problems (2002) [pdf] • Hacker News Board

Re: Linked List Problems (2002) [pdf]

#111

Post by michaelcampbell » Mon, Nov 27, 2017, 2:55 PM UTC

bjoli wrote: post #82

auxym wrote: post #75

Earlier quoted context omitted.

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?

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

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

Re: Linked List Problems (2002) [pdf]

#112

Post by michaelcampbell » Mon, Nov 27, 2017, 2:57 PM UTC

bjoli wrote: post #96

codefined wrote: post #87

Earlier quoted context omitted.

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…

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…

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

Re: Linked List Problems (2002) [pdf]

#113

Post by tzs » Tue, Nov 28, 2017, 7:41 AM UTC

Spivak wrote: post #107

tzs wrote: post #31

Earlier quoted context omitted.

Another advantage of 2 is that it works even if the two pointers do not start on the same element.

It's not specifically 2, any two speeds that are coprime will have the same property.

Counterexample: loop of 8 nodes, numbered 0, 1, ..., 7.

Start with one pointer at node 0, moving with speed 5. Start the second pointer at node 1, with speed 3 which is coprime to 5, the speed of the first pointer.

The pointer positions at each step are:

  0 5 2 7 4 1 6 3 repeat
  1 4 7 2 5 0 3 6 repeat

The condition we need in order to guarantee it works regardless of where the two pointers start is that the difference between the speeds is coprime to the cycle length.