Google Interview Question
Software EngineersCountry: India
Interview Type: In-Person
public static int findMeetingPoint(Node head){
Node p1=head;
Node p2=head;
while(p2.next!=null){
p1=p1.next;
p2=p2.next.next;
if(p1==p2){ //meeting point inside the loop
break;
}
}
//to find index of meeting point start from the beginning with p1 count to p2
int index=0;
p1=head;
while(p1!=p2){
p1=p1.next;
index++;
}
System.out.println(index);
return index;
}
public static int findMeetingPoint(Node head){
Node p1=head;
Node p2=head;
while(p2.next!=null){
p1=p1.next;
p2=p2.next.next;
if(p1==p2){ //meeting point inside the loop
break;
}
}
//to find index of meeting point start from the beginning with p1 count to p2
int index=0;
p1=head;
while(p1!=p2){
p1=p1.next;
index++;
}
System.out.println(index);
return index;
}
I think the question asks for a mathematical formula to find the meeting point of fast and slow pointers. Note that the equations derived here have infinite number of solutions as they will keep crossing each other.
The way I approached it is.
Number of nodes before the loop = L
Number of nodes in loop = P
Let H be the number of hops after which both fast and slow pointers meet.
Then the Index of that node at which both meet would be = L + ((H - L) mode Q)
Explanation for it is that beyond the point at which loop starts(i.e. L) node indexes are in a loop but I only kept H(number of hops as linearly increasing).
So if after H hops both slow and fast pointer meet, by that time the fast pointer would have moved a node with index = L + ((2*H - L) mod Q)
Question is asking would be that Index node number say I for which
L + (H- L) mod Q = L + (2*H - L) mod Q
We can get rid of L. So it becomes
(H - L) mod Q = (2*H -L) mod Q
But the above equation have as I said infinite value of H for this indexes might be same. And I think this is what the interviewer intended to see.
Let's say the fast pointer takes k steps for every step taken by the slow pointer. The fast pointer will have taken nk steps when the slow pointer reaches the loop, so its position in the loop will be (nk - n) % p. The distance from the fast pointer to the slow one is thus p - ((nk - n) % p). This will be reached in ceil(p - ((nk - n) % p) / (k-1)) turns. By this time the slow pointer will have travelled n + ceil(p - ((nk - n) % p) / (k-1)) steps, which is the answer.
When the slow node has traveled n steps, fast has traveled (say) kn steps.
If they meet after w steps of the slow node (or kw steps of fast pointer then -
w%p=(kn-n+kw)%p (-n in second expression since we are reducing distance traveled by fast outside the loop)
This means that both side of expression leave same reminder on dividing by p which can be written as
w - lp = (k-1)n + kw - mp (for some l & p)
w(1-k)=(k-1)n+(l-m)p
w=cp-n (c=1-m/1-k)
answer is w%p which is -n%p or (p-n)%p
The question as stated has no unique solution, in the sense of not relying on extra variable. Clearly the answer, q, will be different depending on how much is p2 moving faster than p1.
Here's the mathematical formula:
Let's say p2 is moving faster than p1 by a factor of k.
By the time p1 enters the loop (equivalently, traveled a distance n), p2 would have traveled a distance of kn.
From here we can say the gap between p2 & p1 is G = (kn-n)%P.
Then every subsequent step, s, the gap is increased by an amount (ks-s) = (k-1)s.
The gap keeps increasing until p2 is exactly P ahead of p1. At this point, we have
(k-1)s+G % P =0.
And at this point, the location of p1 meeting p2, which we called "q" can be observed to be:
q = s % P
So we have 3 equations
1. G = (kn-n)%P
2. (k-1)s+G % P = 0
3. q = s % P
1. implies that there is a constant "x" such that Px+G = (kn-n)
2. implies that there is a constant "y" such that Py = (k-1)s+G
3. implies that there is a constant "z" such that Pz + q = s
By manipulating the algebra of the 3 implications, you can obtain the following important result:
q = P [(x+y)/(k-1) - z] - n
Testing - Assume p2 is twice as faster as p1, and we choose set the constants x=y=z=1 (this means the p2 catches p1 without running more than 1 loop).
The result simplifies to:
q = P - n
If the non-cycle part has length 3 and the cycle part has length 4, then
q = 4 - 3 = 1.
Which you can verify by drawing a picture.
Assuming it is meeting at n+r position.
- -- July 16, 2016Assuming, the first pointer is at n+qp + r position, the second pointer is at 2n + 2qp + 2r postion which can be written as n + sp + r
Hence 2n+ 2qp + 2r = n + sp + r
n+r = (s-2q)p
Now I don't know how to represent s & q in terms of n & p