During the second interview, I was asked to implement LCA in a binary tree (not BST) on collabedit.com. I was close, but not close enough...

Question

Matteo Gobbi · Accepted Answer

class Node {
 int value;
 int height
 Node next;
 Node right;
 Node parent;
}

public int height(Node root) {
    int retValue = 0;
    while((root=parent(root)) != NULL) {
        retValue+
    }
    return retValue;
}

public Node LCA(Node A, Node B) {
    Node temp;
    
    A.height = height(A);
    B.height = height(B);
    if(A.height B.height; i--, A=parent(A));
    
    do {
        A = parent(A);
        B = parent(B);
    } while (A != B);
    
    return A;
}

Genc · Answer

// NOT the best possible solution but an alternative:
// This code gets parents of node1 and puts in an array.
// Then gets parents of node2 and puts in another array.
// Then goes through the list to see if it contains the first node.
// NOTE: Not tried in editor, may not compile. Please use as pseudo code.

public static void main(String[] args){

    // assumption: Nodes are initialized and known already
    Node node1;
    Node node2;
    
    Node lca = getLCA(node1, node2);
    
    // TODO: print lcs
    System.out.println("LCA is: " + lca.toString();
}

static Node getLCA(Node node1, Node node2){

    List list1 = new ArrayList();
    getParents(list1, node1);
    
    List list2 = new ArrayList();
    getParents(list2, node2);
    
    for(Node n : list2){
        if(list1.contains(n){
            return n;
        }
    }
}

static void getParents(List list, Node node){

    if(list == null){
        return;
    }

    if(node == null){
        return;
    }
    
    list.add(node);    
    getParents(list, node.parent);
}


public class Node{
    String value;
    Node parent;
    
    @Override 
    public String toString() {
        return value;
    }
}

Sigiloso · Answer

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas