## Microsoft Interview Question for Software Engineer / Developers

• 0
of 0 votes

Country: India
Interview Type: Written Test

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

Flawless Code...Enjoy!!!
Time O(n) ... Space (1)
Note: For simplicity I have not made these functions generic. After a little tweaking below code can sort list with 0 1 2 3 also.

Here we go:

``````void append(node* &head, node* &tail, node* n)
{
if(!head)
head = n;
else
tail->next = n;
tail = n;
}
void join(node*& a, node*& alast, node* b, node* blast)
{
if(!a)
{
a = b;
alast = blast;
}
else if(b)
{
alast->next = b;
alast = blast;
}
}
int sort123(node* &head)
{
if(!head)
return -1;
node* start[3] = {NULL,NULL,NULL};
node* end[3] = {NULL,NULL,NULL};
for(node* n = head; n; n = n->next)
{
int index = n->data;
if(index < 0 || index > 2)
return -1;
append(start[index],end[index],n);
}
head = start[0];
node* tail = end[0];
join(head,tail,start[1],end[1]);
join(head,tail,start[2],end[2]);
tail->next = NULL;
return 0;
}``````

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

Traverse the linked list. When you encounter a 0 node, add it to the front and update head. When you encounter a 2 node, add it to the end and update tail node. Run a loop for n, else you will end up having extra iterations since tail gets updated.
Is this fine?

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

Everything is supercool if you have considered that when you encounter the two's which you have updated at the end belongs to the sorted list or not or else you will end up in infinite loop never finding tail since for every 2 you add it and update the tail.......0->0->0->1->1->2->2->2->tail......here look whthr your algo terminates or not :-/

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

Instead of adding 2s to the end , insert 2s node after head2. Run the loop till you reach head2.

So finally we get,
(head1)0-0-0-1-1-1-(head2)2-2-2

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

Nice solution.

@Mukesh
Read the answer completely. He said end the loop after N iterations.

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

@zapurza: I think in that case also it will fail for this list

``0->1->2->0->1->2``

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

Maintain 3 different lists. List of zeroes, list of ones and list of twos. Maintain the head and tail of each.

Make a pass through the linked list, if you see a 0 or 1 or 2, insert into the appropriate list. At the end, append the three lists.

C like code below (untested).

``````// Partitions the list and returns a new head.
List * Partition(List * head) {
if (!head || head->next) return;
List *cur = head;
List * heads[3] = {NULL, NULL, NULL};
List * tails[3] = {NULL, NULL, NULL};

while (cur) {
List *tmp = cur->next;
insert(cur, &heads[cur->data], &tails[cur->data]);
cur = tmp;
}
List *merged_head = NULL;
List *merged_tail = NULL;
for (int i = 0; i < 3; i++) {
if (heads[i]) {
if (!merged_tail) {
merged_head = heads[i];
merged_tail = tails[i];
} else {
merged_tail->next = heads[i];
merged_tail = tails[i];
}
}
}
return merged_head;
}
void insert(List *elem, List **head, List ** tail) {
// First element of list.
if (*head == NULL) {
*head = elem;
*tail = elem;
elem->next = NULL;
} else {
// Insert at the head.
elem->next = head;
*head = elem;
}
}``````

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

The first line should be if (!head || !head->next) return head;

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

And instead of hardcoding the value 3, we can make it a parameter to the method.

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

If you want a stable partition, change the insert to insert at the tail, rather than the head.

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

How about this - You traverse through linked list. Keep 3 counts for each 0,1,2.
Then replace original linked list with all 0s at start depending on count of 0s and so on.

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

@addy--U cant change values in it..Else its not a MS Question.Do it by exchanging
ptrs

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

short and elegant!!

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

consider this you have this stream of numbers in the link list
1220022111001010101020201022210011012........now my theory says have a temp pointer and this will require atleast 3 pass that is 3n=~O(n).... zeroTemp pointer is for Zero's oneTemp is for One's and twoTemp is for Twos's and Temp is general for the linkList...................so in first pass keep looking for zero's that is
1-->2-->2-->0-->0-->2-->2-->1-->1-->1-->0-->0...........
^ ^
Temp zTemp

