## Facebook Interview Question for Software Developers

Country: United States
Interview Type: Phone Interview

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

``````// Utility function to store vertical order in map 'm'
// 'hd' is horizontal distance of current node from root.
// 'hd' is initially passed as 0
static void getVerticalOrder(Node root, int hd,
TreeMap<Integer,Vector<Integer>> m)
{
// Base case
if(root == null)
return;

//get the vector list at 'hd'
Vector<Integer> get =  m.get(hd);

// Store current node in map 'm'
if(get == null)
{
get = new Vector<>();
}
else

m.put(hd, get);

// Store nodes in left subtree
getVerticalOrder(root.left, hd-1, m);

// Store nodes in right subtree
getVerticalOrder(root.right, hd+1, m);
}

// The main function to print vertical oder of a binary tree
// with given root
static void printVerticalOrder(Node root)
{
// Create a map and store vertical oder in map using
// function getVerticalOrder()
TreeMap<Integer,Vector<Integer>> m = new TreeMap<>();
int hd =0;
getVerticalOrder(root,hd,m);

// Traverse the map and print nodes at every horigontal
// distance (hd)
for (Entry<Integer, Vector<Integer>> entry : m.entrySet())
{
System.out.println(entry.getValue());
}
}``````

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

Does this work correctly? It looks like this is essentially doing a DFS traversal so it could improperly add node depth-wise. Imagine if in the example in the OP there was a child node to the right of the node with value 0, let's say with value 8. The printout should then be 5 9 0 6 1 8 4 7 3, but this function will output 5 9 0 6 8 1 4 7 3. I think you need to do BFS with a queue.

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

``````static void print(Node n) {
Deque<Node> stack = new ArrayDeque<>();
while (n != null) {
stack.push(n);
n = n.l;
}
doStack(stack);
}

static void doStack(Deque<Node> stack) {
if (stack.isEmpty()) {return;}
Node prev = stack.pop();
System.out.println(prev.v);
while (!stack.isEmpty()) {
Node n = stack.pop();
System.out.println(n.v);
print(prev.r);
prev = n;
}
print(prev.r);
}``````

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

beautiful

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

Clever but supports only tree example in question. It doesn't support tree like this:
*
* ..............6
* ............/...\
* ...........9.....4
* ........../..\....\
* .........5....1....6
* ..........\......../
* ...........0.... .7
* .............\.......
* ..............11
* ................\
* .................12
* ...................\
* ...................13
* .....................\
* ......................14
*/

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

I do not think it will work for this tree either:

``````/*
.........0
......../  \
.......-1..1
.........\
.........0
......../
......-1
....../
....-2
*/``````

It will print the upper -1 instead of the -2.

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

Algorithm:
- Do a inorder tree traversal with following changes
Root Node is denoted with Row Ordinal and Column Ordinal as 0
Every time traversal take a left, Column Ordinal is decremented by 1
Every time traversal take a right, Column Ordinal is incremented by 1
Every time traversal takes to children, Row Ordinal is incremented by 1
Every time traversal moves back to parent, Row Ordinal is decremented by 1
- Sort Nodes based on Column Ordinal, if Column Ordinal matches, then use Row Ordinal
- Print Sorted Nodes

Psuedo-Code:

``````- Class Node definition is (Value, Left, Right)
- Class NodeEx definition is (Value, RowOrdinal, ColumnOrdinal)

class TreePrinter {
private Node treeRootNode;
private ArrayList<NodeEx> nodes;

public TreePrinter(Node rootNode) {
this.treeRootNode = rootNode;
this.nodes = new ArrayList<NodeEx>();
}

public void printTree() {
this.nodes.clear();
traverseInOrder(rootNode, 0, 0);
sortNodesByOrdinals();
printNodes();
}

private void traverseInOrder(Node node, int rowOrdinal, int columnOrdinal) {
if (null == node) return;
this.nodes.append(new NodeEx(node.value, rowOrdinal, columnOrdinal));
traverseInOrder(node.Left, rowOrdinal+1, columnOrdinal-1);
traverseInOrder(node.Right, rowOrdinal+1, columnOrdinal+1);
}

private sortNodesByOrdinals() {
nodes.sort_by(node1, node2) {
if node1.ColumnOrdinal < node2.ColumnOrdinal return -1;
else node1.ColumnOrdinal > node2.ColumnOrdinal return +1;
else if node1.RowOrdinal < node2.RowOrdinal return -1;
else if node1.RowOrdinal > node2.RowOrdinal return +1;
else return 0;
}
}
}``````

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

