Microsoft Interview Question
Q1. The interviewer first discussed about my projects ?
especially what your role in every project , what are you use from technologies to implement ?
team size in every project
Q2. Convert a Binary Tree to Doubly Link List (DLL) in place?
first the order of DLL must be in the same inorder of binary tree left most in BT see pic 1
pic 1
in-order method go to deep left at first from the head 10 then go left treat it as tree head 12 go left a gain then 25 the end leaf no left and right come back take 12 move right take 30 go to parent of 12 has 10 take if and i has leaf right 15 head of sub tree then go to 36 take it and last take 15
secondly using recursive to fill doubly linked list from tree by in-order predecessor that is
find in-order predecessor of root in left sub-tree (in-order predecessor is rightmost node in left sub-tree). then
Make in-order predecessor as previous of root and root as next of in-order predecessor. and so on
this code describe that written in java
secondly using recursive to fill doubly linked list from tree by in-order predecessor that is
find in-order predecessor of root in left sub-tree (in-order predecessor is rightmost node in left sub-tree). then
Make in-order predecessor as previous of root and root as next of in-order predecessor. and so on
this code describe that written in java
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree
{
Node root;
/* This is the core function to convert Tree to list. This function
follows steps 1 and 2 of the above algorithm */
Node bintree2listUtil(Node node)
{
// Base case
if (node == null)
return node;
// Convert the left subtree and link to root
if (node.left != null)
{
// Convert the left subtree
Node left = bintree2listUtil(node.left);
// Find inorder predecessor. After this loop, left
// will point to the inorder predecessor
for (; left.right != null; left = left.right);
// Make root as next of the predecessor
left.right = node;
// Make predecssor as previous of root
node.left = left;
}
// Convert the right subtree and link to root
if (node.right != null)
{
// Convert the right subtree
Node right = bintree2listUtil(node.right);
// Find inorder successor. After this loop, right
// will point to the inorder successor
for (; right.left != null; right = right.left);
// Make root as previous of successor
right.left = node;
// Make successor as next of root
node.right = right;
}
return node;
}
// The main function that first calls bintree2listUtil(), then follows
// step 3 of the above algorithm
Node bintree2list(Node node)
{
// Base case
if (node == null)
return node;
// Convert to DLL using bintree2listUtil()
node = bintree2listUtil(node);
// bintree2listUtil() returns root node of the converted
// DLL. We need pointer to the leftmost node which is
// head of the constructed DLL, so move to the leftmost node
while (node.left != null)
node = node.left;
return node;
}
/* Function to print nodes in a given doubly linked list */
void printList(Node node)
{
while (node != null)
{
System.out.print(node.data + " ");
node = node.right;
}
}
/* Driver program to test above functions*/
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
// Let us create the tree shown in above diagram
tree.root = new Node(10);
tree.root.left = new Node(12);
tree.root.right = new Node(15);
tree.root.left.left = new Node(25);
tree.root.left.right = new Node(30);
tree.root.right.left = new Node(36);
// Convert to DLL
Node head = tree.bintree2list(tree.root);
// Print the converted list
tree.printList(head);
}
}
Q3. One DBMS query select 2nd max salary from table,
SELECT MAX(Salary) FROM Employee
WHERE Salary != (SELECT MAX(Salary) FROM Employee )
or
SELECT MAX(Salary) FROM Employee
WHERE Salary NOT IN (SELECT MAX(Salary) FROM Employee )
Q4. OS questions from deadlock, synchronization, scheduling, diff between process and thread.
Q5. What happens when you type URL in browser and hit enter? Explain in detail.
Q4 and Q5 and others will answered in next part follow to get latest update
written by
