## Facebook Interview Question for Data Scientists

Country: United States
Interview Type: Phone Interview

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

This question is completely different than tree walk algorithm.
There are two different solutions to this problem. Running time of them is O(n lg n) and O(n).
Solution 1 ( O(n lg n) ):
Set a key value to each node. Set the key of root to n. Start BFS from the root. At each step when you visit a node, set the left child key to nodes’ key minus one and the right child key to nodes’ key plus one; then insert the node at the end of an array. After BFS is finished, sort the array based on the key using a stable sorting algorithm in O(n lg n).
Solution 2 ( O(n) ):
Create an array of size 2n. Simulate the counting sort during BFS, such that after your BFS each index includes the count of nodes with that key. Repeat BFS one more time; insert the elements in the sorted format in the second array of size n by using the information of the first array in a counting sort manner. This takes O(n) to finish.

Note: Both algorithms need O(n) space.

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

I would first define what a column in a tree is. I think a recursion can help:
#columns(root)=#columns(root.left)+length(root.value)+#columns(root.right),
#columns(empty tree)=0

The position at which to print node value is: (level of the node, #columns(root.left))

If I can't print at x,y positions I need a level order traversal to print line by line.

It is O(n) time and O(n) space (for the level order traversal and the position)

Note, there are better ways to layout the tree, if the tree has branches that can be kind of nested into each other.

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

I think he/she means the columns in this format.

7
/ \
8 2
/ / \
1 3 4
/ \
5 9
\
6

That would be 1, 8, 5, 7, 3, 2, 9, 4, 6.
Those solutions are correct in my opinion. I think finding better than O(n) is not possible? Any suggestions?

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

If you really think about it, this question doesn't make any sense. the question is assuming an invalid graphical layout of a binary tree. Layout a large binary tree on paper and you will see what I mean. I am surprised that facebook would even ask such a faulty question.

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

``````# Time:  O(n)
# Space: O(n)

# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None

import collections
# BFS + hash solution.
class Solution(object):
def verticalOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
cols = collections.defaultdict(list)
queue = [(root, 0)]
for node, i in queue:
if node:
cols[i].append(node.val)
queue += (node.left, i - 1), (node.right, i + 1)
return [cols[i] for i in xrange(min(cols.keys()), max(cols.keys()) + 1)] \
if cols else []

if __name__ == "__main__":
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(4)
result = Solution().verticalOrder(root)
print result

##Output : [, [1, 5, 6], , ]``````

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.