Goldman Sachs
3.7 of 5 1,590 reviews
www.goldmansachs.com New York, NY 5000+ Employees

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 Flag Question

Part of a Summer Analyst Interview Review - one of 1,555 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 Flag Response
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 Flag Response
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 Flag Response
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 Flag Response

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


Goldman Sachs – Why Work for Us?

We bring together people, capital and ideas to produce solutions and results for our clients by playing a number of roles: financial advisor, lender, investor and asset manager. A commitment to integrity, team work and… Full Overview

Provided by employer [?]

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

Glassdoor is your free inside look at Goldman Sachs interview questions and advice. All interview reviews posted anonymously by Goldman Sachs employees and interview candidates.