3 ms·

This is a pretty standard linked list question (called cycle detection) – one of the easiest questions on LeetCode. You can use the two-pointer method to just d

by qls 8y ago

This is a pretty standard linked list question (called cycle detection) – one of the easiest questions on LeetCode. You can use the two-pointer method to just detect if there's a cycle. If you want to find the node that the cycle starts at, you can just walk the slow pointer from the slow/fast meeting point and a pointer to the head of the list 1 step at a time until they both meet (there's a simple explanation for this that I won't bother writing out).

chillacy 8y ago
I must admit I didn’t figure that one out till I saw the solution which was a “oh duh” moment. I don’t think i would have ever stumbled upon it without lots of hints during an interview.
- dietr1ch 8y ago
  The constraints, if correctly stated, can help a lot to figure what to do if you take a look at them closely. In constant memory there's not that many things to do, a single pointer clearly won't be enough as you can't recall if you already visited the node or not, so `K>1` pointers must be used. If any two pointers moved at the same pace they would be duplicated and the second won't give any information. That and the fact that you can only move forward leaves a pretty constraint situation and acts as a guide. It's not a bad thought problem, but I guess the fact that it's really unlikely to happen in a real world scenario plays against it (the memory on a hash table is probably way cheaper than the extra reasoning this takes). Also, knowing a bit about the answer is an unfair advantage, it might be more of a test on memory than on reasoning, which makes the problem bad for interviews.
  - cc81 8y ago
    I don't think it is a very good thought problem because I think very few would figure it out unless they have encountered the algorithm or a similar one before. It is one that a lot of people will go "Aha, of course" when they hear about it but not figure out themselves.
  - chillacy 8y ago
    I understand the reasoning now since I know the answer but I still don’t think I would arrive at the answer even with the reasoning. I don’t use it as an interview question so I don’t know if people ever genuinely solve it or just memorize the solution.

by qls 8y ago

chillacy 8y ago

I must admit I didn’t figure that one out till I saw the solution which was a “oh duh” moment. I don’t think i would have ever stumbled upon it without lots of hints during an interview.

dietr1ch 8y ago
The constraints, if correctly stated, can help a lot to figure what to do if you take a look at them closely. In constant memory there's not that many things to do, a single pointer clearly won't be enough as you can't recall if you already visited the node or not, so `K>1` pointers must be used. If any two pointers moved at the same pace they would be duplicated and the second won't give any information. That and the fact that you can only move forward leaves a pretty constraint situation and acts as a guide. It's not a bad thought problem, but I guess the fact that it's really unlikely to happen in a real world scenario plays against it (the memory on a hash table is probably way cheaper than the extra reasoning this takes). Also, knowing a bit about the answer is an unfair advantage, it might be more of a test on memory than on reasoning, which makes the problem bad for interviews.
- cc81 8y ago
  I don't think it is a very good thought problem because I think very few would figure it out unless they have encountered the algorithm or a similar one before. It is one that a lot of people will go "Aha, of course" when they hear about it but not figure out themselves.
- chillacy 8y ago
  I understand the reasoning now since I know the answer but I still don’t think I would arrive at the answer even with the reasoning. I don’t use it as an interview question so I don’t know if people ever genuinely solve it or just memorize the solution.