## Facebook Interview Question for iOS Developers

• 5

Country: United States
Interview Type: In-Person

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

An in-order, depth-first traversal of a binary search tree (which an AVL is by definition) produces a sorted list of all elements in O(n) time. Simply take the middle element of this list in order to retrieve the median.

typedef void (^AVLTreeTraversalBlock)(AVLTree *tree, BOOL *stop);

@implementation AVLTree (CCPMedian)

- (void)ccp_depthFirstInOrderTraversalWithBlock:(AVLTreeTraversalBlock)block {
[self.left ccp_depthFirstInOrderTraversalWithBlock:block];

if (block) {
BOOL stop = NO;
block(self, &stop);
if (stop) {
return;
}
}

[self.right ccp_depthFirstInOrderTraversalWithBlock:block];
}

- (NSNumber *)ccp_median {
__block NSMutableArray *values = [NSMutableArray array];
[self ccp_depthFirstInOrderTraversalWithBlock:^(AVLTree *tree, BOOL *stop){
}];

// Assume we have a method ccp_middleValue that returns
// the middle element of a sorted list, or the mean of the two
// middle values if there are an even number of elements
// (the definition of the median according to Wikipedia).
return [values ccp_middleValue];
}

@end

Some optimizations could be made as well; for example, if the tree maintains a count of its nodes, we could stop our traversal once we reach the middle element (the median).

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

Binary Search Tree is not AVL tree. An AVL tree can be implemented as Balanced BST.

This was a question asked to my friend 1 week ago by Google recruiter
Q) Which one of these Data Structures have Log N traverse time

Red Black Tree
Binary Search Tree
Hash Table
Array
Directed Acyclic Graphs

He included BST in his answer which was wrong.
Watch out for these differences in interviews.

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

Are you sure it's "traverse" time?
Even for "retrieval" time, of course BST is not the answer since is doesn't have to be balanced.
But a AVL tree has to be a BST, except it's self-balancing.

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

AVL is a self-balancing BST by definition. You are right that BST is not AVL but question clearly tells its AVL tree, so we can use its BST property to do in-order traversal to get sorted values to find the median. The answer looks correct, I don't understand your comment. Can you kindly clarify more if am missing something.

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

@byteattack
AVL is a self-balancing BST by definition. You are right that BST is not AVL but question clearly tells its AVL tree, so we can use its BST property to do in-order traversal to get sorted values to find the median. The answer looks correct, I don't understand your comment. Can you kindly clarify more if am missing something.

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

For any balanced BST, maintain a count of number of nodes in its left sub-tree and number of nodes in right subtree + 1 (for itself). This can be maintained in constant time during insertion and deletion. Now finding a median is just finding the key with rank n/2 where n is total number of elements.

Time complexity - O(log n) in worst case.
Space Complexity - O(1)

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

What's the explanation for the space complexity to be O(1)? Where are the n BST nodes held?

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

n BST nodes are already given. It is O(1) extra space.

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

You are right, BST is not AVL and since BST could be unbalanced the search time of O(log n) can not be guaranteed in BST.

On the other hand AVL is a BST and it's almost balanced. So the answer to above question is "Red Black tree"

"mdc's" approach seems to be correct to find a median

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

The root of an AVL tree has the balance factor -1, 0 or 1.
If the balance factor is 0 the root's value is the median.
If the balance factor is -1 the median is the average of the root's value and the maximum value of root's left subtree.
If the balance factor is 1 the median is the average of root's value and the minimum of root's right subtree.
Complexity is logarithmic in N.

If the AVL structure is adjusted to keep track of max and min values then finding the median can be done in constant time.

Updating the min & max values when inserting/deleting from the tree adds overhead that is (worse case) logarithmic. For each node the min value is the min value of left child, the max value is the max value of the right child.

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

No, it doesn't work. AVL tree are balanced based on just the height of the left subtree and right subtree. There could be a big difference between the actual number of nodes in the two subtree.