``````public class ByColumnTree {

public static void main(String[] args) {

Node root = root(6);
Node n9 = root.left(9);
n9.left(5).right(0);
n9.right(1);
root.right(4).right(3).left(7);

traverse(fringe, root);

Collections.sort(fringe);
System.out.println(fringe);
}

private static void traverse(List<Node> fringe, Node node) {
if(node.left != null) traverse(fringe, node.left);
if(node.right !=  null) traverse(fringe, node.right);
}

static class Node implements Comparable<Node> {
Node left;
Node right;
int val;

int displacement;
int depth;
Node parent;

static Node root(int val) {
var node = new Node();
node.val = val;
return node;
}

Node left(int val) {
var node = new Node();
node.val = val;
node.depth = this.depth + 1;
node.displacement = this.displacement + 1;
node.parent = this;
this.left = node;
return node;
}

Node right(int val) {
var node = new Node();
node.val = val;
node.depth = this.depth + 1;
node.displacement = this.displacement - 1;
node.parent = this;
this.right = node;
return node;
}

@Override
public int compareTo(Node other) {
int d = Integer.compare(other.displacement, this.displacement);
if (d != 0) return d;
return Integer.compare(this.depth, other.depth);
}

@Override
public String toString() {
return String.valueOf(val);
}
}
}``````

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

6 is the root. the space didn't come along well.

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

in-order traversal

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

in-order traversal?

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

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

def getcoldistance(root,horzdist,mydict):
if not root:
return None
if horzdist in mydict:
mydict[horzdist].append(root.val)
else:
mydict[horzdist] = [root.val]
getcoldistance(root.left,horzdist-1,mydict)
getcoldistance(root.right,horzdist+1,mydict)

def printvertdist(root):
m = {}
getcoldistance(root,0,m)
for key in sorted(m):
for val in m[key]:
print(val,end='')

root =  Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.right = Node(8)
root.right.right.right = Node(9)

printvertdist(root)``````

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

using level order traversal and keeping a hash map to preserve the order

void printTree(TreeNode root){

if(root==null){
return;
}
int hd =0;

while(q.size()>0){
Pair pair = (Pair)q.poll();
TreeNode temp = q.getTreeNode();
hd = q.getHd();
if(temp.left!=null){
}
if(temp.right!=null){
}
}

Iterator<Integer> itr = map.getKeySet();
while(itr.hasNext()){
int key = (Integer)itr.next();
while(l!=null){
System.out.print(l.val+" ");
l= l.next;
}
}
}

void addValue(map, int key, int val){
if(map.get(key)==null){
map.put(0,l);
} else{
}
}

class Pair {
TreeNode node;
int hd;
public Pair(TreeNode node,int hd){
this.node = node;
this.hd =hd;
}
}

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

Traverse Breadth-First to preserve order for nodes with the same horizontal distance. Horizontal distance is used to find nodes in the same column I.e. horizontal distance for nodes 4, 7 and 12 is 1.
/*
..............6
............/...\
...........9.....4
........../..\....\
.........5....1....6
..........\......../
...........0.... .7
.............\.......
..............11
................\
.................12
...................\
...................13
.....................\
......................14
*/

``````private void printInVerticalOrder(Node root) {
if (root == null){
return;
}
TreeMap<Integer, List<Integer>> hdToValues = collectHorizontalDistancesToValues(root);
print(hdToValues);
}

private TreeMap<Integer, List<Integer>> collectHorizontalDistancesToValues(Node root) {
TreeMap<Integer, List<Integer>> hdToValues = new TreeMap<>();

while (!nodes.isEmpty()) {
HDNode hdNode = nodes.removeFirst();

hdToValues.putIfAbsent(hdNode.hd, new ArrayList<>());

if(hdNode.node.left != null){
}
if(hdNode.node.right != null){
}
}
return hdToValues;
}

private void print(TreeMap<Integer, List<Integer>> hdToValues) {
while (!hdToValues.isEmpty()) {
Map.Entry<Integer, List<Integer>> entry = hdToValues.pollFirstEntry();
entry.getValue().forEach(v -> System.out.print(v + " "));
System.out.println("\n");
}
}

private class HDNode {
int hd;
Node node;

HDNode(int hd, Node node) {
this.hd = hd;
this.node = node;
}
}``````

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

``````Class Data {
public int nodeVal;
public int dist;

public Data(int n, int d) { nodeVal = n; dist = d;}
}

