Amazon Interview Question Software Engineer / Developers


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.

- bluesky on September 24, 2012 | Flag Reply
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)
    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----]

- Hitesh Vaghani on September 25, 2012 | Flag Reply
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;

- sahaj on September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This comment has been deleted.

- Administrator on September 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Abhijit on September 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Dharam on September 24, 2012 | Flag
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.

- snis on September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- brnr on September 30, 2012 | Flag
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 ???

- sreeram on October 01, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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