Find lowest common ancestor (LCA).

Question

Matteo Gobbi · Accepted Answer

In pseudocode:

input x,y (they are the 2 nodes)
-------

node A;
node B;

/* Put the nodes taller than the other, in var B e the other one in var A */
if(h(A) h(A);i--) {
	B=p(B);
}

/* take the parent while the 2 nodes are the same */
do {
	A=p(A);
	B=p(B);
} while(A!=B);

return A; (or B)

Matteo Gobbi · Answer

Another solution (better) without the parent pointer:

public node LCA(node T, node x, node y) {
    if (T == NULL) return NULL;
    if (T == x || T == y) return T;

    node rightLCA = LCA(T.right, x, y);
    node leftLCA = LCA(T.left, x, y);

    if(rightLCA != NULL && leftLCA != NULL) 
        return T;
    else return (rightLCA != NULL) ? rightLCA : leftLCA;
}

Genc · Answer

void main(){

    int lca = getLCA(n1, n2);

    // print lca
}

int getLCA(int n1, int n2){

    if(n1 == n2) {return n1;}
    
    // TODO: can optimize these
    int min = Math.Min(n1, n2);
    int max = Math.Max(n1, n2);
    
    // get the minimum int which is larger than the max
    // so if min = 4 and max = 11, we need 12
    int start = max % min;
    start = max + (min - start);
    
    
    // start from the min. ancestor which is larger than the max.
    // in our case, this is 12
    for(int i=start;;i+=min){
        if(i % max == 0){
            return i;
        }
    }
}

Meta

Domanda di colloquio di Meta

Risposte di colloquio

Aziende seguite

Ricerche di lavoro