Amazon Interview Question
Software Engineer / DevelopersCountry: India
means dat u have two arrays ....u have to compare bst formed by both arrays whether dey r identical(value plus struct)
In this case, we do not need to construct the BST.
1. If both arrays' values and their ordering patterns with in each array is same, both arrays would construct similar BST. O(n).
2. If values are not identical but both arrays follows similar ordering pattern , structure will be same but not the values. ex: A1: 1,2,3 n A2: 4,5,6 or A1: 9,5,11 or A2: 3,1,4 ...structures of two BSTs in each example would be same but not the values.
I think question comes down to ensuring same size, similar values , and similar ordering pattern among values of each array.
Different Ordering pattern can also yield the same BST
e.g 3 , 1 , 6 and 3, 6, 1 would generate the same BST
different ordering patterns do not yield same bst to be same tree it is necessary to be same each branch i.e complete structure and data of each node so if two arrays are equal it will give same bst
{3, 1, 6} and {3, 6, 1} would yield the same trees. Both have 3 as the root and 1 and 6 as its children.
On the other hand, {3, 1, 6, 2} and {3, 6, 2, 1} would yield different trees. In the first one, 1 and 6 are children of 3, while 2 is right child of 1. In the second one, 6 and 2 are children of 3, while 1 is left child of 2.
hey...tell me whether dis algo is working or not....take one count variable for each array and traverse array...if in array succedng value is less than cur value do -1 if grtr do +1 aftr trvrsng both array chck deir count value if they r same dey form same bst...dis algo is to be applied when both arrays has similar values and same length
I think this approach would only compare the structure. But what about values?
3,1,6 & 3,2,7 both will give you same value!!!
hey..tell me whether dis algo will work or not...take one count variable for both arrays...now start trvrsng first array if next elemnt is less than current do count=count-1 else add 1...do same for second array...if both count value r same dey form same bst....dis one has to be done aftr chckng same value in both arrays,equal length and first elmnt is also equal....
//Convert array to BST and Compare
SortArray(int array[],int start , int end)
{
if(start >end)
return NULL;
mid = (start + end)/2;
BinaryTree *node = new BinaryTree(a[mid]);
node -> left = SortArray(a,start,mid-1);
node -> right = SortArray(a, mid+1, end);
return node;
}
isSame( BinaryTree *t1, Binary *t2)
{
if(t1 == NULL && t2 == NULL)
return TRUE;
else if(t1 != NULL && t2 != NULL)
{
return ( (t1->data == t2->data) && (isSame(t1->left,t2->left)) && (isSame(t1->right , t2->right)));
}
else
retrurn false;
}
int main()
{
BinaryTree *t1 = SortArray( a1,0,n-1);
BinaryTree *t2 = SortArray( a2,0,n-1);
result = isSame(t1,t2);
}
print inorder traversal of both BST formed from the 2 unsorted arrays. comapare the 2 inorder traversal. In this case though 2 arrays structure are need not to be same . But then BST will be same . so BST will give the same inorder traversal .
Note :I am just sharing my ideas. I m not sure of this
Yes the order matters...
Fix the first element, take two temp array equal to the size of given aray.
In first array kerp adding elements that are greater than a(0) the first element and similarly keep adding elements lower than a(0) .
What this will do is maintain the order of elemnts on rhs and lhs of root.
Traverse the second array 'b' and check if b(0) = a(0) if they r equal then roots are same and then check if the order of elements of greatr nd smaller elements and the num itself is same.
If same then they make same bst.
Eg.
A is 10,2,4,6,11,12,13
B is 10,11,2,12,13,4,6
Wil give you same bst
Greater elements orderis 11,12,13
Smaller elements order is 2,4,6
Which is same in both arrays.
Time complxis O(n)
Space O(n)
Yes the order matters...
Fix the first element, take two temp array equal to the size of given aray.
In first array kerp adding elements that are greater than a(0) the first element and similarly keep adding elements lower than a(0) .
What this will do is maintain the order of elemnts on rhs and lhs of root.
Traverse the second array 'b' and check if b(0) = a(0) if they r equal then roots are same and then check if the order of elements of greatr nd smaller elements and the num itself is same.
If same then they make same bst.
Eg.
A is 10,2,4,6,11,12,13
B is 10,11,2,12,13,4,6
Wil give you same bst
Greater elements orderis 11,12,13
Smaller elements order is 2,4,6
Which is same in both arrays.
Time complxis O(n)
Space O(n)
For two arrays to generate same BST:
1. Root should be same
2. Relative order of all elements greater than root should be same
3. Relative order of all elements less than root should be same.
(and of course the elements should be same as well:))
Example:
Same BST :
6,2,7,8,5,1,3,9,10,4
6,7,8,2,5,9,1,10,3,4
(root same and relative order of elements less and greater than root same
7,8,9,10 & 2,5,1,3,4
)
For two arrays to generate same BST:
1. Root should be same
2. Relative order of all elements greater than root should be same
3. Relative order of all elements less than root should be same.
(and of course the elements should be same as well:))
Example:
Same BST :
6,2,7,8,5,1,3,9,10,4
6,7,8,2,5,9,1,10,3,4
(root same and relative order of elements less and greater than root same
7,8,9,10 & 2,5,1,3,4
)
This is O(n)
I just need to make list of element greater and less than root for both and then compare corresponding lists for equality!
not working.
10,2,18,20,17
Both form the same BST's. However,relative ordering of the elements greater than root are not same.
The general idea makes sense but it would give wrong answer if we only consider the relative order of element greater/less than root...
e.g. {10 12 13 11 4 2 6 } and {10 12 11 13 4 6 2} would construct the same BST, but the relative order is different...
To make this right, we should not only consider the root, but each element as well, but it would be O(n^2)....
Can we do,
take increasing sequence from root and monotonic decreasing sequence from root and compare.
After comparing number of elements and all elements are same.
e.g. {10 12 13 11 4 2 6 } and {10 12 11 13 4 6 2}
from 1st array 10,12,13 from second 10,12,13
decreasing 10 4 2 and 10 ,4,2
?
use 2 variables - l and r. The 'l' variable should always contain the greatest value from the left subtree - Initially, the first element smaller than the root and set another variable lvalue=1. While traversing the array,first compare with the root value, if it is lesser, then if it is lesser than 'l', decrement 'lvalue'. If it is greater, increment 'lvalue' and assign the current value to 'l'.
In the same run if any element is greater than root, compare with 'r' value -if lesser decrement 'rvalue' else increment 'rvalue' and assign 'r' the current element.
Do this for the second array. if the 'rvalue' and 'lvalue' of the two arrays are same, they will have the same structure, else will be different.
Working code for java.
Algorithm as given by words&Lyrics
ackage ds.impl;
import java.util.*;
public class TwoUnsortedArrayBST {
/**
* @param args
*/
public static void main(String[] args) {
int[] a={6,2,5,1,3,4,7,8,9,10};
int[] b={6,7,8,9,10,2,5,1,3,4};
System.out.println("Same BST :"+checkSameBST(a, b));
}
public static boolean checkSameBST(int[] a , int[] b){
Queue minA=new LinkedList();
Queue maxA=new LinkedList();
Queue minB=new LinkedList();
Queue maxB=new LinkedList();
if(a[0]!=b[0]){
System.out.println("root not same");
return false;
}
else if(a.length!=b.length){
System.out.println("length not same");
return false;
}
else{
for(int i=1;i<a.length;i++){
if(a[i]>a[0] && b[i]>b[0] && a[1]!=b[i]){
System.out.println("maxa and maxb not same");
return false;
}
else{
maxA.offer(a[i]);
maxB.offer(b[i]);
}
if(a[i]<a[0] && b[i]<b[0] && a[1]!=b[i]){
System.out.println("mina and minb are not same");
return false;
}
else{
minA.offer(a[i]);
minB.offer(b[i]);
}
if(a[i]>a[0] && b[i]<b[0]){
if(maxB.isEmpty())
maxA.offer(a[i]);
else{
if((Integer)maxB.peek()==a[i]){
maxB.remove();
continue;
}
else{
System.out.println("checking "+(Integer)maxB.peek()+" and "+a[i]);
return false;
}
}
if(minA.isEmpty())
minB.offer(b[i]);
else{
if((Integer)minA.peek()==b[i]){
minA.remove();
continue;
}
else{
System.out.println("checking "+(Integer)minA.peek()+" and "+b[i]);
return false;
}
}
}
if(a[i]<a[0] && b[i]>b[0]){
if(maxA.isEmpty())
maxB.offer(a[i]);
else{
if((Integer)maxA.peek()==a[i]){
maxA.remove();
continue;
}
else{
System.out.println("checking "+(Integer)maxA.peek()+" and "+a[i]);
return false;
}
}
if(minB.isEmpty())
minA.offer(b[i]);
else{
if((Integer)minB.peek()==b[i]){
minB.remove();
continue;
}
else{
System.out.println("checking "+(Integer)minB.peek()+" and "+b[i]);
return false;
}
}
}
}
return true;
}
}
}
BST of given sorted array means it becomes sorted.
Do BFS on both the trees. Improvise BFS to do it in O(n)!!
XOR all of them .. complexity o(n) .. (condition - BST have unique numbers )
if result is 0 - then formed from same array.
Also, for a given array with/without duplicates, its BST will still be the same because duplicates won't be inserted twice. Hence XORing will give a wrong picture in case array has duplicates.
BST anyways can't have duplicates.
For two arrays to generate same BST:
1. Root should be same
2. Relative order of all elements greater than root should be same
3. Relative order of all elements less than root should be same.
(and of course the elements should be same as well:))
Example:
Same BST :
6,2,7,8,5,1,3,9,10,4
6,7,8,2,5,9,1,10,3,4
(root same and relative order of elements less and greater than root same
7,8,9,10 & 2,5,1,3,4
)
construction of BST would take nLogn time, given that both has same no of elements
- Ashupriya June 30, 2012so On is difficult to achieve, though there are certain checks that we can impose to quit early
[1] if the length of the two arrays are different then they can not be identical
[2] Construction of BST mostly depends on the order of the elements they come (unsorted)
keep track of the height of each tree (since we are not building height balanced tree) if the height of tree with same no of elements inserted then its unlikely that they will be same later
by the way did you happen to aswer it in On time? or the interviewer was emphasizing to be in On