VMWare Inc Interview Question for Software Engineer / Developers


Country: United States




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

We know in BST root is bigger than all nodes in left subtree and is no larger than all nodes in right subtree. Thus, if the array is a post traversal of a BST, then arr[n-1] can divide the array into two parts arr[0, i) and arr[i, n-1), where
(1)each item in arr[0, i) is less than arr[n-1]
(2)each item in arr[i, n-1) is not less than arr[n-1]
(3)both arr[0, i) and arr[i, n-1) are post traversals of BSTs.

bool isPostTraversalOfBST(int arr[], int n)
{
	if(n < 2) return true;

	int i = 0;
	//try to find out the beginning of right subtree's traversal
	for(; arr[i] < arr[n-1]; ++i) ;
	//check if all arr[i,n-1) >= arr[n-1]
	for(int j = i + 1; j + 1 < n; ++j){
		if(arr[j] < arr[n-1]) return false;
	}
	//check if both two parts are post traversals of BSTs
	return isPostTraversalOfBST(arr, i) &&
		   isPostTraversalOfBST(arr + i, n - i - 1);
}

- uuuouou April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Maybe the last statement should be :
return isPostTraversalOfBST(arr, i) &&
isPostTraversalOfBST(arr + i, n - 1);

- 1wanna August 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a nice solution. Would this work if the tree is as follows?

1
\
2

This should lead to a post traversal of [2, 1].

Hand simulating the code, I get the result of false. Yet, this tree does follow the BST property that every node in the left subtree of a node is less than the node and every node in the right subtree of a node is greater than the node.

- bob October 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

For a binary tree inorder traversal and either a postorder or preorder traversal can uniquely identify the tree.
The inorder sequence will resolve the left-right problem, and the other sequence (pre or post) will tell us the roots of the various subtrees. For example, if inorder is CBA, and preorder is CAB, then we know that C is at the root, and both B and A are in the right subtree.
In short to reconstruct the BT from the array we need at least two types of traversals. I don't think it is feasible to reconstruct BT with only post order traversal.

- hulkthedestroyer April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

exactly

- Srinivas April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You're right. We can not reconstruct from only the postorder traversal. We can reconstruct the tree only if we already know that it is a BST. In the general case it needs postorder+ inorder or preorder+inorder. !!!! in the general case postorder+preorder is not enough either

- Anonymous April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Nice question! :-)

I have a solution with O(n) running time for this. We are going to traverse the array from the end. The idea is to maintain a collection of legal sub-trees to enter and to find a fit for the current element in those sub-trees. Note that, in the postorder traversal, we are always sure that all nodes in the left sub-tree of a given node appear before all nodes in the right sub-tree of that node. Knowing this, we can conclude that all sub-trees in our collection that are to the right of the current fit (for the current element), all become illegal and should be discarded. This observation tells us what data structure we should be using, and that DS is stack. The structure for the sub-trees is an implementation detail and you could get a sense of it in the following code.

My C++ implementation:

#include <iostream>
#include <stack>

using namespace std;

const int INF = (-1) ^ (1 << 31);

class TreeNode{
private:
	int data;
	TreeNode *left, *right, *par;
public:
	TreeNode()
		:left(NULL), right(NULL), par(NULL) { }
	TreeNode(TreeNode *prnt, int val)
		:data(val), left(NULL), right(NULL), par(prnt)
	{
		if (prnt == NULL)
			return;

		if (data < prnt->data)
			prnt->left = this;

		else
			prnt->right = this;
	}
	int getVal()		{ return this->data; }
	TreeNode* getRight(){ return this->right; }
	TreeNode* getLeft()	{ return this->left; }
	TreeNode* getPar()	{ return this->par; }
};

struct StackElem{
	int LB, RB;
	TreeNode *par;
	StackElem(int l, int r, TreeNode *p)
		:LB(l), RB(r), par(p){ }
};

bool fits(int b, int a, int c)
{
	return (b >= a && b <= c);
}