Temp points to 2 and zTemp points to 0..........now you encountered first zero at 4th location have a backup of its location in Temp pointer that is Temp.next and set zTemp as this zero's location . let it be there , now proceeding we find that next is also a Zero so no circus here just increment zTemp to next zero....coming to 6th location we see '2' so here what we do is we want to continue the chain of non Zero's with Temp pointer so we point Temp.next to this '2' . Now zTemp is pointing to 2nd Zero and and Temp is pointing to 6th location that is at '2'........proceeding in this faishon we seprated the zeros and non zeros at the end we have 0-->0-->0-->0->0-->.......1-->2-->2-->2-->2-->1-->1 and so on.........now we one oneTemp and seprate 1's from the list and then we are left with '2'......just merge them.
Assumption : I kept head pointer each for 0's 1's and two's

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

It is possible to do in one pass.

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

Yes that is possible but what I am trying to do here is avoid extra usage of extra O(n) space everything is done inplace.

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

@Mukesh: One pass, O(1) space is possible. See the answer which starts with "Maintain 3 different lists..." and can be generalized to 0,1,2,3, ...,n and not just 0,1,2.

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

@Anonyumous, Maintain 3 Lists takes 0(n) space. What you can do is maintain 3 counting variables for 0,1,2. I don't think in place is possible without extra space and in single pass

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

@Nitin: Look carefully: we are not allocating new nodes. We are only reusing the nodes from the input list, and maintaining them as 3 different lists.

So that algorithm space usage is O(1).

btw, "no extra space" is not the same as saying space usage must be O(1).

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

We aren't really maintaining 3 lists of Nodes (or their pointers). We are actually just maintaining the head & tail for each value, so at most 6 Nodes, which is O(1) because it doesn't depend on the length of the list.

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

1- make a hash table.... which checks for values 0,1,2 and store address of the "node".
2- traverse the linked list and update hash table.....
3- now link all the nodes from hash table to form a linked list..

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

I think this problem can be thought of more easily if we don'd consider the link list elements containing 2, we can go through the link list once for just taking all the 1's are keeping them at the end of the list and then we can go again and keep all the 2's. Asymptotically this will take O(n) time only. Okay so we take a pointer first_encounter, we will set first_encounter to the element just before we encounter the first 1. Now we keep traversing the list. For ex
0->0->0->0->1->2->0>1->1
So first_encounter will be set at 4th position (as there is a 1 at 5th), now whenever we get anything but 1 in the next element we will splice it out and place it between first_encounter and its next element (which contains the first 1). for ex after reaching 2 list would look like
0->0->0->0->2->1->0->1->1

In the end you will get a list will all 1's in the end. Go through the list one more for 2's. With a little modification you can do this in one pass by using a second_encounter for 2's. You would just have put second_encounter at the end of all 1's (probably need a 3rd pointer for that).

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

1. Have 3 startptr and endptr representing start and end of the lists.
e.g , start0 will point to start of 0's List
end2 will point to end of 2's List and so on.
2. Traverse the given Linked list and append the nodes to the respective endptr.
3. Make head = startptr of 0's List. Append 1's List to endptr0 and then append 2's List to endptr1.

void
append(Nodeptr * node, Nodeptr * startptr, Nodeptr * endptr)
{

(*node)->next = NULL;
if (*startptr == NULL )
{
*startptr = *node;
*endptr = *node;
return;
}

(*endptr)->next = *node;
*endptr = *node;

}

void
sort012(Nodeptr * headref)
{
Nodeptr ptr = *headref;

Nodeptr start0 = NULL, end0 = NULL, start1 = NULL, start2 = NULL, end1 = NULL,
end2 = NULL;

while (ptr)
{
Nodeptr save_next = ptr->next;

if (ptr->val == 0)
append(&ptr, &start0, &end0);
else if (ptr->val == 1)
append(&ptr, &start1, &end1);
else
append(&ptr, &start2, &end2);

ptr = save_next;
}

*headref = start0;
end0->next = start1;
end1->next = start2;

}

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

1. Have 3 startptr and endptr representing start and end of the lists.
e.g , start0 will point to start of 0's List
end2 will point to end of 2's List and so on.
2. Traverse the given Linked list and append the nodes to the respective endptr.
3. Make head = startptr of 0's List. Append 1's List to endptr0 and then append 2's List to endptr1.

void
append(Nodeptr * node, Nodeptr * startptr, Nodeptr * endptr)
{

(*node)->next = NULL;
if (*startptr == NULL )
{
*startptr = *node;
*endptr = *node;
return;
}

(*endptr)->next = *node;
*endptr = *node;

}

