Given a array of size 'n' with 0's and 1's as its elements, sort the array in ascending order

Its cool problem.

Method 1)

Count the number of 1's (ones) in the array , say k.
Then simply set last k elements to 1 and n-k elements to 0(zero).
(other way is count 0's)


Its takes total (n+ n = 2n) = O(N) time.


Method 2)

f = 0;
l = n -1;
for ( ; f < l; ) {
if(arr[f]) {
if(!arr[l]) {
arr[f++]=0;
arr[l]=1;
}
l--;
} else {
arr[l] && l--;
f++;
}
}




Let me know which is better ?? And if there is any better approach..

Fun With Programming Puzzles

1) check if a given binary tree is a binary search tree or not?

What most of the people do when they are writing this algo is they only take care one criteria LeftChild < Parent < RightChild. Does this alone criteria is enough to say its binary search tree ? Its not true for all the trees. Just think for a while why so? Still if you are thinking yes then what about the below tree ?


---------------10
----------------|
--------8------|-------12
-------- |------ --------|
----6---|---11____9--|----14


Its a binary tree but not BST(Binary Search Tree). Actual criteria should be LeftChildTree < parent < RightChildTree

Algo 1)

int isThisABST(struct node* mynode) {
if (mynode==NULL) return(true);

if (node->left!=NULL && maxValue(mynode->left) > mynode->data)
return(false);
if (node->right!=NULL && minValue(mynode->right) <= mynode->data)
return(false);

if (!isThisABST(node->left) || !isThisABST(node->right))
return(false);
return(true);

}

This consumes lot of time. Each time calculating maxValue and minValue is time consuming.



Algo 2)

This algo will use same criteria in a different way. The above criteria is means same as BST inorder travarsal is sorted.
So while doing inorder travarsal we can store the printing value and compare with the previusly printed value. If prev printed value is greater than present one then its not a BST.

int isThisABST(struct node* mynode)
{
struct node *prev_print_node = NULL;

return(isThisABST_internal(mynode, &prev_print_node));
}

static int isThisABST_internal(struct node *mynode, struct node **prev_print_node)
{

if (mynode)
{
if (false == isThisABST_internal(mynode->left))
return(false);
if ((*prev_print_node) && ((*prev_print_node)->data > mynode->data))
return(false);

*prev_print_node = mynode;
if (false == isThisABST_internal(mynode->right))
return(false);
}
return (true);
}