## Adobe Interview Question for Member Technical Staffs

• 1
of 1 vote

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 4 vote

we don't really use ratio 2:1. We just make one pointer move little bit (+1) faster than other. if we moved the faster pointer any faster, it could jump over slower pointer and we wont be able to detect the loop in 1 pass. By using steps of 1 and 2 we ensure that we catch the loop 1st time faster pointer passes slower one. BTW using 5:6 or (125:126) would work well too. but it doesn't give any additional benefit.

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

I take last part back...125:126 wont work as well. It has to be 1:2 to make it in one pass.

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

Any combination of speed that we take (F and S) is guaranteed to give result in the same number of cycles as the LCM of F and S. The minimum of that is 2 and hence the ratio 2:1

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

Say in each step, the fast pointer moves F nodes ahead and the slow pointer moves S nodes. So in each step, the distance between the two pointers increases by F-S.

Say there is a loop starting at the B-th node (B>=1), and the loop size is L >= 1 (self-loop is OK). If it takes N steps to detect the loop, we should have

``N >= B and (F - S) * N % L == 0``

This is easy to see that

``N = L * K / ( F - S )``

where K is the smallest number such that L * K >= B and L * K % ( F - S ) == 0.

Then the total cost for detecting a loop can be formulated as

``````( F + S ) * N = L * K * ( F + S ) / ( F - S )
subject to L * K >= B and L * K % ( F - S ) == 0``````

Now consider the case when L and F - S are mutually prime and the loop starts at the head of the list. In this case, we need at least K = F - S to satisfy L * K % ( F - S ) == 0. Then the cost becomes

``L * ( F + S )``

So we should pick the smallest F and S possible to reduce cost. So F = 2 and S = 1 is the best choice.

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

Suppose the distance of loop entry from the starting point is A, and the loop size is B, and the speed ration of the slow and fast pointers is 1:N.

At A'th step the slow pointer reaches the entry, while the fast pointer is
behide the slow pointer by distance X.

``X = (B - ((N - 1) * A) % B)) % B   // note 0<=X<B-1``

It will take floor (X / (N - 1)) steps for the fast pointer to catch the slow pointer.

The total cost is

``Y = (A + floor(X / (N -1)) * (N + 1)``

Obviously

``A * (N + 1) <= Y <= (A + floor ((B - 1) / N - 1)) * (N + 1)``

Since the lower bound is A * (N + 1), we should make N as small as possible.

For curious readers the upper bound is

``````(A + floor ((B - 1) / N - 1)) * (N + 1) < (A + 1  + (B-1)/(N-1))*(N+1)
= (A+1)*(N+1) + (B-1)(1 + 2/(N-1))``````

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

With every step the gap between slower and faster pointer increases by 1...So, gap start as 0 and increments by 1 (until say 2, 3, 4, 5) and then it starts decrementing by 1 (say 5,4,3,2,1,0). once we reach 0 we can say that both pointers point to the same number

Comment hidden because of low score. Click to expand.

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