void
sort012(Nodeptr * headref)
{
Nodeptr ptr = *headref;

Nodeptr start0 = NULL, end0 = NULL, start1 = NULL, start2 = NULL, end1 = NULL,
end2 = NULL;

while (ptr)
{
Nodeptr save_next = ptr->next;

if (ptr->val == 0)
append(&ptr, &start0, &end0);
else if (ptr->val == 1)
append(&ptr, &start1, &end1);
else
append(&ptr, &start2, &end2);

ptr = save_next;
}

*headref = start0;
end0->next = start1;
end1->next = start2;

}

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

Its simple !!!
Algo :- Keep two pointers one pointing to head and other at tail of Linked list. Now traverse the list from head if you encounter any node with value 0 then remove from that position and add at the head and updated the head ptr to the newly added node.
If you encounter 2 then remove that node and add that node at the tail of linked list and update the tail ptr to the new node added.

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

Pretty sure this will create an infinite loop where once you've reached the 2's, you'll continually add the two to the end and never stop. You'd need to add a pointer to the original tail so you know when to stop processing.

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

how come...same approaches at same time.. :)

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

In one scan count number of 0's 1's and 2's , here we require another 3 variable to store the count :P . Now after counting the number of 0s 1s and 2s ......start from head and keep modifying the link list and decrementing the counter and when 0's are written start writing 1's and then 2's untill the counter turns zero!!!....

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

@ mukesh... i have the same approach... via hash table....
bt time complexity will b slightly more than O(n).. i think
O(n)- for traverse
some constant for linking them
O(n)+c

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

ROFL really ?? i cant stop laughing !!

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

I think every solution here will be O(n), so that's not the differentiating factor here. For this problem, I think solutions will be evaluated based on how much memory it uses, how many passes it requires, whether the list can be modified in-place, and just to be picky, whether the original order can be preserved.

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

traverse the list whenever we find the 1 delete it and add it infront of the head ,whenever find 3 delete it and add it to last...u have the ordered list

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

I cocncur... though its 0,1,2 not 1,2,3 :)

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

I tried using an example. Tell me if I got it. You have a linked list that looks like this: [0] --> [1] --> [2] --> [1] --> [2] --> [0] for example. You start at [0] and compare to the next node [1]. since 0 <= 1, you move on. You compare [1] to the next node [2]. 1 <= 2, so you move on. You compare [2] to the next node [1]. 2 <= 1 is not true, so you make [2] point to [1]'s successor and make [1] point to [2]. Now you have [0] --> [1] --> [1] --> [2] --> [2] --> [0]. Continue by comparing [2] to the next node [2]. since 2 <= 2, you move on. Compare [2] to the next node [0]. since 2 <= 0 is not true and the next node is 0, make [0] point to the head node, and make [2] point to [0]'s successor (which is null). You finally have [0] --> [0] --> [1] --> [1] --> [2] --> [2]. And you are done. Let me know if you find some error with this process.

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

So this only works when there are no doubles of an element next to each other. For example, 0122022111 would end up as 0012222111 at some point with the current pointer pointing at the last 2. You would need to make 1 go before the 2's, but if you just swap then you would get 0012221211. So you might have to have an extra pointer that keeps track of the last 1 while ordering, so 0012222111 would have the extra pointer point at the 1 before the 2. So whenever you get a 1, then just place it after the last 1 in the order.

If it was a doubly-linked list, then you could always just have 0's point to the head and 2's be the successor of the last element. and pass by 1's. If it is a singly linked list, then you would need a different method.

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

``````// if 1 or less
if ((head == null) || (head.Next == null))
return;

//Find last
var last = head;
while (last.Next != null) last = last.Next;
var lastValue = last;

Node previous = head;
current = head.Next;
while (current != lastValue)
{
if (current.value == 0)
{
//append to first
previous.Next = current.Next;
current.Next = head;
head = current;
current = previous.Next;
}
else if (current.value == 2)
{
//append to last
previous.Next = current.Next;
last.Next = current;
current.Next = null;
last = current;
current = previous.Next;
}
else
{
previous = current;
current = current.Next;
}``````

}

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

Didnt read the entire lot....but here is what i was thinking..
lets take the first eg: 1220022111001010101020201022210011012
I'd traverse the list...
divide the list into 3 lists...
List 1 : contains all 0
List 2: all 1s
List 3: all 2s