void stupidTreePrint(Node root) {
List<Data> arr = new ArrayList<>();
auxFunc(root, 0, arr);

// stable sort
Collection.sort(arr, (o1, o2) -> Integer.signum(o1.dist-o2.dist));

arr.foreach(e -> System.out.println(" " + e.nodeval + " "));
}

void auxFunc(Node root, int dist, List<Data> arr) {
if(root == null) return;

Data tmp = new Data(root.value, dist);

auxFunc(root.left, dist - 1, arr);
auxFunc(root.right, dist + 1, arr);
}``````

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

python implementation
/*
..............6
............/...\
...........9.....4
........../..\....\
.........5....1....6
..........\......../
...........0.... .7
.............\.......
..............11
................\
.................12
...................\
...................13
.....................\
......................14
*/

``````class Node:
def __init__(self, val:int, left=None, right=None):
self.val,self.left,self.right = val,left,right
def __repr__(self): return f'{self.val}'

def mark_nodes(root, index, depth, res):
cut = None
if root.left is not None:
mark_nodes(root.left, index-1, depth+1, res)
res.append((root, index, depth))
if root.right is not None:
mark_nodes(root.right, index+1, depth+1, res)

def print_lrtd(sorted_nodes):
accum = []
mark_nodes(root, 0, 0, accum)
sorted_nodes = sorted(accum, key=lambda x: (x[1],x[2]))
return [i[0] for i in sorted_nodes]

Output:
stem = Node(0, None, Node(11, None, Node(12, None, Node(13, None, Node(14)))))
root = Node(6, Node(9, Node(5, None, stem), Node(1)), Node(4, None, Node(3, Node(7))))
print_lrtd(root)``````

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

``````def Node : { val : null, left : null, right : null  }
def Entry : { node : null, x : null, y : null }

def make_entries( entry_list, root , x_pos, y_pos  ){
entry_list += new ( Entry, root, x_pos, y_pos )
if ( !empty( root.left ) ) { make_entries( entry_list, root.left, x_pos - 1, y_pos + 1 ) }
if ( !empty( root.right ) ) { make_entries( entry_list, root.right, x_pos + 1, y_pos + 1 ) }
}

def visit_tree_column_and_row_wise( root ){
entries = make_entries( list(), root, 0, 0 )
// sort all entries by x_pos and then y_pos
sorta( entry_list ) where {
left_entry = \$.l
right_entry = \$.r
prec = sign( left_entry.x - right_entry.x )
if ( prec !=0 ) return prec
sign( left_entry.y - right_entry.y )
}
println( str( entry_list , "," ) as { \$.node.val }  )
}``````

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

``````class TNode:

def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right

def to_indexed_list(tree, row, col, nodes):
nodes.append(((col, row), tree.value))
if tree.left:
to_indexed_list(tree.left, row + 1, col - 1, nodes)
if tree.right:
to_indexed_list(tree.right, row + 1, col + 1, nodes)

def print_tree(t):
nodes = []
to_indexed_list(t, 0, 0, nodes)
nodes = sorted(nodes, key=lambda x: x[0])
for ((_, _), v) in nodes:
print(v)

t = TNode(6, TNode(9, TNode(5, None, TNode(0)), TNode(1)), TNode(4, None, TNode(3, TNode(7))))

print_tree(t)``````

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

``````int getTreeSize(node* root) {
if (root == NULL) {
return 0;
}

return 1 + getTreeSize(root->left) + getTreeSize(root->right);
}

void printColumnRowWise(node* root) {
int size = getTreeSize(root);
vector<int> cols[size];

// do a level order traversal
queue< pair<node*, int> > q;
q.push(make_pair(root, 0));

while (!q.empty()) {
// get the front node
pair<node*, int> p = q.front();

node* curr = p.first;
int curr_col = p.second;

// add the front node to cols vector
cols[curr_col + size / 2].push_back(curr->val);

if (curr->left) {
q.push(make_pair(curr->left, curr_col - 1));
}

if (curr->right) {
q.push(make_pair(curr->right, curr_col + 1));
}

// pop the front element
q.pop();
}

for (int i = 0; i < size; i++) {
for (int j = 0; j < cols[i].size(); j++) {
cout << cols[i][j] << " ";
}
}

cout<<endl;
}``````

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

``````int getTreeSize(node* root) {
if (root == NULL) {
return 0;
}

return 1 + getTreeSize(root->left) + getTreeSize(root->right);
}

