## Amazon Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: Phone Interview

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

For 3x speed they will meet after 3 rounds. Atleast we have go 3 rounds before checking for meeting. Similarly for 4x speeds.

I don't know about how the choice is made between 2x, 3x, 4x etc. speeds.

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

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)
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----]

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

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

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

This comment has been deleted.

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

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.

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

@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??

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

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.

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

Would you mind giving an example, I simply can't figure out how to determine the optimized speed, and how it would change based on the count of nodes and size of circle, because there is a difference of steps depending on these variables.

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

what do u mean by after how many cycles do they meet pls explain ???

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.