Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

Use a queue to perform BFS. Enqueue 'null' at the end of each depth. Print the node values as they come from the queue. When you see 'null' then (i) print carriage return character (ii) enqueue null again. Do until queue size is 1 and contains only 'null'.

A sample code is below:

public static class printTree (Node root) {
	Queue<Node> q = LinkedList<Node>(); 	// an empty queue
	q.add(root);
	q.add(null); 		// use null as 'end of certain depth' marker
	do {
		Node x = q.remove();
		if (x != null)
			System.out.print(x.toString());
			if (x.left   != null) 	q.add(x.left);
			if (x.right != null) 	q.add(x.right);
		else {
			System.out.print("\r");
			q.add(null);
		}
	}
	while(q.size()>1 || q.peek() != null);
}

- autoboli January 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good I tried that strategy of using null for space and I could not get it to work right.

- Nelson Perez January 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question is the same which require newline feed in the previously asked question instead of newline feed you can replace it with carriage return.

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	static class Node
	{
		char value;
		Node left;
		Node right;
		
		public Node(char in)
		{
			this.value = in;
			this.left = null;
			this.right = null;
		}
	}
	static class Tree
	{
		Node root;
		
		public Tree(Node r)
		{
			this.root = r;
		}
		
		public  void treeBFS()
		{
			Queue<Node> queue = new LinkedList<Node>();
			
			queue.add(root);
			int count = 0;
			
			while(!queue.isEmpty())
			{
				if(count == 0)
				  count = queue.size();
				  
				Node c = queue.poll();
				count = count-1;
				if(c != null)
				{
					if(count == 0) 
					{
						System.out.print(" "+c.value);
						System.out.println(" ");
					}
					else
					{
						System.out.print(" "+c.value);
					}
					if(c.left != null);
					{
						queue.add(c.left);
					}
					if(c.right != null)
					{
						queue.add(c.right);
					}
				}
			}
		}
	}
	

	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Node A = new Node('A');
		Node B = new Node('B');
		Node C = new Node('C');
		Node D = new Node('D');
		Node E = new Node('E');
		Node F = new Node('F');
		Node G = new Node('G');
		
		A.left = B;
		A.right = C;
		
		B.left = D;
		B.right = E;
		
		C.left = F;
		C.right = G;
		
		Tree root = new Tree(A);
		root.treeBFS();
		
	}
}

- Himanshu Jain January 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I like how you use the count to make the new lines. I wish I though of that as I could not figure out how to maintain the level.

- Nelson Perez January 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Actually you could do that using a Queue and anther Queue just to maintain in the right order when printing.

public class Node<T>
{
	public Node<T> Left {get; set;}
	public Node<T> Right {get;set;}
	public T Data {get; set;}
}

private class NodeLevel<T>
{
	public Node<T> Node {get; set;}
	public int Level {get; set;}
}

static public string GetBinaryTreeRows<T>(Node<T> root)
{
	if(root == null) return null;
	
	
	Queue<NodeLevel<T>> Q = new Queue<NodeLevel<T>>();
	Queue<NodeLevel<T>> S = new Queue<NodeLevel<T>>();
	
	Q.Enqueue(new NodeLevel<T>(){ Node=root, Level=0});
	
	while(Q.Count > 0)
	{
		NodeLevel<T> np = Q.Dequeue();
		Node<T> n = np.Node;
		S.Enqueue(np);
		
		if(n.Left != null)
		{
			Q.Enqueue(new NodeLevel<T>(){ 
				Node = n.Left, 
				Level = np.Level + 1});
		}
		
		if(n.Right != null)
		{
			Q.Enqueue(new NodeLevel<T>(){ 
				Node = n.Right, 
				Level = np.Level + 1});
		}
	}
	
	StringBuilder sb = new StringBuilder();
	
	int lastLevel = 0;
	while(S.Count > 0)
	{
		NodeLevel<T> np = S.Dequeue();
		if(np.Level != lastLevel)
		{
			lastLevel= np.Level;
			sb.Append("\n");
		}
		
		sb.Append(np.Node.Data.ToString());
		sb.Append(" ");
	}
	return sb.ToString();
}

