## Amazon Interview Question for SDE1s

Country: India
Interview Type: In-Person

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

There are many ways to do it.. One simple technique is
1) Traverse to the middle node
2) Seperate the list starting from the next node of middle node.
So now you will have two list...

List1 - header to middle node
List2 - next of middle node to tail

3) Do a two- way merge on List1 and List2

complexity: O(n), n is the total no of nodes in the list,
space; O(1) - I don't think making a list into two halves is an extra space. So, it takes constant space... I'm not 100 % sure about this. Can any one confirm..

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

I think you are right.
For your question : "space; O(1) - I don't think making a list into two halves is an extra space. So, it takes constant space... I'm not 100 % sure about this. Can any one confirm."

my answer is that when you are traversing to middle of the list you are just forwarding the pointer towards middle node, which is O(1) space operation.
Hence it is surely O(1) space solution.

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

but how would you know which node is middle node. unless you traverse till the end you will not know the middle element. so we need to traverse again then it would be O(n2).

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

Middle node can be found by using fast and slow pointer. When fast pointer will reach to the last node, slow pointer will point the middle node. Then merge can be done.

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

``````Node convertList(Node first, Node middle)
{
if(middle == null)
return null;

Node tempFirst = first.next;
Node tempMiddle = middle.next;

first.next = middle;
middle.next = convertList(tempFirst, tempMiddle);

return first;
}``````

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

If the pattern contains more alphabets, such that, say resultant should be like a1->b1->c1-d1-a2->b2->c2-d2-a3->b3->c3-d3, then do we need to have a 'n'-way merge mechanism?

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

``````*curr = head;
for(int i=0; i < length/2 ; i++) {
curr=curr->next;
}
while(cure->next!=null) {
temp1 = temp->next;
temp2 = curr->next;
temp->next = curr;
curr->next =temp1;
temp = temp1;
curr = temp2;
}``````

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.