Chapter 2 Question 8, simpler solution

[amir-bio]

Hello All,

I just wrote my solution to 2_8. I think m solution is correct and much simpler (however uses O(N) space) But neither the question nor the answer specifies any limitation on the space complexity. I was surprised that my approach was not even mentioned. I've pasted my code below, have I done something wrong?
(I'm also hosting the code at https://gitlab.com/amirha97/coding-practice-project/blob/master/python/chapter2/c2_8.py, more comments there)

def startOfLoop(n):
    d = set()
    while n is not None:
        if n in d:
            return n
        else:
            d.add(n)
        n = n.next

And my Node definition:

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

Update:
The solution to 2_7 also seems to ignore this approach. ( I'm rusty on my Java, but I think java also allows comparing references directly, so this approach should also work) [In case anyone's interested in how I did that: https://gitlab.com/amirha97/coding-practice-project/blob/master/python/chapter2/c2_7.py]

[Frikster]

See #51 . Just like in its case I think the whole point of 2.8 is to understand the algorithm. In an interview your answer would be accepted and then they'll likely ask you to do it without the set. See also hint # 7 in the textbook. There the author discusses an alternative to 2.5 which has no space or time complexity problems but then points out that in an interview the interviewer will most likely accept it and then tell you to redo it in the way they want to see it.

Although I completely agree, it seems a mistake on the part of the author to neglect touching on the trade-offs of doing it with vs without a set. I instinctively used a set the first time I saw this question as well.

You're also right about Java. Here's an implementation using a set in Java. O(n) Time and O(n) Space just like your solution.