I've tested using this code. Does not seem clear the tree but it looks like this:

(d)
	   /      \
      (b)         (g)
     /    \        /   \
 (a)    (c)   (e)  (h)
                    \
                    (f)

void Main()
{
	// Tree
	// a - h
	Node<string> root = new Node<string>(){
		Data = "d",
		Left = new Node<string>(){
			Data = "b",
			Left = new Node <string> ()
			{
				Data = "a"
			},
			Right = new Node<string>()
			{
				Data = "c"
			}
		},
		Right = new Node<string>()
		{
			Data = "g",
			Left = new Node<string>()
			{
				Data = "e",
				Right = new Node<string>()
				{
					Data = "f"
				}
			},
			Right = new Node<string>()
			{
				Data = "h"
			}
		}
	};

	string expected = "d \nb g \na c e h \nf ";

	string output = GetBinaryTreeRows(root);

	Console.WriteLine(output);

		if(output != expected)
		{
			throw new Exception("Test Failed");
		}
}

- Nelson Perez January 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ID (Iterative Deepening solution). Please recall that ID has same asymptotic time complexity as either BFS or DFS.

public static void printLevels(Node root) {
	int depth=0;
	while(printDepth(root, 0, depth) > 0){
		depth++;
		System.out.println();
	}
}
public static int printDepth(Node curNode, int curDepth, int targetDepth) {
	if (curDepth==targetDepth){
		System.out.print(curNode.val());
		return 1;
	}
	int sum=0;
	if (curNode.left() != null) {
		sum += printDepth(curNode.left(), curDepth+1,targetDepth);
	}
	if (curNode.right() != null) {
		sum += printDepth(curNode.right(), curDepth+1,targetDepth);
	}
	return sum;
}

- CT January 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) runtime complexity and O(log n) max memory (it seems like someone asks this question at least once a week...):

class Node{
	Node left, right;
	char c;
}

public static void print(Node node){
	if(node == null){
		return;
	}

	LinkedList<Node> list = new LinkedList<Node>();
	LinkedList<Node> alt = new LinkedList<Node>();
	LinkedList<Node> temp;
	list.add(node);
	StringBuilder b = new StringBuilder();
	while(!list.isEmpty()){
		while(!list.isEmpty()){
			node = list.removeFirst());
			if(node.left != null){
				alt.add(node.left);
			}
			if(node.right != null){
				alt.add(node.right);
			}
			b.append(node.c);
		}
		System.out.println(b.toString());
		b.setLength(0);
		temp = list;
		list = alt;
		alt = temp;
	}
}

- zortlord January 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take a array of n/2 size that's the maximum length the output can be.Initialize it with INT_MAX or INT_MIN.

Take an index i which always point to the first element in this array

Do level order traversal and put the elements in the array in the order we traverse. By now the index points to the last element of the current row. After completing each row intialize the index again to the starting index of the array and repeat till all rows are exhausted.

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

import java.util.LinkedList;
import java.util.Queue;

class BinaryTreeRows {
	public static void main (String [] args) {
		Node root = new Node(8);
		root.left = new Node(1);
		root.left.left = new Node(3);
		root.left.left.left = new Node(4);
		root.left.left.left.right = new Node(3);
		root.left.right = new Node(6);
		root.left.right.right = new Node(2);
		root.right = new Node(9);
		root.right.left = new Node(-1);
		root.right.right = new Node(6);

		printTree(root);
	}

	public static void printTree(Node node) {
		Queue<Node> queue = new LinkedList<Node>();
		queue.offer(node);
		boolean newLevel = true;
		int levelCount = 0, currentCount = 0;
		while (queue.size() != 0) {
			if (newLevel == true) {
				System.out.println("\n");
				newLevel = false;
				levelCount = queue.size();
				currentCount = 0;
			}
			Node element = queue.poll();
			System.out.print(element.value + "\t");
			if (element.left != null) {
				queue.offer(element.left);
			}
			if (element.right != null) {
				queue.offer(element.right);
			}
			currentCount++;
			if (currentCount == levelCount) {
				newLevel = true;
			}
		}
	}
}