so.... If 1 or 2 is encountered... i'd just remove the node from the original list and add it to the designed list(somthing like a bucket).
for each removal of node from the original List ... i'd keep track of the first and last nodes of the 1's and 2's List.
also do somthing like... node->next = removednode->next

At the end...i'd expect 2 seperate lists of 0's,1's and 2's

I'd just club them together after this..
as I am traversing the original list only once... I guess my complexity should remain O(n).

is the above feasible ?

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

You just need to maintain 3 pointers witch pointing to the tail of 'sub-list' of 1's, 2's and 3's respectively.
We go though the list by one pass. For every node we insert it to the tail of the right 'sub-list' and then update the tail pointer of 'sub-list'.
At first those 3 pointers, p0, p1, p2, are all null.
We assume the list is 1-->2-->2-->0-->0-->2

1st node (1) :
p1==null so insert 1 to the head of the list
p2==p1(==null) so update p2
Update p1

``````1-->2-->2-->0-->0-->2
|
p1
p2``````

2nd node (2):
Insert 2 to the next of p2
update p2

``````1-->2-->2-->0-->0-->2
|      |
p1  p2``````

3rd node (2):
Insert 2 to the next of p2
update p2

``````1-->2-->2-->0-->0-->2
|             |
p1         p2``````

4th node (0):
p0==null so insert 0 to the head of the list
update p0

``````0-->1-->2-->2-->0-->2
|      |             |
p0  p1         p2``````

5th node (0):
Insert 0 to the next of p0
update p0

``````0-->0-->1-->2-->2-->2
|      |             |
p0  p1         p2``````

6th node (2):
Insert 2 to the next of p2
update p2

``````0-->0-->1-->2-->2-->2
|      |                    |
p0  p1                p2``````

The time complexity if O(n) and space complexity is O(1).

Be aware that when you update p0, you should check if other two pointers need to be updated. You should check backward. If p2==p1 then update p2 and if p1==p0 then update p1. Now you can update p0.

Similarly when you update p1 you should check if p2 need to be updated.

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

the charts should be

``````1-->2-->2-->0-->0-->2
|
p1
p2``````

``````1-->2-->2-->0-->0-->2
|   |
p1  p2``````

``````1-->2-->2-->0-->0-->2
|       |
p1      p2``````

``````0-->1-->2-->2-->0-->2
|   |       |
p0  p1      p2``````

``````0-->0-->1-->2-->2-->2
|    |       |
p0  p1      p2``````

``````0-->0-->1-->2-->2-->2
|    |           |
p0  p1          p2``````

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

I don't think you can do it with just 3 pointers to the tails. Consider {0, 0, 0, 2, 2, 2, 1}. After traversing through the 0s & 2s, p0 & p2 will point to the last 0 and 2, respectively. So how can you point 1 to the first 2? That's why you also need pointers to the heads.

Nice graphics & explanations though :)

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

``````#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
void insert(struct node *pointer,int data)
{
if(pointer==NULL)
{
pointer=malloc(sizeof(struct node));
pointer->data=data;
pointer->next=NULL;
pointer=pointer->next;
}
else
{
while(pointer->next!=NULL)
{
pointer=pointer->next;
}
pointer->next=malloc(sizeof(struct node));
pointer=pointer->next;
pointer->data=data;
pointer->next=NULL;
}
}
void print(struct node*pointer)
{
if (pointer==NULL)
{
return;
}
printf("%d  ",pointer->data);
print(pointer->next);
}
void merge(struct node*pointer1,struct node*pointer2)
{
while(pointer1->next!=NULL)
{
pointer1=pointer1->next;
}
pointer1->next=pointer2;
}
void main()
{
struct node *start[3],*temp[3],*input,*i_temp;
int i;
input=malloc(sizeof(struct node));
i_temp=input;
i_temp->next=NULL;
for (i = 0; i < 3; i += 1)
{
start[i]=malloc(sizeof(struct node));
temp[i]=start[i];
temp[i]->next=NULL;
}
for (i = 0; i < 10; i += 1)
{
insert(input,i%3);
}
input=input->next;
while(input->next!=NULL)
{
insert(start[input->data%3],input->data);
input=input->next;
}
merge(start[0],start[1]);
merge(start[1],start[2]);
print(start[0]);
}``````

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

In a single traversal find out number of zeros , ones and twos, by having 3 variables.
Then one more time do the traversal and put that many number of zeros , ones and twos.
Overall complexity would be O(2n) which is 0(n).

