## Facebook Interview Question for SDE1s

• 1
of 1 vote

Country: United States

Comment hidden because of low score. Click to expand.
3
of 3 vote

Iterate through the original tree to find the target while being sure to apply the same moves on the deep copy tree.

``````TreeNode getDeepCopyNode(TreeNode root, TreeNode dcRoot, TreeNode target) {
if (root == null)		return null;

if (root == target) {
return dcRoot;
}

for (int i = 0; i < root.children.length; i++) {
TreeNode res = getDeepCopyNode(root.children[i], dcRoot.children[i], target);
if (res != null)	return res;
}

return null;
}``````

Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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
}
path = find_path(root_orig,node_orig)
apply_path( root_deep_copy, path )
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 {
};

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) {
return true;
}
}
}
return false;
}
void createTree(TreeNode& root, int depth);

void FindNode() {
TreeNode root;
createTree(root, 5);

TestNode testn(&tn);
if (findPath(root, testn)) {
TestPath tp(testn.path);
if (findPath(root, tp)) {
TreeNode* pathN = tp.node;
std::cout << "found\n";
}
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````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;
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.