Facebook Interview Question
Software EngineersCountry: United States
There will be 3 scenarios to consider:
- node is 0 and is leaf: simply remove node from parent children, return empty
- node is 0 and is a parent with non-empty valid children: make first child as the new "promoted" parent and return new collection of filtered-out children
- node is non-zero, return node and return filtered-out children
implementation of the above idea in Scala:
package code.tree
case class TreeNode(nodes: Seq[TreeNode] = Seq.empty, data: Int = 0)
object RemoveNodes {
def main(args: Array[String]): Unit = {
// Let us create the tree
val root = TreeNode(
nodes = Seq(
TreeNode(nodes = Seq(
TreeNode(data = 25), TreeNode(), TreeNode(data = 30), TreeNode()),
data = 14),
TreeNode(nodes = Seq(
TreeNode(data = 18), TreeNode(), TreeNode(data = 11), TreeNode()),
data = 6),
TreeNode(nodes = Seq(
TreeNode(data = 4), TreeNode(), TreeNode(data = 3), TreeNode())),
TreeNode(nodes = Seq(
TreeNode(), TreeNode(), TreeNode(data = 5), TreeNode(nodes = Seq(
TreeNode(data = 7), TreeNode(), TreeNode(data = 9), TreeNode()))))
),
data = 12
)
// Remove 0s
val head = removeZeros(root)
printTree(head)
}
def printTree(node: Option[TreeNode]): Unit = {
node match {
case Some(x) => printTree(x)
case _ => println("Empty tree")
}
}
def printTree(node: TreeNode): Unit = {
println(node.data)
node.nodes.foreach(printTree)
}
def getValidChildren(node: TreeNode) = {
node.nodes.map(removeZeros).filter(_.isDefined).map(_.get)
}
def removeZeros(node: TreeNode): Option[TreeNode] = {
if (node.data == 0 && node.nodes.isEmpty) {
None
}
else if (node.data == 0 && node.nodes.nonEmpty) {
val validChildren = getValidChildren(node)
Some(
TreeNode(
data = validChildren.head.data,
nodes = validChildren.drop(1)
)
)
}
else {
Some(
TreeNode(
data = node.data,
nodes = getValidChildren(node)
)
)
}
}
}
// output:
/*
12
14
25
30
6
18
11
4
3
5
7
9
*/
class TreeNode():
def __init__(self,value):
self.children = []
self.value = value
def add_child(self, v):
c = TreeNode(v)
self.children.append(c)
return c
def remove_zeros(self, ):
new_children = []
for c in self.children:
c = c.remove_zeros()
if c:
new_children.append(c)
self.children = new_children
if self.value != 0:
return self
elif len(self.children) == 0:
return None
c = self.children.pop()
self.value = c.value
self.children += c.children
return self
def print_tree(self):
print self.value
for c in self.children:
c.print_tree()
# 1
# 2
# 0 0
# 3 4
t = TreeNode(1)
c = t.add_child(2)
c.add_child(0)
c = c.add_child(0)
c = c.add_child(3)
c.add_child(4)
print "---"
t.print_tree()
t = t.remove_zeros()
print "---"
t.print_tree()
{{
class TreeNode():
def __init__(self,value):
self.children = []
self.value = value
def add_child(self, v):
c = TreeNode(v)
self.children.append(c)
return c
def remove_zeros(self, ):
new_children = []
for c in self.children:
c = c.remove_zeros()
if c:
new_children.append(c)
self.children = new_children
if self.value != 0:
return self
elif len(self.children) == 0:
return None
c = self.children.pop()
self.value = c.value
self.children += c.children
return self
def print_tree(self):
print self.value
for c in self.children:
c.print_tree()
# 1
# 2
# 0 0
# 3 4
t = TreeNode(1)
c = t.add_child(2)
c.add_child(0)
c = c.add_child(0)
c = c.add_child(3)
c.add_child(4)
print "---"
t.print_tree()
t = t.remove_zeros()
print "---"
t.print_tree()
}}
{{
class TreeNode():
def __init__(self,value):
self.children = []
self.value = value
def add_child(self, v):
c = TreeNode(v)
self.children.append(c)
return c
def remove_zeros(self, ):
new_children = []
for c in self.children:
c = c.remove_zeros()
if c:
new_children.append(c)
self.children = new_children
if self.value != 0:
return self
elif len(self.children) == 0:
return None
c = self.children.pop()
self.value = c.value
self.children += c.children
return self
def print_tree(self):
print self.value
for c in self.children:
c.print_tree()
# 1
# 2
# 0 0
# 3 4
t = TreeNode(1)
c = t.add_child(2)
c.add_child(0)
c = c.add_child(0)
c = c.add_child(3)
c.add_child(4)
print "---"
t.print_tree()
t = t.remove_zeros()
print "---"
t.print_tree()
}}
class TreeNode():
def __init__(self,value):
self.children = []
self.value = value
def add_child(self, v):
c = TreeNode(v)
self.children.append(c)
return c
def remove_zeros(self, ):
new_children = []
for c in self.children:
c = c.remove_zeros()
if c:
new_children.append(c)
self.children = new_children
if self.value != 0:
return self
elif len(self.children) == 0:
return None
c = self.children.pop()
self.value = c.value
self.children += c.children
return self
def print_tree(self):
print self.value
for c in self.children:
c.print_tree()
# 1
# 2
# 0 0
# 3 4
t = TreeNode(1)
c = t.add_child(2)
c.add_child(0)
c = c.add_child(0)
c = c.add_child(3)
c.add_child(4)
print "---"
t.print_tree()
t = t.remove_zeros()
print "---"
t.print_tree()
/*
* Assuming that there will be no INT_MIN value.
* struct Node {
* int val;
* vector<Node *> ptrs;
* };
*/
void deleteNodeWithVal(Node *root, int val) {
if (root == NULL) return;
for (auto x:root->ptrs) {
deleteNodeWithVal(x, val);
if (root->val == val) {
if (root->ptr.size() == 0) { delete root; root = NULL; }
else {
root->val = INT_MIN;
}
}
}
}
/*
* Assuming that there will be no INT_MIN value.
* struct Node {
* int val;
* vector<Node *> ptrs;
* };
*/
void deleteNodeWithVal(Node *root, int val) {
if (root == NULL) return;
for (auto x:root->ptrs) {
deleteNodeWithVal(x, val);
if (root->val == val) {
if (root->ptr.size() == 0) { delete root; root = NULL; }
else {
root->val = INT_MIN;
}
}
}
}
- Kamal January 03, 2019