For example, assume left subtree is a full binary tree of height k and right subtree is a full binary tree of size k minus one leaf deleted for all the nodes in the second to last level. The balance factor is 1 but the difference between the nodes in the subtrees are huge.

AVL tree seem to do jack squat for reducing the order of finding median. You can use it to get a sorted order and find the median which is still going to be O(n) which is order equivalent to finding the median in an array in the first place.

Anyone knows anyway which actually reduces the order, please email me. I am really interested to know.

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

I agree with Navid and that's why i subscribed to this question.

I would like to know:
or
we fill in values

We can implement BST using AVL tree

Keep counts
1) elements larger than median
2) elements smaller than median

calculate the median for first two elements

for third element onwards keep the track of the counters. If the counters differ by more than 2 then you know the tree might be out of order

then maybe we can do something at that step

to prove the point AVL BST is not a good median holder see this example
(insert into AVL BST with max diff = 1)
12 - 9 - 18 - 7- 10

This tree is still in balance ( the height differ by just 1 of left and right subtree of 12)
but the median should be 10.

12
9      18
7  10

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

@navid, no, it's not correct. "right subtree is a full binary tree of size k minus one leaf deleted for all the nodes in the second to last level." cannot be an AVL tree. In an AVL tree, The height of the tree may grow only after you fill completely, as otherwise there should be two subtree whose heights differ by >1.

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

As mdc said, you should use in-order DFS to traverse tree from minimal value up to the bigger values.

For memory consumption optimization you can do following things:
- maintain amount of added values to tree
- calculate amount of values at tree before actually getting median value

After that you know total amount of values at tree and you can find median just like that (python):

class Tree(object):
...
def inorder(self, node):
if node:
for i in self.inorder(node.left):
yield i
yield node.value
for i in self.inorder(node.right):
yield i

count = amount_of_value_at_tree

m_list = list(islice(tree.inorder(t.root), count/2+1))
if count % 2 == 1:
median = m_list[-1]
else:
median = (m_list[-1] + m_list[-2])/2
print median

But the question is - why do we need balanced tree here? We can do that calculation for any BST.

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

AVL tree with 2 modifications

1. Balance based on count of elements in left subtree and right
2. Balance all subtrees as well

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

Given 4 nodes, how do you construct such a tree?

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

I propose using 2 heaps - min-heap for the greater, and max-heap for the lesser. These heaps ensure O(1) in retrieving the minimal and maximal elements and O(logN) for insertion.
When inserting new values, we use the minimal and maximal to of the heaps to choose and update the right median.
We maintain balance (max diff of 1 between the heap sizes) by moving the minimal of the greater-heap, or the maximal of the lesser-heap to the opposite heap as needed. If the heaps are of same size, we can add the new value to either heap.
The median is the root of the heap with the +1 size, or the average of both roots, in case the sizes are equal.

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

- (Node *)medianWithRoot:(Node *)root
{
return root;
}

.... it's balanced. Might off by one or two spots, but bleh...

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

