Goldman Sachs

  www.goldmansachs.com
Work in HR? Unlock Free Profile

Goldman Sachs Summer Analyst Interview Question

I interviewed in New York, NY and was asked:
"How do you check if a Linked List has a recurring loop?"
Tags: technical, analytical, algorithm, linked list
Add Tags [?]
Answer

Part of a Summer Analyst Interview Review - one of 1,590 Goldman Sachs Interview Reviews

Answers & Comments

0
of 0
votes

I thought of using a hash table to store the values of each node, and adding values to the table as we iterate through the Linked List. This would only work if the values are unique. It was the not fastest or best either. With some hints, I came to a better solution of iterating through the Linked List twice - one that hops 1 node each time and the other hops 2 nodes each time. If the latter loop surpasses or reaches a node from the first, there exists a loop. There would be no loop of course when both reach the end of the Linked List.

- Interview Candidate on Feb 16, 2013
0
of 0
votes

There is a blog discussing this problem, as well as another problem to find the entry node in the loop.

- Harry on Feb 17, 2013
0
of 0
votes

There is a blog discussing this problem, as well as another problem to find the entry node in the loop. The link of the blog is:

http://codercareer.blogspot.com/2012/01/no-29-loop-in-list.html

- Harry on Feb 17, 2013
1
of 1
vote

/*
     Jun Zheng, Rice Univ
     C++, Xcode 4.5.2
     Interview question of GS
     Check if a linkedlist has circle, phead points to the start node
     */
    bool ifCircular(node<T>* phead){
        node<T>* pfast=phead;
        node<T>* pslow=phead;

        while(pfast !=NULL && pfast->next !=NULL){
            pfast=pfast->next->next;
            pslow=pslow->next;
            if(pfast==pslow) return true;
        }
        return false;
    }

- Jun Zheng on Feb 20, 2013

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.