[HN Gopher] The Tortoise, the Hare, and the Cyclical Linked List
       ___________________________________________________________________
        
       The Tortoise, the Hare, and the Cyclical Linked List
        
       Author : rbanffy
       Score  : 8 points
       Date   : 2021-12-15 12:45 UTC (10 hours ago)
        
 (HTM) web link (medium.com)
 (TXT) w3m dump (medium.com)
        
       | Sharlin wrote:
       | Obligatory link: _Hexing the technical interview_ [1]
       | 
       | [1] https://aphyr.com/posts/341-hexing-the-technical-interview
        
       | travisd wrote:
       | Haven't gone through the proof closely, but I suspect this would
       | work for any prime for the tortoise, not just 2 (though 2 is
       | probably optimal in actual implementation). This is the most I've
       | used my discrete math degree in my 2.5 years post undergrad.
        
       | xvedejas wrote:
       | This is a cool little algorithm. I've heard about it first in the
       | context of "nightmarish interview questions" though, where a
       | programmer was meant to derive the technique from thin air :)
        
         | petermcneeley wrote:
         | Though not as elegant and concise you can get a similar result
         | by dropping a single marker at log number of steps.
        
         | kerblang wrote:
         | Yes it is routinely used as a way to humiliate candidates,
         | because it's a perfect brain teaser: Devilishly simple but
         | difficult to conjure unless you've seen it before - "Why
         | couldn't I think of that???" Most undergrad CS curriculums
         | won't cover it.
         | 
         | https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoi...
        
       ___________________________________________________________________
       (page generated 2021-12-15 23:01 UTC)