Given a tree of child/parent relationships, write an algorithm to find common parent

Question

Muthu · Accepted Answer

Lease common ancestor problem.

public static Node lowestCommonAncestor(Node root, Node a, Node b) {
    if (root == null) {
        return null;
    }
    
    if (root.equals(a) || root.equals(b)) { 
        // if at least one matched, no need to continue
        // this is the LCA for this root
        return root;
    }
 
    Node l = lowestCommonAncestor(root.left, a, b);
    Node r = lowestCommonAncestor(root.right, a, b);
 
    if (l != null && r != null) {
    	return root;  // nodes are each on a seaparate branch
    }
 
    // either one node is on one branch, 
    // or none was found in any of the branches
    return l != null ? l : r;
}

future_candidate · Answer

With no assumptions about the tree and given only parent-child relations (root has null parent) we can step back to root from one node storing all ancestors in a hashtable. then we trace ancestors of another node each time checking whether it exists in the hashtable. if it exists we return it as the lowest common ancestor.

def lowestCommonAncestor(a, b):
    a_ancestors = set()
    p = a 
    while p != None:
          a_ancestors.add(p)
          p = p.parent
    p = b
    while p != None
          if p in  a_ancestors:
                 return p

future_candidate · Answer

The runtime is O(height of tree) Space complexity is also O(height of tree)

future_candidate · Answer

2nd while loop is missing p = p.parent outside the if block

Google

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas