Microsoft Interview Question
Software Engineer / DevelopersPure insertion sort, Like binary search, go to the middle of the selected set everytime and see if the number is greater .. then, once you find the smallest.. traverse from there and insert it...
Deletion is also same !!
well, going to the middle would take traversing n/2 elements because this is a doubly linked list not an array. so the complexity with this algo would be = n/2 + n/4 + n/8.... + n/n ==> O(n) for searching and O(1) for inserting.
Instead, why not just traverse through the array?
the complexity = O(position_Of_New_Element)
-> Obtain a pointer to the begin, middle and end of the double linked list and store it.
-> For every new element to be inserted,
check if it is less than middle element or not {O(1)}
traverse to the left or right based on the comparison {O(n/2)}
-> worst case complexity: O(n/2)
space complexity: O(1)
node* insert(node* ptr,int x)
- Anonymous January 25, 2011{
node* ptr1=ptr,ptr2=NULL;
ptr2=(node*)malloc(sizeof(node));
if(ptr!=NULL)
{
while(ptr!=NULL && ptr->data >= x)
{
ptr1=ptr;
ptr=ptr->next;
}
if(ptr!=NULL)
{
ptr->left->right=ptr2;
ptr2->right=ptr;
ptr->left=ptr2;
}
else
{
ptr1->right=ptr2;
ptr2->left=ptr1;
ptr2->right=NULL;
}
}
else
{
ptr2->data=x;
ptr2->left=NULL;
ptr2->right=NULL;
}
}