CareerCup

You must have done well to get to the Director. I assume he was the last person in the loop.

yeah well i didnt get the job :(, i was interviewing for New College grad position in Tools and Server Division with Windows Workflow Foundation team of .Net Framework.

bool Search (Node *root, int key)
{
   while (root != NULL)
   { 
       if (root-> no == key) {return true;}
       else if (root->no > key) {root = root->right;}
       else {root = root->left; }   
   }
   return false;
}

Node * LowestCommonAncestor(Node *root, int a, int b)
{
      if (root == NULL) {return ; }
            
      if (a < root-> no && b > root->no )
      {
         if ( Search(root->left, a) && Search(root->right, b) )
         {
              return root;
         }
         else
         {
              return NULL;
         }
      }
      else if ( a < root-> no && b < root-> no)
      {
         return LowestCommonAncestor(root->left, a, b);
      }
      else if ( a > root-> no && b > root-> no)
      {
         return LowestCommonAncestor(root->right, a, b);
      }
      else
      {
         return NULL;
      }              
}

Above code will only work for BST and will not work for every "Binary Tree"

I took a while to reach to ans as this was binary tree , the solution i had given there was
1) get preoder and inorder
2) take first element in prorder and search it into inorder all the element to left of it is left subtree and on right are right subtree

3)find the index of node1 and node2 in inorder , if one appears on the left of root and other on the right then return root as ans

4) if both appear on left side , discard all the elements right to root , same with if they appear on the right of root

5) increament index in preorder

6) continue this recursively

node * LCA(node *n1,node *n2,node * root) {
if (!root || !n1 || !n2) return null;

if ((n1->val <= root->val) && (n2->val > root->val)) return root;
else if (n1->val > root->val) return LCA(n1,n2,root->right);
else if (n2->val < root->val) return LCA(n1,n2,root->left);
}
Above code is for BST and with assumption that :
n1->val < n2->val
n1 and n2 are present in the BST

typedef  struct node{
       int val;
       struct node *left;
       struct node *right;
} tNode;

tNode * ClosestCommonAnscestor( tNode *root, tNode *key1, tNode *key2)
{
     if( root == NULL )
     {
             return NULL;
     }
     else if( root == key1 || root == key2 )
     {
           return root;
     }
     else
     {
         tNode *l= NULL, *r = NULL ;
         
         l = ClosestCommonAnscestor( root->left, Key1, key2 );
         r = ClosestCommonAnscestor( root->right, Key1, key2 );
         if( (l != NULL)  && (r != NULL) )
         {
               return root;
         }
         else
         {
               return l ? l : r;
         }
     } 
}

If you find any mistakes in my code please let me know.

hey sachin, i have an interview with Server and Tools as well. could you please tell me some of the other questions you were asked? I would really appreciate your assistance.

Best,
DK