Facebook Interview Question for SDE1s


Country: United States




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

Pretty straight forward. The only thing to remember here is that when using "stack" we should push the "right" node before we push the "left" node (stack is FILO)

#include "CommonHeader.h"

class TreeNodeR
{
public:
    TreeNodeR* left = nullptr;
    TreeNodeR* right = nullptr;
    int value = 0;

    TreeNodeR() {}
    TreeNodeR(int v)
        : value(v)
    {
    }
};

static void doLevelOrderBottomRecurse(TreeNodeR* node, size_t depth, std::vector<std::vector<size_t> >& res)
{
    if(res.size() < (depth + 1)) {
        res.push_back({});
    }
    res[depth].push_back(node->value);
    if(node->left) {
        doLevelOrderBottomRecurse(node->left, depth + 1, res);
    }
    if(node->right) {
        doLevelOrderBottomRecurse(node->right, depth + 1, res);
    }
}

std::vector<std::vector<size_t> > levelOrderBottomRecurse(TreeNodeR* root)
{
    std::vector<std::vector<size_t> > res;
    doLevelOrderBottomRecurse(root, 0, res);
    std::reverse(res.begin(), res.end());
    return res;
}

std::vector<std::vector<size_t> > levelOrderBottomStack(TreeNodeR* root)
{
    std::vector<std::vector<size_t> > res;
    std::stack<std::pair<TreeNodeR*, size_t> > s;
    s.push({ root, 0 });
    while(!s.empty()) {
        std::pair<TreeNodeR*, size_t> p = s.top();
        s.pop();
        size_t depth = p.second;
        TreeNodeR* node = p.first;
        if(res.size() < (depth + 1)) {
            res.push_back({});
        }
        res[depth].push_back(node->value);
        // Since we are using "stack", we need to push the "right" element first
        // stack is FILO
        if(node->right) {
            s.push({ node->right, depth + 1 });
        }
        if(node->left) {
            s.push({ node->left, depth + 1 });
        }
    }
    std::reverse(res.begin(), res.end());
    return res;
}

static void print_result(const std::vector<std::vector<size_t> >& res)
{
    std::for_each(res.begin(), res.end(), [&](const std::vector<size_t>& v) {
        std::for_each(v.begin(), v.end(), [&](size_t v) { std::cout << " " << v; });
        std::cout << std::endl;
    });
}

// Test
void printReverseOrderTree()
{
    std::unordered_map<int, TreeNodeR> G;
    G[3] = TreeNodeR(3);
    G[9] = TreeNodeR(9);
    G[20] = TreeNodeR(20);
    G[15] = TreeNodeR(15);
    G[7] = TreeNodeR(7);

    G[3].left = &G[9];
    G[3].right = &G[20];
    G[20].left = &G[15];
    G[20].right = &G[7];

    std::vector<std::vector<size_t> > res1 = levelOrderBottomRecurse(&G[3]);
    print_result(res1);
    std::vector<std::vector<size_t> > res2 = levelOrderBottomStack(&G[3]);
    print_result(res2);
}

- PenChief October 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Question specifically says use stack and recursion. Cannot use any other data structure like queue, list or vector to store the result and print it. Idea of question is to exploit recursion as a way of storing the result string.

import java.util.Stack;

public class PrintBTReverseLevel {

    static class Node {
        int value;
        Node left;
        Node right;

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

        public void addLeftNode(int value) {
            Node n = new Node(value);
            this.left = n;
        }

        public void addRightNode(int value) {
            Node n = new Node(value);
            this.right = n;
        }
    }

    static int LEFTRIGHT = 0;
    static int RIGHTLEFT = 1;

    //called with root node and RIGHTLEFT as direction
    private static void printReverseLevelOrder(Stack<Node> stack, int direction) {

        if(stack.isEmpty())
            return;

        //Go to next level
        Stack<Node> nextLevel = new Stack<Node>();
        String currentLevel = "";
        while(!stack.isEmpty()) {
            Node p = stack.pop();
            if(direction==RIGHTLEFT) {
                if(p.right!=null)
                    nextLevel.push(p.right);
                if(p.left!=null)
                    nextLevel.push(p.left);
            }else {
                if(p.left!=null)
                    nextLevel.push(p.left);
                if(p.right!=null)
                    nextLevel.push(p.right);
            }
            if(direction==LEFTRIGHT) {
                //Add in currentLevel String as popped
                currentLevel += p.value+",";
            }else {
               //Add in currentLevel String in reverse order
                currentLevel = p.value + "," + currentLevel;
            }
        }

        printReverseLevelOrder(nextLevel, (direction==RIGHTLEFT)?LEFTRIGHT:RIGHTLEFT);

        currentLevel = currentLevel.substring(0, currentLevel.length()-1);
        currentLevel = "[" + currentLevel + "],";
        System.out.println(currentLevel);
        //Print current stack
    }

    public static void main(String args[]) {

        Node root = new Node(1);
        root.addLeftNode(2);
        root.addRightNode(3);

        root.left.addLeftNode(4);
        root.left.addRightNode(5);

        root.right.addLeftNode(6);
        root.right.addRightNode(7);

        root.left.left.addLeftNode(8);

        root.left.right.addLeftNode(9);
        root.left.right.addRightNode(10);

        Stack<Node> stack = new Stack<Node>();
        stack.push(root);

        System.out.println("[");
        printReverseLevelOrder(stack, RIGHTLEFT);
        System.out.println("]");

    }
}

