Skip to content

Instantly share code, notes, and snippets.

@victorouse

victorouse/dom.html

Created March 4, 2018 04:57
Show Gist options
  • Star 26 You must be signed in to star a gist
  • Fork 4 You must be signed in to fork a gist
  • Save victorouse/56e05553db54cbb73fff62c36a2b4545 to your computer and use it in GitHub Desktop.
Save victorouse/56e05553db54cbb73fff62c36a2b4545 to your computer and use it in GitHub Desktop.
Download ZIP
Facebook Interview: Given two identical DOM tree structures, A and B, and a node from A, find the corresponding node in B
Raw
dom.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width">
<title>Facebook DOM Traversal</title>
</head>
<body>
<div id="rootA">
<div>
<div></div>
</div>
<div></div>
<div>
<div>
<div id="nodeA"></div>
<div></div>
</div>
</div>
</div>
<div id="rootB">
<div>
<div></div>
</div>
<div></div>
<div>
<div>
<div id="nodeB"></div>
<div></div>
</div>
</div>
</div>
</body>
</html>
Raw
solution.js
const rootA = document.getElementById('rootA');
const rootB = document.getElementById('rootB');
const nodeA = document.getElementById('nodeA');
const nodeB = document.getElementById('nodeB');
function getPath(root, node) {
const path = [];
while (node !== root) {
const parent = node.parentElement;
const children = Array.from(parent.children);
const nodeIndex = children.indexOf(node);
path.push(nodeIndex);
node = parent;
}
return path;
}
function getNodeFromPath(node, path) {
const toWalk = [...path];
while (toWalk.length > 0) {
node = node.children[toWalk.pop()];
}
return node;
}
function getSymmetricNode(rootA, rootB, nodeA) {
const pathToNode = getPath(rootA, nodeA);
return getNodeFromPath(rootB, pathToNode);
}
const targetNode = getSymmetricNode(rootA, rootB, nodeA);
console.log(nodeB === targetNode);
@MuhammadJamaluddin
Copy link

Thanks

const toWalk = [...path]; was probably not necessary?

@carefree-ladka
Copy link

//Recusrive
`
/**

  • @param {HTMLElement} rootA
  • @param {HTMLElement} rootB - rootA and rootB are clone of each other
  • @param {HTMLElement} nodeA
    */
    const findCorrespondingNode = (rootA, rootB, target) => {
    if (rootA === target) {
    return rootB
    }
    for (let i = 0; i < rootA.children.length; i++) {
    const res = findCorrespondingNode(rootA.children[i], rootB.children[i], target)
    if (res) return res
    }
    }`

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment