Microsoft Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
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?
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 :-/
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
Nice solution.
@Mukesh
Read the answer completely. He said end the loop after N iterations.
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;
}
}
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.
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
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.
@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.
@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
@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).
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).
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;
}
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;
}
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.
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!!!....
@ 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
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.
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.
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.
// 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;
}
}
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 ?
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.
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
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 :)
#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]);
}
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)
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;
}
}
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;
}
}
// 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;
}
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;
}
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;
}
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)
@access deneid--U cant change values in it..Else its not a MS Question.Do it by exchanging
ptrs
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.
@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).
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:
- Avinash September 13, 2012void 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; }