Airbnb | Phone screen | Lowest Common Ancestor of Two Regions

2744

AirBnb questions are usually very lengthy, so in short

Given a list of string array,
In each string array, the first element consists of the rest elements.
e.g.
[Earth, South America, North America, Asia, Pacific, Africa]
[Asia, China, Korea, Japan]
[North America, USA, Canada]
[South America, Brazil, Columbia]
[Africa, Algeria, Lybia]
[China, Beijing, Shanhai]
[Japan, Tokyo, Kyoto]
[Korea, Seoul]

Given two valid elements, find its least common ancestor (LCA)
e.g.
input
[Tokyo, Kyoto]
output
Japan

input
[Beijing, Japan]
output
Asia

input
[Seoul, Africa]
output
Earth

My own solution

function findLowestCommonTerritory(territoryList, inputs) {
    const parents = {};
    territoryList.forEach(t => {
        t.forEach((a, i) => {
            if (i !== 0) {
                parents[a] = t[0];
            }
        });  
    });

    const result = [];
    for (const input of inputs) {
        result.push(lca(parents, input[0], input[1]));       
    }

    return result;
}

function lca(parents, node1, node2) {
    const ancestors = new Set();
    while (node1) {
        ancestors.add(node1);
        node1 = parents[node1];
    }

    while (node2 && !ancestors.has(node2)) {
        node2 = parents[node2];
    }
    return node2;
}

Comments (5)