Facebook Interview Question
SDE1sCountry: United States
Observe the notional xpath as defined as :
index1/index2/index3/.... implies from root, go to the node with index index1, that child's index2 child, then that child's index3 child so on and so forth.
It is obvious that we can have a function :
String find_path(TreeNode root, TreeNode node)
// returns the path to node in root, empty string otherwise.
Once we have that, the deep copy guy must have the xpath. Apply the same xpath to the deep copy tree, and you find the deep copy node.
TreeNode apply_path(TreeNode root, String xPath)
// returns the node to the path in root, null otherwise.
Some smart developer, may, want to combine these two functionalities for optimisations sake - I do not blame them, but they are inherently two distinct functionalities.
Now that the problem is split into 3 more problems, I am good to go. Next comment will have all the answers.
See my comments above.
def _recurse_( root, node, path ){
if ( empty(root.children) ){
return ( root == node ? path : '')
}
for ( inx : [0: size(root.children) ] ){
path = _recurse_(root.children[inx], node, path + '/' + inx )
if ( !empty(path) ){
return path
}
}
return ''
}
def find_path(root, node){
_recurse_(root,node,'')
}
def apply_path( root, path ){
if ( empty(path) ) return null
indexes = path.split('/')
cur = root
for ( inx : indexes ){
cur = cur[inx] ?? null
if ( empty(cur) ) return null
}
cur // reuturn
}
def facebook_problem( root_orig, node_orig, root_deep_copy){
path = find_path(root_orig,node_orig)
apply_path( root_deep_copy, path )
}
Since the tree B is exact copy of A the traversals A is repeatable in B. Thus a simple counter (node enumerator) will do the path. no need for string.
struct TreeNode {
std::vector<TreeNode> adjacentNodes;
};
struct TestNodeBase {
TestNodeBase(TreeNode* n, int p) : node(n), path(p) {}
TreeNode* node;
int path;
};
struct TestNode: TestNodeBase {
TestNode(TreeNode* n) : TestNodeBase(n, 1) {}
bool test(TreeNode* testNode) {
if (testNode == node)
return true;
path++;
return false;
}
};
struct TestPath : TestNodeBase {
TestPath(int p) : TestNodeBase(nullptr, p) {}
bool test(TreeNode* testNode) {
if (--path) {
return false;
}
node = testNode;
return true;
}
};
template <class T>
bool findPath(TreeNode& tree, T& test) {
if (test.test(&tree))
return true;
std::deque<TreeNode*> walkQue;
walkQue.push_back(&tree);
while (!walkQue.empty()) {
TreeNode* node = walkQue.front();
walkQue.pop_front();
for (int i = 0; i < node->adjacentNodes.size(); ++i) {
if (test.test( &(node->adjacentNodes[i]) )) {
return true;
}
walkQue.push_back(&(node->adjacentNodes[i]));
}
}
return false;
}
void createTree(TreeNode& root, int depth);
void FindNode() {
TreeNode root;
createTree(root, 5);
TreeNode& tn = root.adjacentNodes[1].adjacentNodes[2].adjacentNodes[0];
TestNode testn(&tn);
if (findPath(root, testn)) {
TestPath tp(testn.path);
if (findPath(root, tp)) {
TreeNode* pathN = tp.node;
std::cout << "found\n";
}
}
}
public static void main(String args[]) throws Exception {
}
public TreeNode getCopyNode(TreeNode root, TreeNode copy, TreeNode target) {
TreeNode op = null;
if (getCopyNode(root, copy, target, op))
return op;
return null;
}
public boolean getCopyNode(TreeNode root, TreeNode copy, TreeNode target, TreeNode node) {
if (copy!=null && copy.equals(target)) {
node = copy;
return true;
}
if (root.getChildren() != null) {
int i = 0;
for (TreeNode treeNode : root.getChildren()) {
if (getCopyNode(treeNode, copy.getChildren().get(i++), target, node))
return true;
}
}
return false;
}
static class TreeNode {
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((children == null) ? 0 : children.hashCode());
result = prime * result + data;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
TreeNode other = (TreeNode) obj;
if (children == null) {
if (other.children != null)
return false;
} else if (!children.equals(other.children))
return false;
if (data != other.data)
return false;
return true;
}
TreeNode(int data) {
this.data = data;
}
@Override
public String toString() {
return this.data + "";
}
int data;
List<TreeNode> children;
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public List<TreeNode> getChildren() {
return children;
}
public void setChildren(List<TreeNode> children) {
this.children = children;
}
}
Iterate through the original tree to find the target while being sure to apply the same moves on the deep copy tree.
- raitGroup1007 July 25, 2017