Amazon Interview Question for Software Engineer / Developers






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

1. scan the list to compute the length
2. scan again to find the median

O(n)

- Anonymous January 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In one pass:
1. Take two pointers, slow and fast, both pointing to head of list
2. Now move slow point node node next and fast pointer two node next
3. Keep moving until fast pointer reaches to END of list OR 2nd last node (depends on node count in list is odd or even), at this point, slow pointer is at the center of list.

- Anurag Singh January 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good thinking. at first it looks like it is faster but theoretically it has the same complexity as scanning the entire list and traversing to the median.
Because the number of element accesses is the same. i.e. for every iteration, slow pointer accesses 1 element and fast pointer accesses 2 elements --> total accesses 3n/2
which is same as normal traversing. i.e. same complexities but
Practically the time and space you are saving is any overhead for every iteration such as incrementing, checking conditions, any variable retrieval etc..

- blueskin.neo January 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Neo, i feel it shud work faster. Say, if there are 10 elements, the slow pointer is going to move thru 5 elts (1-2-3-4-5) and fast pointer is move thru 5 elts again(2-4-6-8-10).. So ideally wouldnt it be twice the speed, than the normal soln of traversing n finding the median?
Anyway, the interviewer wud be impressed with this soln rather the naive method, for sure. Kudos Anurag!

- AB January 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@AB For the fast pointer to access the elements 2,4,6,... it has to use node.next.next. It uses 2 references. Hence, it uses the same time as the first method. I mean, the interviewer might actually be disappointed that you could not understand that it takes the same time for both and you chose the complicated way.

- Brahadeesh March 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

of course the second one will be faster

- Ant January 30, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Both the algorithms would have same time complexity. We cannot go 2-4-6-8-10 in a linked list, it has to be two moves at once for faster pointer and one move for the smaller pointer.

- Raman February 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

same complexity, the jumping by 2 is actually 1 by 1.

- Anonymous February 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Both have same complexity... Floyd's hare and tortoise algorithm suggested earlier is better off for cycle detection

- ac February 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

想法不错

- qiran1@umbc.edu March 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

teri maa

- Anonymous May 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Function to get to the middle of the LL
mynode *getTheMiddle(mynode *head)
{
mynode *middle = (mynode *)NULL;
int i;

for(i=1; head!=(mynode *)NULL; head=head->next,i++)
{
if(i==1)
middle=head;
else if ((i%2)==1)
middle=middle->next;
}

return middle;
}


check if this is correct...??

- Anonymous January 23, 2013 | Flag Reply


Add a Comment
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.

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