> ok great, now say that you can't find any satisfying prior art for this on Google, how would you reason through your own solution?
So then I try and give them a O(n^3) solution (or something).
Of course this isn't accepted as there's a better O(n^2) solution, which can always be found by googling, and I fail the interview.
The "turtle and the hare" problem of finding a loop in a single linked list in O(n) time and O(1) memory is the perfect example. It's easy if you know the answer (or can google) but basically impossible if you don't.
What did the interviewer do when I said I couldn't do better than a hashmap? He laughed and said "not many can".
I’m not familiar with this one but have been thinking about it for a few minutes and think I have an answer (granted I think it will depend on language and OS whether it would work)
The gist of it is: walk the list and after each step, multiply the previous node’s pointer by negative one.
If the current node’s pointer is negative you’ve found a loop (because you colored it by inverting the pointer in a previous step).
Clean up by starting at the beginning and multiplying all pointers by negative one until you reach the last one you inverted. Then return your answer (true).
If you reach a null pointer there is no loop because you’ve gotten to the end of the list. Clean up by going through again and multiplying all the nodes by negative one. Then return your answer (false).
Your worst case running time is 2n (if there is no loop) which reduces to O(n) and you use O(1) memory because you’re coloring the list by using the already existing pointers in the list.
So then I try and give them a O(n^3) solution (or something).
Of course this isn't accepted as there's a better O(n^2) solution, which can always be found by googling, and I fail the interview.
The "turtle and the hare" problem of finding a loop in a single linked list in O(n) time and O(1) memory is the perfect example. It's easy if you know the answer (or can google) but basically impossible if you don't.
What did the interviewer do when I said I couldn't do better than a hashmap? He laughed and said "not many can".