Facebook Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
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
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
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.
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();
}
---
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;
}
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;
}
@hershi,
- Bruno Schwartz December 04, 2016Your 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.