- Anonymous October 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Printing from the array -

public static void main(String args[]){
        Integer[] nodes = {3, 9, 20, null, null, 15, 7};
        printFromLeaf(nodes, 1);
        System.out.println(nodes[0]);
    }
   
   
    public static void printFromLeaf(Integer[] nodes, int index){
        int n = nodes.length-1;
        if(index > n)
            return;
        
        int left = index*2;
        int right = index*2 + 1;
        
        if(left-1 <= n && nodes[left-1] != null)
            printFromLeaf(nodes, left);
        
        if(right-1 <= n && nodes[right-1] != null)
            printFromLeaf(nodes, right);

        if(left-1 <= n && right-1 <= n && nodes[left-1] != null && nodes[right-1] != null)
            System.out.println(nodes[left-1] + ", " + nodes[right-1]);
    }

- sudip.innovates October 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import sys

items = sys.stdin.readline().strip().split(' ')
tree_definition = []
for i in items:
    if i != 'None':
        tree_definition.append(int(i))
    else:
        tree_definition.append(None)
levels = {}
def add(tree, idx, level):
    if idx <= len(tree) and tree[idx] != None:
        # Add to my level
        if level in levels:
            levels[level].append(tree[idx])
        else:
            levels[level] = [ tree[idx] ]

        # Add left subtree to next level
        add(tree, idx*2+1, level+1)

        # Add right subtree to next level
        add(tree, idx*2+2, level+1)

add(tree_definition, 0, 0)

n = len(levels.keys())
for i in range(n):
    level = n-1-i
    print "{}".format(" ".join(map(str, levels[level])))

- Ruge October 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a Queue to do level order traversal. When putting nodes in Q, also put the levels.
Every time we pop from the Queue, push to the stack along with the level. Next, push the right child in the Queue (node.right, level+1) and THEN push the left child in the Queue.

In the end, stack has the data we need.

- pranaypratap October 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node:
  def __init__(self, val, left, right):
    self.left = left
    self.right = right
    self.val = val
  def get_left(self):
    return self.left
  def get_right(self):
    return self.right
  def get_val(self):
    return self.val

root = Node(5,
  Node(3,
    Node(2, Node(11, None, None), Node(10, None, None)),
    Node(22, None, None)
  ),
  Node(2,
    Node(11,
      Node(15, Node(16, None, None), Node(17, None, None)),
      Node(18, Node(19, None, None), Node(20, None, None))
    ),
    Node(10, None, None)
  )
)

def append_child(node):
  children = []
  if node.get_left():
    children.append(node.get_left())
  if node.get_right():
    children.append(node.get_right())
  return children
  
def get_values(arr):
  return list(map(lambda x: x.get_val(), arr));

def get_levels_in_reverse(stack):
  tmp = []
  item = stack.pop();
  while item:
    tmp.append(item)
    if len(stack) > 0:
      item = stack.pop() 
    else:
      item = None
      
  for node in tmp:
    stack.extend(append_child(node));
  
  if len(stack) > 0:
    return [get_values(tmp)] + get_levels_in_reverse(stack)
  return [get_values(tmp)]

print(get_levels_in_reverse([root]))

- Javascripter October 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

JavaScript solution

function helper(node, level, solution){
  if (!node){
    return;
  }
  
  if (level > solution.length - 1){
    solution.push([]);
  }
  solution[level].push(node.value);

  helper(node.left, level + 1, solution);
  helper(node.right, level + 1, solution);
}

function levelOrderBottom(root){
  const solution = [];
  helper(root, 0, solution);
  return solution.reverse();
}

const root = {
  value: 3,
  left: {
    value: 9,
    left: null,
    right: null
  },
  right: {
    value: 20,
    left: {
      value: 15,
      left: null,
      right: null
    },
    right: {
      value: 7,
      left: null,
      right: null
    },
  },
};

console.log(levelOrderBottom(root));

- Anonymous October 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In python this should do it:

def levelOrderBottom(root):
	l = []
	previous_level = 0
	queue = [(root,1)]
	while queue:
		node, height = queue.pop(0)
		if height != previous_level:
			l.append([])
			previous_level = height
		l[-1].append(node.data)
		if node.left is not None:
			queue.append((node.left, height+1))
		if node.right is not None:
			queue.append((node.right, height+1))
	return l[::-1]

Assuming a data structure like this:

class Node:
	def __init__(self, data, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right


root = Node(3)
root.left = Node(9)
root.right = Node(20, Node(15), Node(7))

- Jon Snow October 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

printReverseTree();

function createNode(value){
var node = {val: value, left: null, right: null};
return node;
}

function createTree() {
var node20 = createNode(20);
node20.left = createNode(15);
node20.right = createNode(7);
var tree = createNode(3);
tree.left = createNode(9);
tree.right = node20;
return tree
}

function printReverseTree(){
var tree = createTree();
var result = print(tree, 0, []);
result = result.reverse();
result.forEach(item => {
console.log(item);
});
}

function print(node, depth, result){

if(node.left){
print(node.left, depth + 1, result);
}
if(node.right){
print(node.right, depth + 1, result);
}

if(!result[depth])
result[depth] = [];

result[depth].push(node.val);
return result;
}

- Larissa Callogeras November 12, 2017 | 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