Facebook Interview Question for SDE1s


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

- raitGroup1007 July 25, 2017 | Flag Reply
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.

- NoOne July 23, 2017 | Flag Reply
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 
}
def facebook_problem( root_orig, node_orig, root_deep_copy){
    path = find_path(root_orig,node_orig)
    apply_path( root_deep_copy, path )
}

- NoOne July 23, 2017 | Flag Reply
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 {
	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";
		}
	}
}

- vzyarko July 25, 2017 | Flag Reply
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;
		}
	}

- koustav.adorable July 23, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More