Facebook Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

@hershi,

Your next item leaf determination only holds true if current is less than the ancestor. If current is greater than the ancestor, then next that is greater than current will always test greater than the ancestor whether it is a leaf or not.

- Bruno Schwartz December 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

def get_leaves(pre_order, leaves):
    if not pre_order:
        return
    
    root = pre_order[0]
    if len(pre_order) == 1:
        leaves.append(root)
        return
        
    left_start = None
    left_end = None
    right_start = None
    righ_end = None
    for i in xrange(1, len(pre_order)):
        if not left_start and pre_order[i] <= root:
            left_start =  i
        
        if not right_start and pre_order[i] > root:
            right_start =  i
    
    if left_start:
        if right_start: left_end = right_start
        else: left_end = len(pre_order)
        get_leaves(pre_order[left_start:left_end], leaves)
    
    if right_start:
        right_end = len(pre_order)
        get_leaves(pre_order[right_start:right_end], leaves)

a = [5, 3, 2, 1, 4, 7, 6, 8]
a_leaves =[]
get_leaves(a, a_leaves)
print a_leaves

- Nitish Garg January 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can solve this using a stack and a root value.


You initialize the root as Integer.MIN_VALUE

for each number:
if number less than root -> return false;

if number greater than root -> pop stack until the peek value of the stack is greater than the number, make the last popped value the root, the other popped values are the leafes

push the number on the stack

- Peter November 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

With BST pre-order array, leaf node seems to be the element that smaller than next element. Is this assumption correct? If so, we can use this to write two loops for each of the array.

- Nobody November 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

From a pre-order traversal array of a BST, we can detect leaves by doing a sequential scan of the array with a helper stack (see code below for finding the next leaf).
From there, we can just keep on finding the next leaf in each tree and compare until we find leaves that don't match (or we run out of leaves in one tree before the other; or we just find no mismatches).

A binary tree with pre-order traversal array of 1,2,3 can be a root of 1 with left child 2 and right child 3, or it could be a linked list (e.g. 1 with right child 2, and 2 with right child 3)

Runtime: O(n). Space complexity: O(log n)

static int? NextLeaf(int[] preOrderTraversal, int offset, Stack<int> stack)
        {
            if (offset == preOrderTraversal.Length - 1)
            {
                return offset;
            }

            if (offset > preOrderTraversal.Length - 1)
            {
                return null;
            }

            var current = preOrderTraversal[offset];
            var next = preOrderTraversal[offset + 1];

            // Next is smaller? Then it is the left sub-tree root
            // Next item is bigger. Is it bigger than my ancestor?
            // No - then current is the parent, and the next item is the root of the right sub-tree
            // Yes - then current is a leaf. Pop ancestors until you get to the common ancestor (and pop that one too)
            if (current > next || stack.Count == 0 || next < stack.Peek())
            {
                stack.Push(current);
                return NextLeaf(preOrderTraversal, offset + 1, stack);
            }

            // The stack is empty, or the next is not bigger than the immediate ancestor. 
            while (stack.Count > 0 && stack.Peek() < next) stack.Pop();
            return offset;
        }

            if (preOrderTraversal1.Length == 0 || preOrderTraversal2.Length == 0)
            {
                return;
            }

            var iStack = new Stack<int>();
            var jStack = new Stack<int>();
            var i = NextLeaf(preOrderTraversal1, 0, iStack);
            var j = NextLeaf(preOrderTraversal2, 0, jStack);

            Console.WriteLine("Leaves: i {0}, j {1}", i, j);
            while (i.HasValue && j.HasValue && preOrderTraversal1[i.Value] == preOrderTraversal2[j.Value])
            {
                i = NextLeaf(preOrderTraversal1, i.Value + 1, iStack);
                j = NextLeaf(preOrderTraversal2, j.Value + 1, jStack);
            }

            Console.WriteLine("First mismatching leaves {0}, {1}", i, j);
        }

This can't be done for a generic tree, since there's no way to determine the leaves based on a pre-order traversal array.

- hershi November 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A code finding the next leave

PITM nxtleave(PITM p)
{
 PITM d;
 if((p->l==0)&&(p->r==0)) return p;
 if(p->l)
 {
   if(p->r)
	push(p->r);
   d=nxtleave(p->l);
   if(d!=0)
    return d;
 } else 
 if(p->r)
 {
   d=nxtleave(p->r);
   if(d!=0)
     return d;
 }
 return 0;
}

--- caller
	nxta=vroot;
	while(nxta)
	{
	 p=nxtleave(nxta);
	 nxta=pop();
	}

---

- Jeff Ding December 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

