4 ms·
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 th
by xvedejas 5y ago
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 5y agoThough not as elegant and concise you can get a similar result by dropping a single marker at log number of steps.
- kerblang 5y agoYes 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_tortoise_and_hare https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoi...
- 908B64B197 5y ago> Most undergrad CS curriculums won't cover it. The serious ones do. At least, I found it to be commonly known.
- gkop 5y agoHeh, I recall that it’s in an early chapter of the original coding interview prep book.
- GuB-42 5y agoAnother one is: you have a list of numbers, more than half of them are the same number, and you have to find it. Ex: 1 2 3 1 1 3 1 => 1 Hints 1- It can be done in one pass, linear time, constant space 2- It doesn't have to be numbers 3- The algorithm it is literally just 2 statements in a loop
- comex 5y agoAre you allowed to modify the list? Edit: I think I figured it out!
- rowanG077 5y agoFeatures in this video: https://www.youtube.com/watch?v=pKO9UjSeLew https://www.youtube.com/watch?v=pKO9UjSeLew
- wahern 5y agoAccording to the solution in the video, the problem upthread was stated incorrectly. There's an additional constraint that only integers in the interval [1, N], where N is the size of the array, are permitted; or at least where the numbers can be trivially mapped to that interval (e.g. subtraction of an offset).