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

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.