## Google Interview Question for Software Engineers

Country: India
Interview Type: In-Person

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

Assuming it is meeting at n+r position.
Assuming, 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

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

Using induction, it would be equal to (p-1) i.e. length of loop - 1 assuming the indexing starts from 0.

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

Missed the condition where n>=p. If n<p, then q = p, else if n>=p, q = (p*(n/p+1)). This is by induction.

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

By induction, q = (p*(n/p) + 1).

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

``````if n<=p then q=p;
else q=p - (n%p) + n;``````

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

when n = 10, p = 6, then meeting point will be 12. Similarly, when n = 10 p = 6 meeting point will be 14, and so on.
So here is the formula.
meeting point = n + (p - n % p).

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

``````public static int findMeetingPoint(Node 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;
while(p1!=p2){
p1=p1.next;
index++;
}
System.out.println(index);
return index;
}``````

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

``````public static int findMeetingPoint(Node 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;
while(p1!=p2){
p1=p1.next;
index++;
}
System.out.println(index);
return index;
}``````

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

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.

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

i did not get the question. What iss the difference between cycle and loop?

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

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.

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

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

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

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.

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.