Nice Articles

1. http://bjorn.tipling.com/if-programming-languages-were-weapons
2. http://www.infoworld.com/article/2833714/c-plus-plus/snowman-seeks-to-be-llvm-for-decompilers.html

To Do Programs

1. Find and List all files and folders in a directory.

Reverse Level Order Traversal of a Tree

One of the many ways of representing a tree is to have an array(of length same as number of nodes), where each element in the node denotes the parent of that node.
Eg –
{-1, 0, 0, 1, 1} would represent a tree with –

1.  0 as root
2.  1 and 2 as children of 0
3.  3 and 4 as children of 1

Given a similar representation, you have to print reverse level order traversal of the corresponding tree.
Level order traversal of a tree is where we traverse levels of tree one by one.

Eg –
For the above given tree, level order traversal would be –
0
1 2
3 4
And hence, the reverse level order traversal is –
3 4
1 2
0

Note 

1. An element with parent = -1 is the root element.
2. An element with the least index becomes the left most child. (ie. a node with always be on left of all its siblings that have higher index than it)
3. When printing a level of tree you need to maintain left to right order.

Implementation

#include <iostream>
#include<map>
using namespace std;
struct node
{
    node *left;
    node *right;
    int data;
};
node *NewNode ( int val )
{
    node * newNode=new node;
    newNode->left=NULL;
    newNode->right=NULL;
    newNode->data=val;
    return newNode;
}
void FindChildren ( int child[],map<int,int> tree,int parent )
{
    int count = 0;
    for ( int i=0; i< tree.size(); i++ )
    {   if ( tree[i] == parent )
        {
            child[count] = i;
            count++;
        }
    }
}
void CreateSubTree ( node *root,map<int,int> tree )
{
    int child[2] = {-1, -1};
    FindChildren ( child, tree, root->data );

    if ( child[0] != -1 )
    {
        node* temp = NewNode ( child[0] );
        root->left = temp;
        CreateSubTree ( temp, tree );
    }

    FindChildren ( child, tree, root->data );

    if ( child[1] != -1 )
    {
        node* temp = NewNode ( child[1] );
        root->right = temp;
        CreateSubTree ( temp, tree );
    }

}
int TreeHeight ( node *root )
{
    if ( root==NULL ) {
        return 0;
    }
    else
    {
        int leftHeight=TreeHeight ( root->left );
        int rightHeight=TreeHeight ( root->right );
        if ( leftHeight>rightHeight ) {
            return leftHeight+1;
        }
        else {
            return rightHeight+1;
        }
    }

}
void PrintReversal ( node *root,int level )
{
    if ( root==NULL ) {
        return ;
    }
    if ( level==1 )
    {
        cout<<root->data<<" ";
    }
    else
        if ( level>1 )
        {
            PrintReversal ( root->left,level-1 );
            PrintReversal ( root->right,level-1 );

        }

}
void ReverseOrderTraversal ( node *root )
{
    int height=TreeHeight ( root );
    for ( int i=height; i>=1; i-- )
    {
        PrintReversal ( root,i );
        cout<<"\n";
    }

}
int main()
{

    int num,root;
    map<int,int> tree;
    cin>>num;
    int *treeArray=new int[num];

    for ( int i=0; i<num; i++ )
    {
        cin>>treeArray[i];
        tree[i]=treeArray[i];
        if ( treeArray[i]==-1 )
        {
            root=i;
        }
    }
    node *parent=NewNode ( root );
    CreateSubTree ( parent,tree );
    ReverseOrderTraversal ( parent );
    return 0;

}

Please comment if you find anything incorrect

General Algorithms

1. Given an array of n numbers having elements from 1 to n with one number missing. Find the missing number                                                                                                                    Algorithm 1

   1. Get the sum of numbers 
          total = n*(n+1)/2
   2  Subtract all the numbers from sum and
      you will get the missing number.

   Algorithm 2 

   1) XOR all the array elements, let the result of XOR be X1.
   2) XOR all numbers from 1 to n, let XOR be X2.
   3) XOR of X1 and X2 gives the missing number. 

2. Euclid’s Algorithm                                                            int GCD(int A, int B) { if(B==0) return A;                                                           else return GCD(B, A % B); }                                                                                                                                       

Reverse a string without modifying original string

Reverse a string without editing original string and no extra space and swap functions
Algorithm

1. Use recursion to keep moving till end of string.
2. Display data in each index of string 

Input    : string s  (Eg : rev me )
Output : Reverse of s (Eg: em ver )


Implementation

#include <iostream>
#include <string>
using namespace std;
void Reverse ( const char * s )
{
    if ( *s )
    {
        Reverse ( s+1 ) ;
        cout<<*s;
    }
}
int main()
{
    string s;
    getline ( cin,s );
    const char *p= s.c_str();
    Reverse ( p );
    getchar();

}

Please comment if you find anything incorrect.

Find Second Largest element in an array

Algorithm:

1. Initialize max to first element of array and secondMax as INT_MIN
2. Loop through all the elements.
   a. If the current element is greater than max, then update max
       and secondMax. 
   b. Else if the current element is greater than secondMax then update 
    secondMax

 Input    : Array of n elements

Output : Second Largest Element

Implementation 

#include <iostream>
#include<string>
#include <cmath>
using namespace std;
int SecondMax ( int *a,int n )
{
    int max=a[0],secondMax=INT_MIN;
    for ( int k=1; k<n; k++ )
    {
        if ( a[k]>max )
        {
            secondMax=max;
            max=a[k];

        }
        else
            if ( a[k]>secondMax&& a[k]<max )
            {
                secondMax=a[k];
            }
    }
    return secondMax;
}
int main()
{
    int n,*a;
    cin>>n;
    a=new int[n];

    for ( int i=0; i<n; i++ )
    {
        cin>>a[i];
    }
    if ( n<=2 )
    {
        cout<<" Enter valid Input";
    }
    else
    {
        if ( SecondMax ( a,n ) == INT_MIN )
        {
            cout<<"Second Max element does not exist";
        }
        else
        {
            cout<<SecondMax ( a,n );
        }
    }
    delete a;
    getchar();
} 

Please comment if you find anything incorrect. 

Given number is a power of 2 or not

To check whether a given number is power of 2 or not

Algorithm
To check whether a given number, n  is power of 2 or not we do bit AND of n and n-1. It will be zero if number is power of 2. 
Eg: if n is 16 (10000) and n-1 is 15(01111), then n&n-1 is 0. Bit NOT of zero is 1. 
Logical AND of n and 1 will be 1. We cant just use ! ( n&n-1 )because for n=0, it will 1. But 0 is not power of 2.

Input:       number.

Output:    n is (not)power of 2

#include <iostream>
using namespace std;
int PowerOfTwo ( int n )
{
    return ( n &&! ( n&n-1 ) );
}
int main()
{
    int n;
    cin>>n;
    if ( PowerOfTwo ( n ) )
    {
        cout<<n<<" is power of 2";
    }
    else {
        cout<<n<<" is not power of 2";
    }
    return 0;
}

Please comment if you find anything incorrect