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

- guilhebl December 31, 2018 | Flag Reply
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");
		
		A1.childNodes.add(A11);
		A1.childNodes.add(A12);
		A1.childNodes.add(A13);
		
		
		Node A21 = new Node(0,"A21");
		Node A22 = new Node(0,"A22");
		A2.childNodes.add(A21);
		A2.childNodes.add(A22);
		
		
		
		Node A31 = new Node(1,"A31");
		Node A32 = new Node(0,"A32");
		Node A33 = new Node(0,"A33");
		
		A3.childNodes.add(A31);
		A3.childNodes.add(A32);
		A3.childNodes.add(A33);
		
		
		Node A41 = new Node(0,"A41");
		Node A42 = new Node(1,"A42");
		
		A4.childNodes.add(A41);
		A4.childNodes.add(A42);
		
		
		root.childNodes.add(A1);
		root.childNodes.add(A2);
		root.childNodes.add(A3);
		root.childNodes.add(A4);
		
		
		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){
					temp.add(resultNode);
				}
			}
			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;
		}
	}

}

- Kamal January 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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()

- Anonymous January 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
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()

}}

- Anonymous January 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{

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()

}}

- Anonymous January 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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()

- Anonymous January 12, 2019 | Flag Reply
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;
            }
        }
    }
 }

- Anonymous January 15, 2019 | Flag Reply
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;
            }
        }
    }
 }

- h January 15, 2019 | 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