Facebook Interview Question for Software Engineers

Country: United States

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

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
}

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(
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
*/``````

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

``````package com.sample.tree;

import java.util.ArrayList;

public class Solution {

public static void main(String[] args){

Node root = new Node(3,"Root");

Node A1 = new Node(2,"A1");
Node A2 = new Node(0,"A2");
Node A3 = new Node(2,"A3");
Node A4 = new Node(0,"A4");

Node A11 = new Node(1,"A11");
Node A12 = new Node(0,"A12");
Node A13 = new Node(1,"A13");

Node A21 = new Node(0,"A21");
Node A22 = new Node(0,"A22");

Node A31 = new Node(1,"A31");
Node A32 = new Node(0,"A32");
Node A33 = new Node(0,"A33");

Node A41 = new Node(0,"A41");
Node A42 = new Node(1,"A42");

Node finalNode = removeZeroNodes(root);
printNodeValues(finalNode);
}

public static Node removeZeroNodes(Node node){

if(node.childNodes.isEmpty()){
if(node.value == 0) return null;
else return node;
} else {

ArrayList<Node> temp = new ArrayList<Node>();

for(Node childNode : node.childNodes){
Node resultNode = removeZeroNodes(childNode);
if(resultNode != null){
}
}
node.childNodes = temp;
if(node.value == 0 && node.childNodes.isEmpty()){
return null;
}else if(node.value == 0 && !node.childNodes.isEmpty()){
Node tempRoot = node.childNodes.get(0);
node.childNodes.remove(tempRoot);
tempRoot.childNodes = node.childNodes;
node = tempRoot;
return node;
}else{
return node;
}
}
}

public static void printNodeValues(Node node){

System.out.println(node.name);
if(!node.childNodes.isEmpty()){
for(Node childNode: node.childNodes)
printNodeValues(childNode);

}
}

public static class Node{
int value;
String name;
ArrayList<Node> childNodes = new ArrayList<Node>();

public Node(int value, String name){
this.value = value;
this.name = name;
}
}

}``````

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

we have to add children to tempRoot,

``tempRoot.childNodes.addAll(node.childNodes);``

``tempRoot.childNodes = node.childNodes;``

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

class TreeNode():
def __init__(self,value):
self.children = []
self.value = value

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)
print "---"
t.print_tree()
t = t.remove_zeros()
print "---"
t.print_tree()

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

{{
class TreeNode():
def __init__(self,value):
self.children = []
self.value = value

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)
print "---"
t.print_tree()
t = t.remove_zeros()
print "---"
t.print_tree()

}}

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

{{

class TreeNode():
def __init__(self,value):
self.children = []
self.value = value

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)
print "---"
t.print_tree()
t = t.remove_zeros()
print "---"
t.print_tree()

}}

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

``````class TreeNode():
def __init__(self,value):
self.children = []
self.value = value

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)
print "---"
t.print_tree()
t = t.remove_zeros()
print "---"
t.print_tree()``````

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

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

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

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

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.