Write an algorithm to find the most recent common ancestor of two nodes in a binary search tree.

Question

Sigiloso · Accepted Answer

while (true) {
    p1 = node1.parent
    p2 = node2.parent

    if (p1 == p2)
         return true
    else if (null == p1 || null == p2)
        return false
}

Sigiloso · Answer

//Handles if nodes are on different levels of the tree.

while (true) {
    p1q.enqueue((p1 = node1.parent))
    p2q.enqueue((p2 = node2.parent))

   if (null == p1 && null == p2)
        return break;
}

foreach (p1 = p1q.dequeue()) {
    LCA = traverseQ_AndFind(p2q, p1)
    if (null != LCA)
        return(LCA)
}

return(null);

Clearwater Analytics (CWAN)

Pergunta de entrevista da empresa Clearwater Analytics (CWAN)

Respostas da entrevista

Empresas seguidas

Buscas de vagas