Adobe Interview Question
Member Technical StaffsCountry: India
Interview Type: In-Person
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.
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))
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.
- Mak January 30, 2014