void printColumnRowWise(node* root) {
int size = getTreeSize(root);
vector<int> cols[size];

// do a level order traversal
queue< pair<node*, int> > q;
q.push(make_pair(root, 0));

while (!q.empty()) {
// get the front node
pair<node*, int> p = q.front();

node* curr = p.first;
int curr_col = p.second;

// add the front node to cols vector
cols[curr_col + size / 2].push_back(curr->val);

if (curr->left) {
q.push(make_pair(curr->left, curr_col - 1));
}

if (curr->right) {
q.push(make_pair(curr->right, curr_col + 1));
}

// pop the front element
q.pop();
}

for (int i = 0; i < size; i++) {
for (int j = 0; j < cols[i].size(); j++) {
cout << cols[i][j] << " ";
}
}

cout<<endl;
}``````

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

``````int getTreeSize(node* root) {
if (root == NULL) {
return 0;
}

return 1 + getTreeSize(root->left) + getTreeSize(root->right);
}

void printColumnRowWise(node* root) {
int size = getTreeSize(root);
vector<int> cols[size];

// do a level order traversal
queue< pair<node*, int> > q;
q.push(make_pair(root, 0));

while (!q.empty()) {
// get the front node
pair<node*, int> p = q.front();

node* curr = p.first;
int curr_col = p.second;

// add the front node to cols vector
cols[curr_col + size / 2].push_back(curr->val);

if (curr->left) {
q.push(make_pair(curr->left, curr_col - 1));
}

if (curr->right) {
q.push(make_pair(curr->right, curr_col + 1));
}

// pop the front element
q.pop();
}

for (int i = 0; i < size; i++) {
for (int j = 0; j < cols[i].size(); j++) {
cout << cols[i][j] << " ";
}
}

cout<<endl;
}``````

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

``````#include <iostream>
#include <map>
#include <deque>

using namespace std;

struct Node
{
int data;
struct Node* left{nullptr};
struct Node* right{nullptr};

Node(int i) : data(i) {}
};

map<int, deque<int>> sMaps{};
int sLevel;

void foo(Node* pRoot)
{
if (!pRoot)
{
return;
}

sMaps[sLevel].push_front(pRoot->data);

--sLevel;
foo(pRoot->left);
++sLevel;

++sLevel;
foo(pRoot->right);
--sLevel;
}

int main()
{
Node* pRoot = new Node(6);
pRoot->left = new Node(9);
pRoot->left->left = new Node(5);
pRoot->left->left->right = new Node(0);
pRoot->left->left->right->left = new Node(2);
pRoot->left->left->right->left->right = new Node(3);

pRoot->right = new Node(10);
pRoot->right->left = new Node(11);
pRoot->right->right = new Node(12);

foo(pRoot);

for (auto const& pair : sMaps)
{
auto const& deque = pair.second;

auto it = deque.crbegin();
auto end = deque.crend();

while (it != end)
{
cout << *it << '\n';
++it;
}
}

return 0;
}

/*
5
2
9
0
3
6
11
10
12
*/``````

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

``````void print_tree(tree t) {
int d = depth(t);
int level = 2;
int indent = (std::pow(2, d) * 5) / 2 + 1;
std::vector<std::pair<int, tree>> frontier = { {indent, t} };
std::vector<std::pair<int, tree>> new_frontier;
std::vector<std::pair<int, tree>>& curr_frontier = frontier;
std::vector<std::pair<int, tree>>& next_frontier = new_frontier;
while (!curr_frontier.empty()) {
int curr_indent = 0;
for (auto& pair : curr_frontier) {
print_indent(pair.first - curr_indent);
std::cout << pair.second->value;
curr_indent = pair.first;
}
std::cout << std::endl;
curr_indent = 0;
for (auto& pair : curr_frontier) {
if (pair.second->left != nullptr) {
print_indent(pair.first - (d - level + 1) - curr_indent);
std::cout << "/";
next_frontier.push_back({ pair.first - 2 * (d - level + 1), pair.second->left });
curr_indent = pair.first - (d - level + 1);
}
if (pair.second->right != nullptr) {
print_indent(pair.first + (d - level + 1) - curr_indent);
std::cout << "\\";
next_frontier.push_back({ pair.first  + 2 * (d - level + 1), pair.second->right });
curr_indent = pair.first + (d - level + 1);
}
}
std::cout << std::endl;
curr_frontier.clear();
std::swap(curr_frontier, next_frontier);
++level;
}
}``````

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.