PITM nextleave(PITM p)
{
	PITM d;

	if(p->l)
	{
		if(p->r) push(p->r);
		return nextleave(p->l);
	} 
	if (p->r)
	{
		return nextleave(p->r);
	}
	return p;
}
Caller...while(p)
	{
		d=nextleave(p);
		if(d) printf("%d ",d->val);
		p=pop();
	}

- Jeff Ding December 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

PITM nextleaf(PITM p)
{
 if(p->l)
 {
   if(p->r) push(p->r);
   return nextleaf(p->l);
 }
 if(p->r)
 {
   return nextleaf(p->r);
 }
 return p;
}

Caller.... 
while(p)
	{
		d=nextleaf(p);
		p=pop();
	}

- Jeff Ding December 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Anonymous December 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Nobody
Its not true.
consider the case 5 3 4 8
With your logic 3 is also a leaf node which it is not.

Your statement is correct only for complete BST.

- Meg December 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Nobody

Its not true.
consider the case 5 3 4 8
With your logic 3 is also a leaf node which it is not.

Your statement is correct only for complete BST.

- Meg December 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find next leaf in the pre-order array and compare

void populate_leaves(const vector<int> &A, stack<int> &st, int cur) {
while(cur < A.size() - 1) {
int next = cur + 1;
if(next < A.size() - 1 && A[cur] < A[next]) {
break;
}
st.push(cur);
cur++;
}
}

int get_next_leaf(const vector<int> &A, stack<int> &st) {
while(!st.empty()) {
int cur = st.top();
st.pop();
int leaf = -1;
/*
if next < cur, then cur is left of next
if next > cur and next < cur's ancestor, then cur is leaf
*/
if(cur < st.size() - 2) {
int next = cur + 1;
if(A[cur] < A[next]) {
//if ancetros is > next then cur is leaf
if(!st.empty() && A[st.top()] < A[next]) {
leaf = cur;

while(!st.empty() && A[st.top()] < A[next]) {
st.pop();
}
}
populate_leaves(A, st, next);


if(leaf != -1) {
return leaf;
}
}

} else if (cur == st.size() -1) {
leaf = cur;
return leaf;
}
}

return -1;
}

vector<int> leaf_mismatch_bst_given_preorder(
const vector<int> &A, const vector<int> &B) {
vector<int> res = {-1, -1};

if(A.empty() || B.empty()) {
return res;
}

stack<int> a_st;
stack<int> b_st;
populate_leaves(A, 0);
populate_leaves(B, 0);

int aleaf = get_next_leaf(A, a_st);
int bleaf = get_next_leaf(B, b_st);

while(aleaf != -1 && bleaf != -1) {
if(A[aleaf] != B[bleaf]) {
res.push_back(A[aleaf]);
res.push_back(B[bleaf]);
return res;
}
aleaf = get_next_leaf(A, a_st);
bleaf = get_next_leaf(B, b_st);

}
return res;
}

- Arc January 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void populate_leaves(const vector<int> &A, stack<int> &st, int cur) {
while(cur < A.size() - 1) {
int next = cur + 1;
if(next < A.size() - 1 && A[cur] < A[next]) {
break;
}
st.push(cur);
cur++;
}
}

int get_next_leaf(const vector<int> &A, stack<int> &st) {
while(!st.empty()) {
int cur = st.top();
st.pop();
int leaf = -1;
/*
if next < cur, then cur is left of next
if next > cur and next < cur's ancestor, then cur is leaf
*/
if(cur < st.size() - 2) {
int next = cur + 1;
if(A[cur] < A[next]) {
//if ancetros is > next then cur is leaf
if(!st.empty() && A[st.top()] < A[next]) {
leaf = cur;

while(!st.empty() && A[st.top()] < A[next]) {
st.pop();
}
}
populate_leaves(A, st, next);


if(leaf != -1) {
return leaf;
}
}

} else if (cur == st.size() -1) {
leaf = cur;
return leaf;
}
}

return -1;
}

vector<int> leaf_mismatch_bst_given_preorder(
const vector<int> &A, const vector<int> &B) {
vector<int> res = {-1, -1};

if(A.empty() || B.empty()) {
return res;
}

stack<int> a_st;
stack<int> b_st;
populate_leaves(A, 0);
populate_leaves(B, 0);

int aleaf = get_next_leaf(A, a_st);
int bleaf = get_next_leaf(B, b_st);

while(aleaf != -1 && bleaf != -1) {
if(A[aleaf] != B[bleaf]) {
res.push_back(A[aleaf]);
res.push_back(B[bleaf]);
return res;
}
aleaf = get_next_leaf(A, a_st);
bleaf = get_next_leaf(B, b_st);

}
return res;
}

- Arc January 15, 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