## Symantec Interview Question for Java Developers

Country: India

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

I came up with this approach without extra space:
1. take the first element, arr[0], as root.
2. For i=0 to length of array
i. find i where arr[i] > arr[0].
3. Split up arr into two sub arrays, 1 to (i-1) and i to length, the first being the left tree of root and the second the right tree.
4. Check if any element in second sub array has a value less than arr[0]. If found, return false indicating the tree cannot be formed.
5. Recursively call 1 to 4 for the two sub arrays.

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

4.2 also check the left array for greater value. if found return false

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

it seems here we are trying to read the input as a pre-order traversal of a binary search tree. This is not mentioned in the original question ?

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

I use stack here
algo
buff[k]
k=0;
push(a[0])
i=1;
while ( end of array a[]) {
if(a[i]<top()) ;
push(a[i]);
else {
//maintain lowest element in top of the stack
while(a[i]>(buff[k++]=pop()));
push(a[i]);
}
}
complexity -> o(n)
finally if the array buff[] is sorted then its a preorder representation of BST

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

This problem can be solved recursively as mentioned by Anqshu
Essentially Preorder traversal of a tree looks something like this

Root {PreOder of Left Tree} {PreOrder Of Right Sub Tree}
Find the index of Right Sub tree using number immediate > then root.
And then recursively find preorder traversal of left and right tree

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

For each element X in array,
Find the next element Y which is greater than X. Once in the array if we reach Y there should not be any element greater than X.
If this is true for all X then it is a BST.

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

1. get the middle element of the array (mid element should be root),
2. partition left side and right side to new arrays aLeft and aRight,
from 0 - mid , mid + 1 - array.length
each array will represent a subtree of root, with their mid elements representing the root's left child (mid of aLeft) and right child (mid of aRight).
3. Call the function recursively until you reach an array size of 1. These will be the leaf elements

* If you wish to check if this is a balanced binary tree and elements are sorted properly, just check left child and right child while dividing the array using the rule:
if (ROOT > ROOT.LEFT && ROOT < ROOT.RIGHT)

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

In pre order, the first element is always the root.

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

Is it BT or BST, if it is BST, construction is as follows

1. make the first element as root
2. find index i where a[i] > a[0]
3. root->left = constructTree with nodes less than i
4. root->right = constructTree with nodes from i+1

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

It is a BST. IBut the question was to validate the array and not create the tree. Bit confused here.

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.