## Microsoft Interview Question for Software Engineer Interns

• 1
of 1 vote

Country: United States
Interview Type: In-Person

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

``````//Sort a linklist using merge sort
//We will change nodes pointer to make it sorted
//Rewrite merge function such a way that we not need to use merge_util
// as helper

struct Node
{
int data;
Node *next;
Node(int d, Node* temp) : data(d),next(temp)
{

}
};

{
{
}
else
{
}
}

{
{
}
}

//Other version of middle we should not use which return
//n/2+1 th node as middle
//Subproblem2=>[mid+1,end)
//else there will be a infinite loop when item are 2
Node* middle(Node *head)// mid = n/2 th node
{
{
}

while(fast && fast->next)
{
fast = fast->next->next;
if(fast == NULL) break;
slow = slow->next;
}
return slow;
}

{

Node *result = NULL;

{
}
else
{
}
return result;
}

{
}
{
// min size of subproblem is 2 size so if 2 or more element then call it
{

Node *second = mid->next;
mid->next = NULL;

merge_sort(&second);
}
}

int main()
{

return 0;
}``````

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

What will be the complexity for this solution?

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

You meant that final list should be sorted?

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

We can use merge sort here if we want do using link modify, if the problem is we can modify data itself then this question is easy and we can use bubble sort of selection sort...i will post solution soon both ways......

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

We can use simple Bubble sort.

``````public void sort(Node head) {
cur_next = cur.next;
count = 0;

while(cur != null) {
cur= cur.next;
count++;
}

for(int i = 0;i < count ;i++){
cur_next = cur.next;

for(int j = 0;j < i;j++) {
if(cur.value < cur_next.value){
swap_values(cur,cur_value);
}
}
}
}``````

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

I guess the question is just about sorting a linked list based on the values present in the node. It can be done by bubble sort as mentioned by glebstepanov1992

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

//bubble sort approach

``````void bubble_sort(Node* head)
{
{
return;
}

int count = 0;

while(temp != NULL)
{
count++;
temp = temp->next;
}

Node *p = NULL;
Node *q = NULL;
bool flag = false;

for(int i = count-1; i > 0; --i)
{
flag = false;

for(int j = 0; j < i; j++)
{
if(p->data > q->data)
{
flag = true;
swap(p->data,q->data);
}
p = p->next;
q = q->next;
}

if(flag == false) break;

}
}``````

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

Already all the nodes in the list are pointing to the other. So finding the head of the node will solve the problem. I assume it will take n^2 time complexity.

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

To all people saying bubble sort: you would have failed a Microsoft interview lol

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

``````Item* mergesort(Item* top) {
if (!top || !top->next)

Item* middle = top;
for (Item* p = top; p->next && p->next->next; p = p->next->next)
middle = middle->next;

Item* left_last = middle;
middle = middle->next;
left_last->next=NULL;

Item* left = mergesort(top);
Item* right = mergesort(middle);

Item** curr = &top;
while (left || right) {
if (!right ||
(left && left->data <= right->data)) {
*curr = left;
left = left->next;
} else {
*curr = right;
right = right->next;
}
curr = &(*curr)->next;
}
}``````

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

This is a topological sort problem. It can be solved in O(n) time by loading the array into a HashSet and using DFS.

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

Just use two stacks. On stack1 push the first element. Go to the next element and then push to the stack. Make sure the n-element is less than (n-1)element. Use the other stack2 as buffer.

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.