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

- -- July 16, 2016 | Flag Reply
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.

- Keerthi July 17, 2016 | Flag Reply
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.

- Keerthi July 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Keerthi July 17, 2016 | Flag Reply
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;

- LANorth July 17, 2016 | Flag Reply
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).

- Sunil July 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous July 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Neethi Elizabeth Joseph July 20, 2016 | Flag Reply
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.

- Anonymous July 20, 2016 | Flag Reply
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?

- sudhakar July 21, 2016 | Flag Reply
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.

- Anonymous July 21, 2016 | Flag Reply
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

- ibimd July 21, 2016 | Flag Reply
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.

- jimmythefung July 23, 2016 | 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