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.

- angshu1986 May 03, 2015 | Flag Reply
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

- Vib May 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- parvin.singh October 26, 2015 | Flag
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

- sanjaybangalore.gns April 16, 2015 | Flag Reply
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

- pc May 26, 2015 | Flag Reply
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.

- haristech03 December 06, 2016 | Flag Reply
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)

- guilhebl April 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- angshu1986 April 21, 2015 | Flag
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

- Vib April 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- angshu1986 April 21, 2015 | 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