3 ms·
With regards to (2), this is one way of solving the problem. However, your solution uses O(n) memory (where n is the size of the linked list), and the tortoise-
by aquamongoose 12y ago
With regards to (2), this is one way of solving the problem. However, your solution uses O(n) memory (where n is the size of the linked list), and the tortoise-and-hare algorithm uses only O(1) memory. Here's how it works: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_ha...
- thisone 12y agounless the interviewer plans to move the goal posts, there was no specified memory restriction in the original question.
- gohrt 12y agoComplexity optimization is a generally useful skill. "moving the goal posts" is called "every month at work, when you finish 1 task and then move on to another task, instead of going home and getting paid to rest on your laurels"
- thisone 12y agomoving goal posts, is "I asked you for x, you provided me with x, but I really wanted y, so now I'm going to tell you you're wrong" You want someone to answer a programming question within a particular set of boundaries, you set those boundaries.
- dllthomas 12y agoI don't think it has to be "wrong". If I were asking this question, and I was provided with "store them in a hash", I would say something along the lines of "that's a correct solution" and then add additional constraints. "How you adapt in the face of additional constraints" is very much relevant to programming.