Citigroup Interview Question


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 2 vote

There are a few good methods to find the starting point of the loop.
I will discuss 2 of them:-

Method 1:-

1. First check if a loop is present in the list, using the concept of fast and slow pointers, as mentioned in a post above by @Engineer1111
2. If a loop is present, your fast pointer is pointing to one of the nodes in the loop
3. Take another pointer, say start, point it to head of list. One by one move start one node ahead and check if it is reachable from the fast pointer(the one in the loop).
4 The first node which is reachable from fast is the starting node of loop

Method 2:- Efficient way

1. Detect if a loop exists using fast and slow pointers
2. Count the number of nodes in the loop if it exists, let it be k
3. Fix a pointer to head of linked list and the other k nodes ahead from the head
4. Move them one node ahead at a time, the point where they meet is the start of the loop

- pulkit.mehra.001 April 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

The problem is somewhat similar to finding the duplicate in a list of values. What we can do is maintain a hashSet of nodes. We will traverse the nodes one by one and will insert their references in the HashSet. If the node is already present in the hashSet we find a cycle on that node. The complexity will be O(n) for traversing the linkedList and O(1) for insertion. The pseudo code for the same will be something like:

1. Initialize HashSet<Node> hashSet = new HashSet<Node>();
2. Initialize the root to the firstElement of the list
3. while null != root do steps (a) and (b)
    a) boolean addedSuccessfully = hashSet.add(root)
    b) if NOT addedSuccessfully 
             return the root; cycle exists at root
        else root = root.next ; continue with loop

- SumitGaur April 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

node * findstarting(node *m)
{
while(m->flag!=1||m!=NULL)
m->link;
if(m->flag==1)
return m;
else
{
printf("no loop found");
return NULL;
}

- Ashok kumar Bhukhar April 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

node * find_start(node * n)
{
	node * slow = n;
	node * fast = n;
	do
	{
		    slow = slow->next;
		    fast = (fast->next)->next;
	}
	while((slow != fast)&&(fast!=NULL))
	if(fast == NULL) 
		{
			printf("No loop found");
			return NULL;
		}
	else
		return slow;

}

The idea is to have 2 pointers , with one going at double the speed, at some point the 2 pointers will point to the same node.

If length of loop is even, it'll finish in one iteration, else 2. Either case O(n)

- Engineer1111 April 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

It is asked to find the starting of loop.......means in which node the loop is started.But your answer only find the exeistence of loop.

- prasenjitx April 07, 2014 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More