6 ms·
There was a linked list interview question going around back then that went: In constant time, without allocating memory, given a pointer to the first element o
by 13of40 8y ago
There was a linked list interview question going around back then that went: In constant time, without allocating memory, given a pointer to the first element of a linked list, how can you tell if it eventually ends in a null or if it loops back on itself at any point? I actually ended up implementing the solution while tracking down a hang in a DCOM service I was working on...
- billsix 8y agoIn constant time? O(1)?
- Matthias247 8y agoIsn’t that normally the 2 pointers (tortoise/hare) thing? If yes then I agree it’s not constant time. I personally hate this kind of interview question. It’s one that is easily answerable when one heard the exact question before (in training for interviews). But super hard to answer if not. And it even does not have big applications in practice - in 20years of programming, I never encountered a problem like this. In the end the question just wastes time on both sides and won’t really tell a lot about the candidate.
- lawn 8y agoHe meant constant memory. It's to invalidate solutions marking items visited. I too got this question at an interview once, and failed. For fun I asked everyone at work and predictably nobody came close to figuring it out.
- 13of40 8y agoNo, I meant O(n) but used the wrong word for it. Marking items visited can actually work, because on any(?) modern OS the memory for the elements in the list would be allocated at even addresses, meaning the low order bit of the Next pointer is always zero and can be reused as a marker.
- JonathanMerklin 8y agoThere was a blog post shared a while ago on HN where the author ranted that it was his least favorite interview question because the solution (fast/slow pointers) was - if I recall correctly - literally somebody's PhD thesis. There was a years-long window where anyone "clever enough" could have waltzed in with a one page paper. If you've never seen the pattern before, there is a very good chance that you're hosed. Edit: found it [1] [1] https://news.ycombinator.com/item?id=7953725 https://news.ycombinator.com/item?id=7953725
- YorkshireSeason 8y agoThe tortoise & hare algorithm [1] was not just discovered by some random PhD student, but by Robert Floyd, who won a Turing award. [1] https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoise_and_Hare https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoi... [2] https://en.wikipedia.org/wiki/Robert_W._Floyd https://en.wikipedia.org/wiki/Robert_W._Floyd
- bboreham 8y agoI used to ask this (cycles in linked list) question all the time, and I found it useful as a way to see how the candidate worked through an unfamiliar problem. No-one gave the 2-pointer answer, ever. For me it wasn’t a pass/fail “do you know the right answer” question, it’s more of a “can I work with this person” question.
- deleted 8y ago[deleted]
- qls 8y agoThis 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 agoI 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 agoThe 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.