Facebook Interview Question
Software EngineersCountry: UK
Interview Type: Phone Interview
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[0] and x[1]),
[current_level[x:x+2] for x in xrange(0, len(current_level), 2)])
print next_level
current_level = next_level
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()
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;
}
}
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;
}
- Bappa Sarkar May 22, 2017