pair <bool, TreeNode*> solve(int *ary, int n)
{
	if (!n)
		return make_pair(true,(TreeNode *) NULL);

	TreeNode* root = new TreeNode(NULL, ary[n - 1]);

	stack <StackElem *> stk;

	stk.push(new StackElem(-INF, ary[n - 1], root));
	stk.push(new StackElem(ary[n - 1], INF, root));

	for (int i = n - 2; i >= 0; i--)
	{
		while (true)
		{
			StackElem *cur = stk.top();
			stk.pop();

			if (cur->RB < ary[i])
				return make_pair(false,(TreeNode *) NULL);

			if (fits(ary[i], cur->LB, cur->RB))
			{
				TreeNode *newNode = new TreeNode(cur->par, ary[i]);
				stk.push(new StackElem(cur->LB, ary[i], newNode));
				stk.push(new StackElem(ary[i], cur->RB, newNode));
				break;
			}
		}
	}

	return make_pair(true, root);
}

- iroodaz April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In the question they mentioned it is binary tree, and has given only one order i.e, but it is not possible to construct tree from a single order, at least we need any two tree traversals.

- Srinivas April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not any 2. The inorder should be one of them.

- Anonymous April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

*only post order has given,

If we assume that the given binary tree is complete binary tree, then we can construct the tree as uuuouou@ mentioned in his or her first comment.

- Srinivas April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

***EDIT: The OP HAS actually mentioned it should be a BST. Read the statement carefully. ***

Come on guys! It is trivial to construct a binary tree with only one traversal given to us. We can simply return a chain. No big deal! The OP certainly has forgotten to mention it is a BST. If you take a look at the examples, you'd know it anyway. Try to solve it for a BST. It actually is fun to try to find a way to do it in O(n)

- iroodaz April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<cstdlib>
#include<stack>
#include<climits>

using namespace std;

struct Tree
{
    int value;
    Tree *left;
    Tree *right;

    Tree(int i)
    {
        value=i;
        left=NULL;
        right=NULL;
    }
};

void constructTree(Tree **node,int value)
{
    if((*node)==NULL)
    {
        *node = new Tree(value);
    }
    else if((*node)->value<value)
        constructTree(&((*node)->right),value);

    else
        constructTree(&((*node)->left),value);
}

void match(bool &flag, int val)
{
    static int num= INT_MIN;
    if(val>num)
    {
        num=val;
    }
    else
        flag=false;
}

bool binaryTree(Tree *node)
{
    bool flag=true;
    stack<Tree*> st;

    while((st.empty() || node)&&flag)
    {
        if(node!=NULL)
        {
            st.push(node);
            node=node->left;
        }
        else
        {
            node=st.top();
            st.pop();
            match(flag,node->value);
            node=node->right;
        }
    }

    return flag;
}

int main()
{
    int size;
    cin>>size;
    int a[size];
    for(int i=0;i<size;i++)
    {
        cin>>a[i];
    }

    Tree *root=new Tree(a[size-1]);

    for(int i=size-2;i>=0;i--)
    {
        constructTree(&root,*(a+i));
    }

    bool b = binaryTree(root);

    cout<<"out : "<<b;

    return EXIT_SUCCESS;
}

- Vishal October 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry i did a mistake

bool binaryTree(Tree *node)
{
    bool flag=true;
    stack<Tree*> st;

    while((st.empty() || node)&&flag)
    {
        if(node!=NULL)
        {
            st.push(node);
            node=node->left;
        }
        else
        {
            node=st.top();
            st.pop();
            match(flag,node->value);
            node=node->right;
        }
    }

    return flag;
}

- Vishal October 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

bool binaryTree(Tree *node)
{
    bool flag=true;
    stack<Tree*> st;

    while((!st.empty() || node)&&flag)
    {
        if(node!=NULL)
        {
            st.push(node);
            node=node->left;
        }
        else
        {
            node=st.top();
            st.pop();
            match(flag,node->value);
            node=node->right;
        }
    }

    return flag;
}

- Vishal October 09, 2014 | Flag


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