Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
yes, we can do so.i have no idea when to use which one..
but i can find after how many cycle/s both will meet..
take one count variable...increment it after every comparison of pointer that we used for checking circular link list.
something like this ,
if(pointer are same)
circular link list
else
count++;
we will get count..by using that count we will get cycle count..
cycle_count = count % multiplier_factor(2x,3x)...
Trace it out..
For example if circular link list having 14 node and we use multiplier_factor of 3...
we will get answer in 2nd cycle
1->2->3->4->5->6->7->8->9->10->11->12->13->14->1(just for sake i show you ->1 in last).
Multiplier Factor is 3x
1->4->7->10->13->2->5->8->11->14
[------cycle one-----][-------cycle two----]
int ptr1incr = 1;
int ptr2incr = 2; //this is for 2x
// You can substitute it with 3, 4, 5 etc for 3x, 4x, 5x respectively
int count = 0;
int ptr1pos = 0;
int ptr2pos = 0;
int N = 3; // Total number of nodes
do {
count++;
ptr1pos = (ptr1pos + ptr1incr) % N;
ptr2pos = (ptr2pos + ptr2incr) % N
} while (ptr1pos != ptr2pos);
float total_cycles = (float) count/N;
Could you please elaborate a bit about how did you get into this?
pointers meet @ node # "n-2k" or "(n-k)-k" where (n-k) is the loop size.
@Rajanikant,
Consider this case 1->2->3->4->5->6->7->6.
n = 7;
k = 5;
With what you said.. n - 2k = -3 ; now this negative number does tell you something that a.) loop has very short length and slow pointer probably has not entered the loop when fast pointer completes one cycle, but it certainly does not tell you the meeting node as you explained. or does it??
Assuming slow always being 1x and number of nodes in list be N. We can have following:
N+steps = fast * steps
so there would be N/(fast-1) steps before the two pointers meet. So if we have prior knowledge of number of nodes, we can choose a fast pointer speed such that fast-1 is a factor of number of nodes, so that number of loops to be run can be optimised.
For 3x speed they will meet after 3 rounds. Atleast we have go 3 rounds before checking for meeting. Similarly for 4x speeds.
- bluesky September 24, 2012I don't know about how the choice is made between 2x, 3x, 4x etc. speeds.