To put it simply , I ve used Binary Search Tree (didn't add up the balancing -rotation)
bottom line here is to traverse to capture all the value of the nodes
here's java code

public static void main(String[] args){

BinaryTree bt = new BinaryTree();

bt.insert(11);
bt.insert(5);
bt.insert(6);
bt.insert(9);
bt.insert(10);
bt.insert(15);
bt.insert(3);

bt.display();

bt.storeValue(bt.root);
System.out.println(bt.findMedian());

}

public class BinaryTree {

ArrayList<Integer> ar;
class Node{
int data;
Node leftChild;
Node rightChild;

public Node(int d){
this.data=d;
ar=new ArrayList<Integer>();
}
}

Node root;

public void insert(int d){
Node n=new Node(d);
if(root==null){
root=n;
}
else{
Node curr=root;
Node parr=null;

while(true){
parr=curr;
if(d<curr.data){
curr=curr.leftChild;
if(curr==null){
parr.leftChild=n;
return;
}
}
else{
curr=curr.rightChild;
if(curr==null){
parr.rightChild=n;
return;
}
}
}
}

}

public int getMaxDepth(Node n){
Node curr=n;
int count=0;
if(curr!=null){
count++;
if(curr.leftChild!=null && curr.rightChild==null)
return count+getMaxDepth(curr.leftChild);
else if(curr.leftChild==null && curr.rightChild!=null)
return count+getMaxDepth(curr.rightChild);
else {
if(getMaxDepth(curr.leftChild)>getMaxDepth(curr.rightChild))
return count+getMaxDepth(curr.leftChild);
else
return count+getMaxDepth(curr.rightChild);
}
}
else
return count;

}

public void display(){
Stack<Node> parr = new Stack<Node>();
Stack<Node> curr = new Stack<Node>();
boolean isEmptyRow=false;

parr.push(root);

while(isEmptyRow==false){
isEmptyRow=true;
while(parr.isEmpty()==false){
Node n=(Node)parr.pop();
if(n!=null){
System.out.print("  "+n.data+"  ");
curr.push(n.leftChild);
curr.push(n.rightChild);

if(n.leftChild!=null || n.rightChild!=null)
isEmptyRow=false;
}
else{
System.out.print("  **  ");
curr.push(null);
curr.push(null);
}
}

while(curr.isEmpty()==false){
parr.push(curr.pop());
}

System.out.println("\r\n");
}
}

public void storeValue(Node n){
if(n!=null){
if(n.leftChild!=null && n.rightChild==null)
storeValue(n.leftChild);
else if(n.leftChild==null && n.rightChild!=null)
storeValue(n.rightChild);
else if (n.leftChild!=null && n.rightChild!=null){
storeValue(n.leftChild);
storeValue(n.rightChild);
}
}
}

public Integer findMedian(){
Collections.sort(ar);
if(ar.size()%2==1)
return ar.get(((ar.size())+1)/2 - 1);
else
return (ar.get((ar.size()/2) -1 ) + ar.get(((ar.size()/2) + 1)) -1 )/2;
}

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

AVL trees are balanced height not count
I'd go with the following:
count left side, count right side, add 1 for the root and calculate tree size. O(n)
calculate if the median is to the left or to the right by subtracting the right0count from the left-count and divide by 2.
This will provide how many hops we should do and to which side.. O(k) - k is the imbalance count / 2

Cheers

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

The question is a little vague. It states "given" the tree, therefore I think that methods that take advantage of adding features to an AVL tree wouldn't be acceptable. Also, taking the node (or close to the node) seems a little easy, so I would have to say that the traversal methods are the only acceptable ones. Would like clarification on the question.

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

psuedo code -
1) Every node contains its left and right node counts
2) starting from root, check if leftsize == lowermedian if yes, then we found it -
a) check if n == odd, return (root->data)
b) else return( its successor + root->data ) /2;
3) Else check for left or right recursively.
T = O(logn) //As tree is balanced

int median(tree *root,int n, int orgN,int suc)
{
if(!root)	return 0;
if(n == 0) {
if(orgN & 1)	return root->data;
else {
if(root->right) {
int elem = min(root->right);
return (root->data + elem)/2;
} else {
return (root->data+suc)/2;
}
}
}
if(root->lsize == n)
return median(root,0,orgN,0);
else if(root->lsize < n)
return median(root->right,n-root->lsize-1,orgN,0);
else
return median(root->left,n,orgN,root->data);
}
//caller
median(root,(n-1)/2,n,0);

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

psuedo code -
1) Every node contains its left and right node counts
2) starting from root, check if leftsize == lowermedian if yes, then we found it -
a) check if n == odd, return (root->data)
b) else return( its successor + root->data ) /2;
3) Else check for left or right recursively.
T = O(logn) //As tree is balanced

