Vizury Interview Question
Software Engineer / DevelopersThe above suggest method doesnot work for the following condition
A: 8,3,6,1,4,7,10,14,13
B: 8,10,14,3,6,4,1,7,13
A left : 3,6,1,4,7
A right : 10,14,13
b left : 3,6,4,1 ,7
B right : 10,14,13
A left != B left
according to condition this should not for BST
which is wrong
The above suggest method doesnot work for the following condition
A: 8,3,6,1,4,7,10,14,13
B: 8,10,14,3,6,4,1,7,13
A left : 3,6,1,4,7
A right : 10,14,13
b left : 3,6,4,1 ,7
B right : 10,14,13
A left != B left
according to condition this should not for BST
which is wrong
The above suggest method doesnot work for the following condition
A: 8,3,6,1,4,7,10,14,13
B: 8,10,14,3,6,4,1,7,13
A left : 3,6,1,4,7
A right : 10,14,13
b left : 3,6,4,1 ,7
B right : 10,14,13
A left != B left
according to condition this should not for BST
which is wrong
Vipuls method will work with slight modification,
Instead of being arrays being identical, they should form identical BST. And to test that, same function can be called recursively.
Let my try a psudocode.
check_identical(Array A, Array B){
if(A[0] != B[0]) {
return false;
}
if(A.size()!=B.size()){
return false;
}
if(A.size()==1){
return true; //only one elem in array and thats same in both
}
split(A, A_left, A_right);
split(B, B_left, B_right);
return check_identical(A_left, B_left)
&&
check_identical(A_right, B_right);
}
@DNS, thanx for pointing out the mistake. I didn't check for enough test cases.
@Old Monk, I think your solution will work fine.
@Vipul
If u sort ur left and right arrays before comaprision with second Array ur solution will work fine ut then complexity will change in worst case to (n-1)log(n-1) i.e. nlogn..
Old Monk solution doesnt work to me.coz what if elements in right array are in this orer
A_Right 15 25 30
B_Right 30 15 25
I think his method will return false while answer shud br true
wht abt this
f any one of the following conditions are false, then the BSTs are not identical else they are identical.
1: The first element of both arrays are same.
2: The relative ordering of all elements greater than the first element(root) is same in both the arrays.
3: The relative ordering of all elements lesser than the first element(root) is same in both the arrays.
Time Complexity O(n)
Space Complexity O(1)
@vipul
The above suggest method doesnot work for the following condition
A: 8,3,6,1,4,7,10,14,13
B: 8,10,14,3,6,4,1,7,13
A left : 3,6,1,4,7
A right : 10,14,13
b left : 3,6,4,1 ,7
B right : 10,14,13
A left != B left
according to condition this should not for BST
which is wrong
this logic will work great for all the test cases if u take it a bit further
A: 8,3,6,1,4,7,10,14,13
B: 8,10,14,3,6,4,1,7,13
A left : 3,6,1,4,7
A right : 10,14,13
b left : 3,6,4,1 ,7
B right : 10,14,13
While(aleft<=3&&aright<=3 )
if(aleft ==3) // do the same for aright==3
{compare a left and bleft
if not = then NOT BST
}
If(A left >3!! A right > 3)
A left : 1
A right : 6,4,7
similarly for B
b left :1
b right: 6,4,7
Wht abt this
f any one of the following conditions are false, then the BSTs are not identical else they are identical.
1: The first element of both arrays are same.
2: The relative ordering of all elements greater than the first element(root) is same in both the arrays.
3: The relative ordering of all elements lesser than the first element(root) is same in both the arrays.
Time Complexity O(n)
Space Complexity O(1)
It's simple and can be done in O(n).
Create from first array a BST say aBST..
Once done when you are trying to create second BST, say bBST compare the value of the node (being inserted) with the aBST current node value, if equal insert it and move down else return false and you are done.
i thot of a similar approach but with a twist:
1. Create a BST with first input list say aBST, but each node should have an extra bool variable (say IsReached) set to false.
2. Now, start with the first element in second input list. The first element has to be the same as the root node of aBST, (otherwise we are done already), mark it as IsReached = true and goto step 3.
3. for each subsequent element in second input list, do a search in aBST. But condition is that you can test search only till the immediate children of any node where IsReached = true. If found, set the isReached flag = 1 & move on. Otherwise conclude & exit.
howzat?
This will do
static boolean preorder(Node r1, Node r2){
if( r1.l == null && r1.r == null && r2.l == null && r2.r == null)
return r1.d == r2.d;
else if(
(r1.l == null && r2.l != null) || (r1.r == null && r2.r != null) ||
(r1.l != null && r2.l == null) || (r1.r != null && r2.r == null ))
return false;
else
return preorder(r1.l, r2.l) && r1.d == r2.d && preorder(r1.r, r2.r);
}
what about this
for (int i = 0; i < length - 1; i++)
{
if (arr1[i] < arr1[i+1] && arr2[i] < arr2[i+1])
return false;
if (arr1[i] > arr1[i+1] && arr2[i] > arr2[i+1])
return false;
}
return true;
take first element as pivot of the quick sort.
for both the arrays position this element such that left elements are all smaller and right elements are all bigger.
Now compare the array: if they are equal then same BST else not.
eg:
1) Array1:10 5 20 15 30
Array2:10 20 15 30 5
after processing
Array1: 5 10 20 15 30
Array2: 5 10 20 15 30
Result: True
Array1:10 5 20 15 30
Array2:10 15 20 30 5
after processing
Array1: 5 10 20 15 30
Array1: 5 10 15 20 30
Result: false
Comments people. If this approach is correct
I think We can do it by using the array splitting in two part. one is smaller then first nbr and one is bigger the first nbr and seq should not be break for ex: (first element is common as it is root so ignore it)
array A = 57926813
then make two array from it 213 and 7968
Array B = 52713968
then make two array from it 213 and 7968
here both array are same so tree should be ideantical..
If any one of the following conditions are false, then the BSTs are not identical else they are identical.
1: The first element of both arrays are same.
2: The relative ordering of all elements greater than the first element(root) is same in both the arrays.
3: The relative ordering of all elements lesser than the first element(root) is same in both the arrays.
Time Complexity O(n)
Space Complexity O(1)
For the two arrays to give same BST, the two arrays should contain the same elements. (much like anagrams).
sort the two and compare O(n lg n)
I hope their is a better solution to check for anagrams..
Probably he didn't understand "equality" here. Two BSTs have to be identical (not just containing the same elements).
Divide the elements(except the root) of each array into two sets-one that contains the elements that come in the left sub-tree in the order in which they occur in the array and the other that contains the elements that come in the right sub-tree again in the order in which they occur in the array.
Make left and right arrays for both the arrays. Then the left arrays of both as well as the right arrays of both should be exactly same.
For example:
Array1:10 5 20 15 30
Array2:10 20 15 30 5
left1 : 5
right1 : 20 15 30
left2 : 5
right2 : 20 15 30
therefore the arrays would produce the same BSTs
But for:
Array1:10 5 20 15 30
Array2:10 15 20 30 5
left1 : 5
right1 : 20 15 30
left2 : 5
right2 : 15 20 30
As right1 and right2 are not same, therefore different BSTs are produced.
Here is the code:
- Vipul June 16, 2011