## Facebook Interview Question for Software Engineers

• 0

Country: UK
Interview Type: Phone Interview

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

``````function scan(&\$root) {
if (\$root === NULL) {
return;
}
scan(\$root->left);
scan(\$root->right);
if (\$root->left !== NULL && \$root->right !== NULL) {
\$root->data = \$root->left & \$root->right;
}
}``````

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

function scan(&\$root) {
if (\$root === NULL) {
return;
}
scan(\$root->left);
scan(\$root->right);
if (\$root->left !== NULL && \$root->right !== NULL) {
\$root->data = \$root->left & \$root->right;
}
}

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

Pretty simple solution.
Just one thing needs clarification: what do you do when a node only has 1 child.

``````def correct(root):
if not root:
return 0
if not root.left and not root.right:
return root.val
root.val = int(correct(root.left) & correct(root.right))
return root.val``````

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

If last nodes of the tree have left = None and right = None

``````def invert_tree(node):
if node.left == None and node.right == None:
node.value ^= 1
else:
node.value = invert_tree(node.left) & invert_tree(node.right)
return node.value``````

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

The question is a little bit ambiguous.... I thought the question was asking that given an array of leafs you had to construct a correct tree. Here is a simple python code that does that

``````def print_tree(leafs):
current_level = leafs
print current_level
while len(current_level) > 1:
next_level = map(lambda x: int(x and x),
[current_level[x:x+2] for x in xrange(0, len(current_level), 2)])
print next_level
current_level = next_level``````

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

My running python solution:

``````#You have a binary tree which consists of 0 or 1 in the way, that each node value is a LOGICAL AND between its children:

#     0
#   /   \
#  0     1
# / \   / \
#0   1  1  1

#You need to write a code, which will invert given LEAF and put tree in a correct state.

class Node:
def __init__(self,value = "", left = None, right = None):
self._value = value
self._left  = left
self._right = right

def updateTree(node):
if node._left is not None and node._right is not None:
updateTree(node._left)
updateTree(node._right)
node._value = node._left._value and node._right._value

def invert(root, leaf):
if leaf._left != None or leaf._right != None:
return
leaf._value = not leaf._value
updateTree(root)

def initTree(number):
if number == 0:
return None
return Node(False,initTree(number -1),initTree(number -1))

def printTree(node):
if node == None: return
printTree(node._left)
printTree(node._right)
print node._value

def main():
root = initTree(3)
root._left._right._value = True
root._right._left._value = True
root._right._right._value = True
updateTree(root)
printTree(root)
print "after invert the first child"
invert(root,root._left._left)
printTree(root)

if __name__ == "__main__":
main()``````

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

C++ solution. Given the root and the node in question, we first construct the path from the root to the node, then we set the value of each node in this path to 'false'. I am not 100% satisfied with my path to node function, It would probably be better off with an iterative solution instead of a recursive one.

``````struct Node
{
bool val;
Node *left, *right;
Node(bool input)
: val {input}
, left {nullptr},
, right {nullptr}
{}

};

std::vector<Node*>
pathToNode(Node* root, Node* needle)
{
std::vector<Node*> result;
if(root == nullptr) return result;

if(needle == nullptr) return result;

if(root == needle){
result.push_back(needle);
return result;
}
//look left
result = pathToNode(root->left, needle);
if(result.size() != 0){
result.push_back(root);
return result;
}

//look right
result = pathToNode(root->right, needle);
if(result.size() != 0){
result.push_back(root);
return result;
}

return result;

}

void
invertLeaf(Node* root, Node* needle)
{
auto path = pathToNode(root, needle);
for(auto node : path){
node->val = false;
}
}``````

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

I suppose the tree does not have parent pointers. This can be done using postorder

``````public Node changeTree(Node root, Node leaf){
if(root == null || (root.left == null && root.right == null)){
return root;
}

Node leftNode = changeTree(root.left, leaf);
Node rightNode = changeTree(root.right, leaf);
if(leftNode == leaf){
leftNode.val = leftNode.val == 1 ? 0: 1;
}
else if(rightNode == leaf){
rightNode.val = rightNode.val == 1 ? 0: 1;
}

root.val = leftNode.val & rightNode.val;
return root;

}``````

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.