3 ms·
"What The Interviewer Says: How would you find a cycle in a singly linked list?" I hate when interviewers ask that shit for web developer jobs. I can explain
by teej 18y ago
"What The Interviewer Says: How would you find a cycle in a singly linked list?"
I hate when interviewers ask that shit for web developer jobs. I can explain the intricacies of Javascript and tell you why I use Active Record even though it's shit, but all you want to see is how well I can recite the Gang of Four.
- timr 18y agoThe list-cycle problem is from Knuth, not Design Patterns.
- eru 18y agoOr any other basic text. SICP has it, too. And they have exactly the same follow up questiof of "reduce the space usage from O(n) to O(1)", too. (Incidentally a related method is know as "pollard's rho" and used to factor integers.)
- gms 18y agoCan you explain how Pollard can be used to find cycles in a linked list?
- eru 18y agoPlease have a look at http://en.wikipedia.org/wiki/Pollard_rho http://en.wikipedia.org/wiki/Pollard_rho "The rho algorithm is based on Floyd's cycle-finding algorithm [...]" (which can be found at http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#Tortoise_and_hare http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorit...)