Interview Questions

249.Given two sorted positive integer arrays A(n) and B(n)Given a pointer to the node, the node has one data part and two address pointers ......

Microsoft Interview Questions and Answers


(Continued from previous question...)

249.Given two sorted positive integer arrays A(n) and B(n)Given a pointer to the node, the node has one data part and two address pointers ......

Question:
Given a pointer to the node, the node has one data part and two address pointers of its own type,
If the node represent a doubly linked list convert it to B-Tree and vice versa. Write test cases to check the system


maybe an answer:


convert DLL to binary tree
//findmid(L,R)--->returns pointer to middle of linked list
DLL2BST(node *L,node *R){
if(L==R)
rerun L;
else{
x=findmid(L,R);
if(x->left){
x->left->right=null;
x->left=DLL2BST(L,x->left)
}
if(x->right){
x->right->left=null;
x->right=DLL2BST(x->right,R);
}
}
return x;
}



maybe an answer2:


struct btnode
{
struct btnode *left;
struct btnode *right;
int data;

btnode(int inData = 0):left(0),right(0),data(inData) {}
};

static btnode* appendList(btnode *list1, btnode *list2)
{
if (list1 == 0)
return list2;

if (list2 == 0)
return list1;

btnode *temp1 = list1->left;
btnode *temp2 = list2->left;

list1->left->right = list2;
list1->left = list2->left;
list2->left = temp1;
temp2->right = list1;

return list1;
}

/* call this function to convert BST to a DLL */
/* pass root pointer as input argument */
btnode* makeDoublyLinkedList(btnode *root)
{
if (root == 0)
return 0;

btnode *frontList = makeDoublyLinkedList(root->left);
btnode *backList = makeDoublyLinkedList(root->right);

root->left = root;
root->right = root;

frontList = appendList(frontList, root);
frontList = appendList(frontList, backList);

return frontList;
}

(Continued on next question...)

Other Interview Questions