Calling Base Class Virtual Method using Derived class object

Below are couple of ways to achieve calling a base class virtual method using  derived class object
  
Implementation 1

 #include<iostream>
using namespace std;
class Base
{
      public:
             virtual void Check()
             {
                     cout<<"Calling Base";
             }
};
class Derived:public Base
{
      public:
             void Check()
             {
                    cout<<"Calling Derived";
             }
};
int main()
{
    Derived d;
    d.Base::Check(); // Qualified Id
     return 0;
   
}

Implementation 2

#include<iostream>
using namespace std;
class Base
{
      public:
             virtual void Check()
             {
                     cout<<"Calling Base";
             }
};
class Derived:public Base
{
      public:
             void Check()
             {
                  Base::Check();
              }
};
int main()
{
    Derived d;
    d.Check();
    return 0;
   
}
 

Output (in both 1 and 2):
Calling Base

Please comment if you find anything incorrect.

String is Palindrome or not using Recursion

We know iterative ways to find out whether string is palindrome or not but here i will be discussing the recursive way.

Algorithm

1. Transform the string to lower case to cater cases like Nitin.
2. Then traverse the string from start and end using recursion till start is less than end.   

Input      : a string 
Output   : String is (not) Palindrome

Implementation

#include<iostream>
#include<string>
using namespace std;
bool Palindrome(string s, int start,int end)
{
     if(start>end)
           return true;
     else if(s[start]==s[end])
     {
           return Palindrome(s,++start,--end);
     }
     else
           return false;
        
     
}
int main()
{
    string s;
    cin>>s;

  //Converting the string to lower case

    transform(s.begin(),s.end(),s.begin(),::tolower);

    if(Palindrome(s,0,s.length()-1))
       cout<<"String is Palindrome";
    else
       cout<<"String is not Palindrome";
      
    getchar();
    return 0;    
   
}
 

Please comment if you find anything incorrect

                                                                               

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.