VMWare Inc Interview Question
InternsCountry: Armenia
Interview Type: In-Person
Please correct me if I am wrong. This is to create a BST.
1) Here we calculate the pivot using the partition function:
This will split the array into 2 sub-arrays
public static int partition(int[] a, int l, int r)
{
int m=(l+r)/2;
swap(a,l,m);
int pivot=a[l];
int low=l+1;
int high=r;
while(low<=high)
{
while(a[high]>pivot)
high--;
while(low<=high && a[low]<pivot)
low++;
if(low<=high)
{
swap(a,low,high);
low++;high--;
}
}swap(a,l,high);
System.out.println("Here the partition is: "+a[high]);
return high;
}
This function should return the root in the 1st case and the node in the later iterations.
2) Now the quicksort on the subarrays leads to further partitions which will be nodes.
The lower subarray will be the left subtree and the higher would be the right subtree.
quickSort(a,p,q);//left subtree
quickSort(a,q+1,r);//right rightsubtree
add all aliment into RBtree which will converter unsorted array into balanced BST. Complexity: nlogn
void RB_BST::insert(int d){
if(!root) {
node *tmp = new node(d,NULL,NULL,false);
root = tmp;
} else {
root = insertInt(root,d);
}
}
RB_BST::node* RB_BST::insertInt(node*p, int d) {
if(d < p->data) {
if(p->left) {
p->left = insertInt(p->left,d);
} else {
p->left = new node(d,NULL,NULL,true);
}
} else if(d > p->data) {
if(p->right) {
p->right = insertInt(p->right,d);
} else {
p->right = new node(d,NULL,NULL,true);
}
} else {
cout << "duplicate data"<<endl;
}
if(p->right && p->right->isRed == true) {
p = leftRotate(p);
}
if(p->left && p->left->isRed == true && p->left->left && p->left->left->isRed) {
p = rightRotate(p);
}
if(p->left && p->left->isRed == true && p->right && p->right->isRed == true) {
flipLink(p);
}
return p;
}
This can be done in O(n) time and O(n) space. Basically this is a classic example of level order traversal.
Alogithm:
1. Create the root element and insert into a queue
2. Loop throw the queue
3. Remove first element from the queue and create its both children and insert both children into the queue.
4. Repeat the step 3 until you have processed the whole array. This will create a Balanced binary tree.
=========================
There is one more algorithm to do it in O(n) time and O(1) space.
See this link.
http://www.geeksforgeeks.org/sorted-array-to-balanced-bst/
Here if array is not sorted then it will create a non BST
/* A function that constructs Balanced Binary Search Tree from a sorted array */
struct TNode* sortedArrayToBST(int arr[], int start, int end)
{
/* Base Case */
if (start > end)
return NULL;
/* Get the middle element and make it root */
int mid = (start + end)/2;
struct TNode *root = newNode(arr[mid]);
/* Recursively construct the left subtree and make it
left child of root */
root->left = sortedArrayToBST(arr, start, mid-1);
/* Recursively construct the right subtree and make it
right child of root */
root->right = sortedArrayToBST(arr, mid+1, end);
return root;
}
Use a recursive approach to achieve a linear logarithmic complexity. Let's see this in action:
/* Create a wrapper function*/
TreeNode createBalancedTree(int[] array) {
return createBalancedTree(array, 0, array.length - 1);
}
/* Recursive function*/
TreeNode createBalancedTree(int[] array, int min, int max) {
if (max < min) return null;
int mid = (min + max) / 2;
TreeNode node = TreeNode(array[mid]);
node.setLeftChild(createBalancedTree(array, min, mid - 1));
node.setRightChild(createBalancedTree(array, mid + 1, max));
return node;
}
PS: This also create a balanced binary search tree, so we kill 2 birds with a stone.
To use this function simply create an array as below:
int[] array = {1, 4, 2, 5, 3};
TreeNode node = createBalancedTree(array);
Won't work at all
First of all the code u provided doesn't even make bst let alone BTREE
Mistake with the code for BST->
Taking ur input 1,4,2,5,3
starts with root as 1
sets left of root as a subtree which has child from the same array with index from(0,1)
Recursively again it goes on to create child of this subtree as another subtree whose left will be from index(0,-1) where u return so right will be 4
it is something like
So left of 1 has 4 which is incorrect,because it will be something like right of left of 1 is 4 which is wrong
@Gaurav, you are mistaken, although you were close to identifying the position of 4.
Firstly the root will be 2: my code logic sets the root to the mid of the array and then slices left and right of the array until we have completely exhausted the contents of the array {1, 4, 2, 5, 3}
This is what I mean:
int mid = (start + end) / 2;
TreeNode n = new TreeNode(arr[mid]);
So there is no WAY, the value 1 will be the root of the tree.
Yes 4 will be in the right position of 1 - which is correct, and the formed tree is valid according to the definition of a balanced tree. A balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.
Here is the tree I formed based on my logic:
/* The final tree output */
2
/ \
1 5
\ \
4 3
So the tree is clearly balanced ;)
Happy Holidays!!!
PS: @Gaurav, I can send you a link to download my entire source code so that you can run tests on the logic in your desired IDE. Recursion can be a challenge to comprehend without seeing it in action. Let me know man. Cheers.
How can this algo be logorithic? you have to set node for every single element of the array. Unlike binary search which skips every half of the array, this algo have to do for both left and right
@guest, most certainly. I just realized I omitted the linear as part of my sentence. I updated my response. It's a linear logarithmic complexity O(N log N). That said, we can achieve a balanced tree using this approach.
Not possible. Have to visit each element.
- Anonymous December 18, 2013