2 2 1 1 1 0 1 0 2 2 2 0 0 0 1 1
countZ=5
count1=6
count2=5
0(n)
temp=head;
while(temp!=null)
{
if(countZ!=0){
temp.data=0;
countZ--;
}
else if(count1!=0){
temp.data=1;
count1--;
}
else if(count2!=0){
temp.data=2;
count2--;
}
temp=temp.next;
}
0(n)

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

create 3 ints a,b,c a for 0 b for 1 and c for 2...
traverse through the LL increment a/b/c with the values found ... O(n)
then if 3 zeros make the first 3 elements to zeros .... and so on O(n) ..

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

``````node sortList_012(node head){
struct node p0;
struct node* h0 = &p0;
p0.next = NULL;
struct node p1;
struct node* h1 = &p1;
p1.next = NULL;
struct node p2;
struct node* h2 = &p2;
p2.next = NULL;

struct node *cur = head;
if(head==NULL){
return NULL;
}
printf("\nrun");
while(cur!=NULL){
if(cur->data==0){
h0->next=cur;
h0=h0->next;
}
if(cur->data==1){
h1->next=cur;
h1=h1->next;
}
if(cur->data==2){
h2->next=cur;
h2=h2->next;
}
cur=cur->next;
}
if(h0!=NULL){
h0->next=NULL;
}else {
h0=p1.next;
}
if(h1!=NULL){
h1->next=NULL;
h0->next=p1.next;
}//else {
// h1=p2.next;
//}
if(h2!=NULL){
h2->next=NULL;
h1->next=p2.next;
}//else {
//}
if((p0.next)!=NULL && (p1.next!=NULL) && (p2.next!=NULL)){
h0->next=p1.next;
h1->next=p2.next;
}
if(p0.next){
return (p0.next);
}
else if(p1.next){
return p1.next;
}
else {
return p2.next;
}
}``````

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

You can do it in O(n) without using extra space. But, rather just some extra variables.
The code works also when the list contains only zeros, ones or twos and may be just two of them and not he third one.

``````sort_list(node **head)
{
node *zero_head = NULL, *zero_tail = NULL;
node *one_head = NULL, *one_tail = NULL;
node *two_head = NULL, *two_tail = NULL;
node *tmp = NULL;
int changed = 0;

if(!head || !*head)
return;

for(tmp = *head; tmp; tmp = tmp->next)
{
if(tmp->val == 1)
{
if(!one_head)
{
one_head = one_tail = tmp;
}
else
{
one_tail->next = tmp;
one_tail = one_tail->next;
}
}
else if(tmp->val == 0)
{

if(!zero_head)
{
zero_head = zero_tail = tmp;
}
else
{
zero_tail->next = tmp;
zero_tail = zero_tail->next;
}
}
else if(tmp->val == 2)
{
if(!two_head)
{
two_head = two_tail = tmp;
}
else
{
two_tail->next = tmp;
two_tail = two_tail->next;
}
}
else
{
// No other than 0, 1 or 2
printf("List contains numbers other than 0/1/2. Error !!");
return -1;
}

}

if(zero_tail)
{
zero_tail->next = one_head;
*head = zero_head;
changed = 1;

}
if(one_tail)
{
one_tail->next = two_head;
if(!changed)
{
*head = one_head;
changed = 1;
}
}
if(two_tail && !changed)
{
*head = two_head;
changed = 1;
}
}``````

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

yes similarly
1.keep three count variable count0,count1 and count2
2.update the data field of the list

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

``````// Program to sort a linked list 0s, 1s or 2s
#include<stdio.h>
#include<stdlib.h>

/* Link list node */
struct node
{
int data;
struct node* next;
};

