## Microsoft Interview Question

• 0

Country: -

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

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

"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 :-)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Right.
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)

Comment hidden because of low score. Click to expand.
0

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.

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.

Comment hidden because of low score. Click to expand.
0

k+1th node I guess

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

Comment hidden because of low score. Click to expand.
0

Only if you're ignoring overflow...

Comment hidden because of low score. Click to expand.
0

what overflow??

Comment hidden because of low score. Click to expand.
0

algo please for the above problem.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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!!!

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

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.

Comment hidden because of low score. Click to expand.
0

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

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;
}
}

Comment hidden because of low score. Click to expand.
0

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

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

will run forever

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. */

}
}

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

yeah that one's better :)

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.

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;
}

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.

### 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.