## Microsoft Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

``````// merge sort: returns a pointer to the head of a sorted list
return 0;
list *p = head, *pp = p, *prev = 0
if(p->next == 0)
// find a split in the middle using two ptrs
while(pp != 0 && pp->next != 0) {
prev = p, p = p->next;
pp = pp->next->next;
}
prev->next = 0; // cut the list in the middle
list *h1 = merge_sort(p),
*h2 = merge_sort(head);   // sort the two parts

head = h1, prev = 0;
// merge the list 'h2' into 'h1' inplace
while(h2 != 0) {
if(h1 != 0 && h2->val >= h1->val) {
prev = h1;      // just iterater through 'h1' list
h1 = h1->next;
} else { // insert 'h2' before 'h1'
list *t = h2->next; // save the 'next' pointer
if(prev == 0) { // insert a new head
} else {
prev->next = h2;
h2->next = h1;
}
prev = h2; h2 = t;
}
}
}``````

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

Hello How do u decide that the prev pointer has reached middle of linklist.

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

He said using merge sort, why u implement merge_sort by yourself?

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

Monty, as pp is moving through the list at twice the speed of p, when the function breaks out of the first while loop due to pp or pp->next being null p will point to the middle of the list.

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

``````public void mergeSort() {
}

firstHalf.setNext(null);
}

.getData()) {
lastPos = lastPos.getNext();
} else {
lastPos = lastPos.getNext();

}
}

//If any remaining elements in any of the two link lists ...

lastPos = lastPos.getNext();

}

lastPos = lastPos.getNext();

}
}

return null;

int count = 0;
while (fastP.getNext() != null) {
fastP = fastP.getNext();
count++;
if (count % 2 == 0)
slowP = slowP.getNext();
}
return slowP;
}``````

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

I use a wrapper method to call split and to print .. the head node would be sortedHead ..

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.