// Function to sort a linked list of 0s, 1s and 2s
void sortList(struct node **head)
{
//if linklist having 0 or just one node
if((*head)==NULL||(*head)->next==NULL)
return ;

struct node *curr=*head;
struct node *pre=NULL;
struct node *tail=*head;
int count=1;

//counting the no of nodes and tail of the linklist
while(tail->next!=NULL){
tail=tail->next;
count++;
}

for(int i=1;i<=count;i++)
{

//if the node data matched with zero
if(curr->data==0)
{
//if this is the not the first element of the node
if(pre)
{
struct node *temp=curr->next;
curr->next=*head;
*head=curr;
pre->next=temp;
curr=temp;
}
//if this zero is the starting node then just skip
else
{
pre=curr;
curr=curr->next;
}

}

//no need to do anything if node is 1
else if(curr->data==1)
{
pre=curr;
curr=curr->next;
}

///now checking for node when data is 2
else if(curr->data==2)
{
// if node is not the first element
if(pre)
{
//struct node *temp=curr;
pre->next=curr->next;
tail->next=curr;
tail=tail->next;
tail->next=NULL;
curr=pre->next;
}
//if node is the first element
else
{
struct node *temp=*head;
*head=(*head)->next;
tail->next=temp;
tail=tail->next;
tail->next=NULL;
curr=*head;
}
}

}

}

/* Function to push a node */
void push (struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =(struct node*) malloc(sizeof(struct node));

/* put in the data  */
new_node->data  = new_data;

/* link the old list off the new node */
new_node->next =(*head_ref);

/* move the head to point to the new node */
(*head_ref)    = new_node;
}

/* Function to print linked list */
void printList(struct node *node)
{
while (node != NULL)
{
printf("%d  ", node->data);
node = node->next;
}
printf("\n");
}

/* Drier program to test above function*/
int main(void)
{
struct node *head = NULL;
push(&head, 0);
push(&head, 2);
push(&head, 1);
/* push(&head, 2);
push(&head, 1);
push(&head, 1);
push(&head, 2);
push(&head, 1);
push(&head, 2);
push(&head, 0);
//push(&head, 1);
//push(&head, 0);
push(&head, 2);
//push(&head, 1);
//push(&head, 1);
//push(&head, 1);
push(&head, 2 );
push(&head, 1);
*/

printf("Linked List Before Sorting\n");
printList(head);

sortList(&head);

printf("Linked List After Sorting\n");
printList(head);

return 0;
}``````

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

``````Node * sort012_new(Node * head) {

if (!head || !head->next)
return head;

Node * head_of_2s = NULL;

Node * prev = NULL;
Node * curr = head;

while (curr) {
if (curr->data == 0) {
if (prev == NULL || prev->data == 0) {
prev = curr;
curr = curr->next;
}
else {
prev->next = curr->next;
curr->next = head;
head = curr;
curr = prev->next;
}
}
else if (curr->data == 1) {
prev = curr;
curr = curr->next;
}
else {
if (prev == NULL) {
head = curr->next;
curr->next = head_of_2s;
head_of_2s = curr;
curr = head;
}
else {
prev->next = curr->next;
curr->next = head_of_2s;
head_of_2s = curr;
curr = prev->next;
}
}
}

prev->next = head_of_2s;

return head;
}``````

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

``````Node * sort012_new(Node * head) {

if (!head || !head->next)
return head;

Node * head_of_2s = NULL;

Node * prev = NULL;
Node * curr = head;

while (curr) {
if (curr->data == 0) {
if (prev == NULL || prev->data == 0) {
prev = curr;
curr = curr->next;
}
else {
prev->next = curr->next;
curr->next = head;
head = curr;
curr = prev->next;
}
}
else if (curr->data == 1) {
prev = curr;
curr = curr->next;
}
else {
if (prev == NULL) {
head = curr->next;
curr->next = head_of_2s;
head_of_2s = curr;
curr = head;
}
else {
prev->next = curr->next;
curr->next = head_of_2s;
head_of_2s = curr;
curr = prev->next;
}
}
}

prev->next = head_of_2s;

return head;
}``````

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

I don't know my approach is efficient..but it is an approach..so tell me
take 3 vars count_0, count_1, count_2
traverse the list once to get each total count numbers
traverse the list and change the values simply...
i know it's a bit funny approach...nothing sorting or swapping..so tell me a better one
But it's O(n)

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

@access deneid--U cant change values in it..Else its not a MS Question.Do it by exchanging
ptrs

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

I does not matter whether its Google or MS or any other company, the point is solve the problem with least complexity of time and space. If something can be done better without pointer manipulation then adopting that will be the right to do for various reasons like testing, maintenance. This also a point they see in interview and especially in companies like MS.

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

@Praveen Well the company doesn't matter, but this isn't just about pointer manipulation, what if the 0's 1's and 2's are just some key and list has more data and need to be sorted in order. The above mentioned technique is unstable. Most sorting's require that the algorithm should be stable(i.e. it should maintain order of equal elements).

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