## Microsoft Interview Question Software Engineer / Developers

• 0

Onsite interview: Given sorted doubly linked list, write code to insert and delete elements from the list..

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

node* insert(node* ptr,int x)
{
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;
}
}

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

Pure 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 !!

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

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)

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

``````-> 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)``````

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

node * RecInsertDLL(p, prev, num)
{
if(p == null || p->value > num)
{
x = new node;
x->prev = prev;
x->next = p;
x->value = num;
return x;
}

x->next = RIDLL(p->next, p);
return p;
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### 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.