class Node {
	Node left;
	Node right;
	int value;
	Node (int value) {
		this.value = value;
		this.left = null;
		this.right = null;
	}
}

- Sumeet Singhal January 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.*;
import java.util.*;


class Node
{

int data;
public Node left;
public Node right;

public Node(int d)
{
this.data=d;
this.left=null;
this.right=null;
}

}


class printtree
{
public static HashMap<Integer,List<Node>> gs;

public static void main(String[] args)
{
Node root = new Node(1);
root.left = new Node(2);
root.right= new Node(3);


root.left.left=new Node(4);
root.left.right=new Node(5);

root.right.left=new Node(6);
root.right.right=new Node(7);

print(root);

}


public static void print(Node root)
{
gs=new HashMap<Integer,List<Node>>();
func(root,1);

int i=1;
while(gs.containsKey(i))
{
for(Node n : gs.get(i))
{
System.out.print(n.data+",");
}

System.out.println("");
i++;
}

}

public static void func(Node node, int i)
{

if(!gs.containsKey(i))
gs.put(i,new ArrayList<Node>());

gs.get(i).add(node);


if(node.left!=null)
func(node.left,i+1);

if(node.right!=null)
func(node.right,i+1);
}


}

- BlueStag March 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is an efficient java solution:

import java.io.*;
import java.util.*;


class Node 
{

int data;
public Node left;
public Node right;

public Node(int d)
{
	this.data=d;
	this.left=null;
	this.right=null;
}

}


class printtree
{
	public static HashMap<Integer,List<Node>> gs;

	public static void main(String[] args)
	{
		Node root = new Node(1);
		root.left = new Node(2);
		root.right= new Node(3);


		root.left.left=new Node(4);
		root.left.right=new Node(5);

		root.right.left=new Node(6);
		root.right.right=new Node(7);

		print(root);

	}


	public static void print(Node root)
	{
		gs=new HashMap<Integer,List<Node>>();
		func(root,1);
		
		int i=1;
		while(gs.containsKey(i))
		{
			for(Node n : gs.get(i))
			{
				System.out.print(n.data+",");
			}
		
			System.out.println("");
			i++;
		}		

	}
	
	public static void func(Node node, int i)
	{

		if(!gs.containsKey(i))
			gs.put(i,new ArrayList<Node>());
		
		gs.get(i).add(node);


		if(node.left!=null)
			func(node.left,i+1);

		if(node.right!=null)
			func(node.right,i+1);
	}


}

- BlueStag March 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.*;
import java.util.*;


class Node 
{

int data;
public Node left;
public Node right;

public Node(int d)
{
	this.data=d;
	this.left=null;
	this.right=null;
}

}


class printtree
{
	public static HashMap<Integer,List<Node>> gs;

	public static void main(String[] args)
	{
		Node root = new Node(1);
		root.left = new Node(2);
		root.right= new Node(3);


		root.left.left=new Node(4);
		root.left.right=new Node(5);

		root.right.left=new Node(6);
		root.right.right=new Node(7);

		print(root);

	}


	public static void print(Node root)
	{
		gs=new HashMap<Integer,List<Node>>();
		func(root,1);
		
		int i=1;
		while(gs.containsKey(i))
		{
			for(Node n : gs.get(i))
			{
				System.out.print(n.data+",");
			}
		
			System.out.println("");
			i++;
		}		

	}
	
	public static void func(Node node, int i)
	{

		if(!gs.containsKey(i))
			gs.put(i,new ArrayList<Node>());
		
		gs.get(i).add(node);


		if(node.left!=null)
			func(node.left,i+1);

		if(node.right!=null)
			func(node.right,i+1);
	}


}

- bluestag March 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.*;
import java.util.*;


class Node 
{

int data;
public Node left;
public Node right;

public Node(int d)
{
	this.data=d;
	this.left=null;
	this.right=null;
}

}


class printtree
{
	public static HashMap<Integer,List<Node>> gs;

