4 ms·

In constant time? O(1)?

Matthias247 8y ago
Isn’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 ago
  He 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 ago
    No, 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.
    - dmitrygr 8y ago
      Your solution isn't thread safe :)
      - deleted 8y ago
        [deleted]
      - 13of40 8y ago
        It's in a critical section. (Which you pretty much have to do with the canonical one too, since it can run off the rails if another thread modifies the list.)
  - JonathanMerklin 8y ago
    There 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 ago
      The 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 ago
  I 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]

Isn’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 ago
He 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 ago
  No, 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.
  - dmitrygr 8y ago
    Your solution isn't thread safe :)
    - deleted 8y ago
      [deleted]
    - 13of40 8y ago
      It's in a critical section. (Which you pretty much have to do with the canonical one too, since it can run off the rails if another thread modifies the list.)
- JonathanMerklin 8y ago
  There 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 ago
    The 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 ago
I 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]