Facebook Interview Question: LCA problem with no parent po... | Glassdoor

Interview Question

Software Engineering Intern Interview

LCA problem with no parent pointers. Given the root of a

  tree and pointers to two nodes contained in that tree, return the lowest common ancestor of the two nodes. IE, the common ancestor furthest from the root.
Answer

Interview Answer

4 Answers

0

Was the data structure a binary tree or a binary search tree?

Anonymous on Apr 26, 2014
0

The complexity in both cases remaining O(n) though for BST the search for the LCA becomes quite easy.

Srikant Aggarwal on Oct 24, 2014
0

bool printCommonAncestor(struct node* node,int x,int y)
{
     if (node == NULL)
        return false;

     // first recur on left subtree
     bool left = printCommonAncestor(node->left,x,y);
     bool right = printCommonAncestor(node->right,x,y);

     if(left && right)
     printf("%d ", node->data);

     if(left || right)
        {
        if(node->data == x || node->data==y)
        {
     printf("%d ", node->data);
        }
     return true;
        }

     if(node->data == x || node->data==y)
     return true;

     return false;

     // now deal with the node

}

Do a Post order traversal. If its on left and right of the tree then return that node

Anonymous on Mar 3, 2016
0

Array of 256 chars for each string. Assign to 0. Then as a character comes increment the count.
Compute a hash key using these 256 values and store the hash key->String mapping.
Do so for each string, if the mapping already exists, add this string to the list of strings for this mapping.

Anonymous on Mar 3, 2016

Add Answers or Comments

To comment on this, Sign In or Sign Up.