int median(tree *root,int n, int orgN,int suc)
{
if(!root)	return 0;
if(n == 0) {
if(orgN & 1)	return root->data;
else {
if(root->right) {
int elem = min(root->right);
return (root->data + elem)/2;
} else {
return (root->data+suc)/2;
}
}
}
if(root->lsize == n)
return median(root,0,orgN,0);
else if(root->lsize < n)
return median(root->right,n-root->lsize-1,orgN,0);
else
return median(root->left,n,orgN,root->data);
}
//caller
median(root,(n-1)/2,n,0);

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ psuedo code - 1) Every node contains its left and right node counts 2) starting from root, check if leftsize == lowermedian if yes, then we found it - a) check if n == odd, return (root->data) b) else return( its successor + root->data ) /2; 3) Else check for left or right recursively. T = O(logn) //As tree is balanced {{{ int median(tree *root,int n, int orgN,int suc) { if(!root) return 0; if(n == 0) { if(orgN & 1) return root->data; else { if(root->right) { int elem = min(root->right); return (root->data + elem)/2; } else { return (root->data+suc)/2; } } } if(root->lsize == n) return median(root,0,orgN,0); else if(root->lsize < n) return median(root->right,n-root->lsize-1,orgN,0); else return median(root->left,n,orgN,root->data); } //caller median(root,(n-1)/2,n,0);}}} }}}
Comment hidden because of low score. Click to expand.
0
of 0 vote

psuedo code -
1) Every node contains its left and right node counts
2) starting from root, check if leftsize == lowermedian if yes, then we found it -
a) check if n == odd, return (root->data)
b) else return( its successor + root->data ) /2;
3) Else check for left or right recursively.
T = O(logn) //As tree is balanced

int median(tree *root,int n, int orgN,int suc)
{
if(!root)	return 0;
if(n == 0) {
if(orgN & 1)	return root->data;
else {
if(root->right) {
int elem = min(root->right);
return (root->data + elem)/2;
} else {
return (root->data+suc)/2;
}
}
}
if(root->lsize == n)
return median(root,0,orgN,0);
else if(root->lsize < n)
return median(root->right,n-root->lsize-1,orgN,0);
else
return median(root->left,n,orgN,root->data);
}
//caller
median(root,(n-1)/2,n,0);

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

I used a depth first traversal of an AVL Tree to recursively create a sorted array of all node keys. Using this array It was a simple matter of writing a method to find the mean of a sorted array (findMedianOfArray:_)

//Traverse the AVL Tree and keep track of node keys in the mutable array
-(double)findMedian:(AVLTreeNode*)node array:(NSMutableArray*)array {

if (node != nil) {
[self findMedian:node.left array:array];
[self findMedian:node.right array:array];
}

return [self findMedianOfArray:array.copy];
}

-(double)findMedianOfArray:(NSArray*)array {

NSNumber *medianNumber = @0;

if (array.count == 0) {
return 0;
}
if (array.count == 1) {
id medianObject = array.firstObject;
if ([medianObject isKindOfClass:[NSNumber class]]) {
return ((NSNumber*)medianObject).integerValue;
}
}

if (array.count % 2 == 1) { // is even
NSInteger medianIndex = (array.count / 2);
id medianObject = array[medianIndex];
if ([medianObject isKindOfClass:[NSNumber class]]) {
medianNumber = medianObject;
}
} else { //is odd
NSInteger medianIndex = (array.count / 2);
id medianObjectA = array[medianIndex];
id medianObjectB = array[medianIndex - 1];
if ([medianObjectA isKindOfClass:[NSNumber class]] && [medianObjectB isKindOfClass:[NSNumber class]]) {
medianNumber = [NSNumber numberWithDouble:(((NSNumber*)medianObjectA).doubleValue + ((NSNumber*)medianObjectB).doubleValue) / 2.0];

}
}

return medianNumber.doubleValue;
}

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.