	public static void main(String[] args)
	{
		Node root = new Node(1);
		root.left = new Node(2);
		root.right= new Node(3);


		root.left.left=new Node(4);
		root.left.right=new Node(5);

		root.right.left=new Node(6);
		root.right.right=new Node(7);

		print(root);

	}


	public static void print(Node root)
	{
		gs=new HashMap<Integer,List<Node>>();
		func(root,1);
		
		int i=1;
		while(gs.containsKey(i))
		{
			for(Node n : gs.get(i))
			{
				System.out.print(n.data+",");
			}
		
			System.out.println("");
			i++;
		}		

	}
	
	public static void func(Node node, int i)
	{

		if(!gs.containsKey(i))
			gs.put(i,new ArrayList<Node>());
		
		gs.get(i).add(node);


		if(node.left!=null)
			func(node.left,i+1);

		if(node.right!=null)
			func(node.right,i+1);
	}


}

- bluestag March 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void printTree(){
        Queue q= new LinkedList();
        int curLevel=0;
        int nextLevel=0;
        
        q.add(root);
        curLevel++;
        
        while(!q.isEmpty()){
            Node x=(Node) q.remove();
            curLevel--;
            System.out.print(x.value+" ");
            
            if(x.lChild!=null)
            {
                q.add(x.lChild);
                nextLevel++;
            }
            if(x.rChild!=null)
            {
                q.add(x.rChild);
                nextLevel++;
            }
            if(curLevel==0)
            {
                curLevel=nextLevel;
                nextLevel=0;
                System.out.print("\n");;
            }
            
        }
        
    }

- SG March 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Initialize 2 parameters currentLevel and nextLevel. when currentLevel=0 then next level becomes currentLevel.

void printT(){
        Queue q= new LinkedList();
        int curLevel=0;
        int nextLevel=0;
        
        q.add(root);
        curLevel++;
        
        while(!q.isEmpty()){
            Node x=(Node) q.remove();
            curLevel--;
            System.out.print(x.value+" ");
            
            if(x.lChild!=null)
            {
                q.add(x.lChild);
                nextLevel++;
            }
            if(x.rChild!=null)
            {
                q.add(x.rChild);
                nextLevel++;
            }
            if(curLevel==0)
            {
                curLevel=nextLevel;
                nextLevel=0;
                System.out.print("\n");;
            }
            
        }
        
    }

- SG March 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use a breadth-first traversal, taking advantage of the fact that it's a binary tree (number of nodes doubles at each level as we move down the tree)

void printBinaryTree(Node root) {
	Queue<Node> q = new LinkedList<>();
	q.add(root);
	int visitedNodeCount = 0;
	int printNewLineAt = 1;

	while (!q.isEmpty()) {
		Node n = q.poll();
		if (n.left != null) {
			q.add(n.left);
		}
		
		if (n.right != null) {
			q.add(n.right);
		}
		
		print(node.data);
		visitedNodeCount++;

		if (visitedNodeCount == printNewLineAt) {
			printNewLineAt *= 2;
			print('\n');
		}
	}
}

- Daniel August 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ solution with BFS.

#include <list>
#include <iostream>
using namespace std;

struct node {
	node* left;
	node* right;
	int value;
	node(int v):value(v),left(0), right(0){}
};

void print_tree(node * root)
{
	list<node *>queue;
	int cur_children = 0;
	int next_children = 0;

	if (!root)
		return;

	queue.push_back(root);
	cur_children++;
	while(queue.size())
	{
		node* cur = queue.front();
		queue.pop_front();
		if (cur->left)
		{
			queue.push_back(cur->left);
			next_children++;
		}
		if (cur->right)
		{
			queue.push_back(cur->right);
			next_children++;
		}
		cout<<cur->value<<" ";
		if (--cur_children == 0)
		{
			cout<<endl;
			cur_children = next_children;
			next_children = 0;		
		}
	}
}

- hankm2004 August 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

A row means all those nodes with the same depth ? Level traverse using a queue ?

- uuuouou January 09, 2015 | 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