Microsoft Interview Question


Country: -




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

Lets start with two pointers approach.
One gets incremented by one.
Other gets incremented by two.
And if there is a loop, pointers will meet at certain node. Lets call it "meeting point"

At this point, we have two linked list,
First our original link list (in the qustion), starting from start node.
Other one starting from the node next to our meeting point.

And now, this question transforms into "two link list joining at some node, find joining node at which they join".
Answer to that is simple, find length of both lists and their difference, have pointers to the start of both list, increment pointer of longer list by the difference in their length. After this then keep incrementing both by one till they meet.
Hope all of this makes sense.

- buch. October 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

First half sounds pretty good. But once you know the length of the lists their difference is twice the number of nodes that are not in the loop - thus the index can easily be computed. Or I just don't get the "increment both by one till they meet" part.

- aaa October 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

"increment both by one until they meet" works.

Slow pointer went this far:
X (distance between beginning of list and start of circle) + Y (distance between beginning of list and meeting point).

Fast pointer went this far:
X (distance between beginning of list and start of circle)
+ Y (distance between beginning of list and meeting point) + Z (distance between meeting point and start of circle) +
Y (distance between beginning of list and meeting point)

We also know that the fast one went twice as fast as the slow one.
So 2 * (X + Y) = X + Y + Z + Y
Simplified X = Z

That is why it works.

Math win :-)

- Ninja Coder October 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ninja, you are correct, i missed the maths in it, with your explanation this is a much simpler problem.

- buch. October 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The math is not correct. You're assuming that the fast pointer catches the slow pointer on the second iteration of the loop. But for lists with a large start section (without loops) and a small loop, the fast pointer will iterate the loop several time before the catching the slow pointer.

- Anonymous October 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I still think that once you know both lists lengths you can calculate much easier the index. Once you detect the loop you can tell its length. And the overall list length can be determined if you reverse the links so you get back to the head. The difference in lengths/2 is the idx.

- aaa October 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Right.
To summarize your solution:
1. find a node in the loop (one slow and one fast pointer solution) - O(n)
2. determine the length of the cycle (count the number of steps to reach again the loop node from itself) - O(n)
3. starting from the begining of the list reverse the links and count the nodes until the end - the nodes from the loop will be counted once and the ones from outside will be counted twice - O(n)
4. the index of the loop start element is (count step 3. - count step 2.)/2 - O(1)

- Anonymous October 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ninja's calculations shows the way you need to go with this problem.

The solution to this problem is also provided in the book by Gayle, Cracking The Coding Interview.

- Srikant Aggarwal December 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

1) Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4) Move both pointers at the same pace, they will meet at loop starting node.

- jackass October 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

k+1th node I guess

- incognito1729 August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. you need to find the minimum and maximum number in that list
2. then increase every number by (maximum - minimum) iteratively, then the first number where you find it greater then maximum would be the first node of cycle in the list.

for finding the maximum and minimum number you can do through this way
take two iterater it1, it2
iterate it1 by one node
iterate it2 by two nodes

when these two iteraters meet for the 2nd time then it1 has visited all the nodes of linklist,

I think this will work

- Anonymous October 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Only if you're ignoring overflow...

- Anonymous October 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what overflow??

- buch. October 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

algo please for the above problem.

- sam October 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Numerical overflow. For example this algorithm will definitely not work if the list will contain the maximum representable number.

- Anonymous October 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

wow, one might use long for counter, if that overflows one can keep 1000 bytes for just to keep track of counter.
But is this part of the problem. HELL NO!!!
please dont mislead, if you cant offer any solution.

- buch. October 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this one?

loop(List)
{
p1 and p2 are two pointers;
Initially p1 points to start of the list;
for(no of elements in list)
{
p2=p1;
while(p2!= null and p2!=p1)
p2=p2.next;

if(p2==p1) break; //node where loop starts

p1=p1.next;
}
}

Here for each node i will traverse the whole list with another pointer starting from that node and check whether that i reach that node again or not. If i reach the same node than that would be my start node.

- Anonymous October 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How do you know the number of the elements in the list ?

- Anonymous October 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Okay i thought he had told you no of elements.. Anyways its not even required to find the no of elements. Since it is given that there is only one loop here.

i can write the same as,

loop(List)
{
p1 and p2 are two pointers;
Initially p1 points to start of the list;
while(true)
{
p2=p1;
while(p2!= null and p2!=p1)
p2=p2.next;

if(p2==p1) break; //node where loop starts and hence i break from loop since there is only one loop here

p1=p1.next;
}
}

- jainpratik0911 October 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Unless the loop starts at the first element of the list, this:

while(p2!= null and p2!=p1) p2=p2.next;

will run forever

- Anonymous October 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yeah you correct. This is how i corrected my mistake. Tell me if this can work.

loop(List)
{
p1 and p2 are two pointers;
Initially p1 points to start of the list;

p2=p1.next;
int c=1;

while(check(p1,p2,c) and p2!=p1)
{ p2=p2.next;c++; }

/* p2!=p1 will see if loop starts at very 1st node and check function will check loop that starts at other than 1st node */


// p2 points to node where loop starts

}

check(p3,p4,c)
{
int d=1;
while(p3.next!=p4)
{ p3=p3.next;d++; }

if(c==d) return true;

else

if(d<c) return false;

/* when d id less than c, that means now for travelling from p3 to p4 took lesser traversals than for p2 traversing. That will happen incase of a loop. */



}
}

- jainpratik0911 October 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It seems to work, but it has O(n2)complexity
You should check "aaa"'s solution with O(n) complexity.

- Anonymous October 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yeah that one's better :)

- jainpratik0911 October 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In the question I am assuming the linked list ends after the loop completes.

- jainpratik0911 October 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I used a recursive function to iterate the list. While iterating, I make the next pointer to NULL. The function will reach the node whose "next" is NULL. This is the node where loop starts. As my recursive function pulls back, it carries the loop-starting node backwards. Finally, matching the object with loop-starting node, my function figures out the its position in the list.

Node * FindPosition(Node * n, int position)
{
if(n->next == NULL)
return n;
Node * next = n->next;
n->next = NULL;
Node * ret = (FindPosition(next, position + 1);
if ( ret != NULL && ret == n)
cout<<"Position: "<<position<<endl;
n->next = next;
}

- Anonymous October 06, 2011 | Flag Reply


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