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)

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.

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

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..

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

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!

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

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

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

of course the second one will be faster

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.

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

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

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

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

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

teri maa

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

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

{
if(i==1)
else if ((i%2)==1)
middle=middle->next;
}

return middle;
}

check if this is correct...??

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.