C++ Unit Testing Frameworks Comparison

Below are the comparison of 3 commonly used C++ testing frameworks i.e CPPUnit , Google Test and Boost Test.

Please comment if you find anything incorrect

Do You know?

• GOOGLE :: "Global Organization Of Oriented Group Language Of Earth".
• YAHOO :: Yet Another Hierarchical Officious Oracle. 
• GREP  :: General Regular Expression Parser.
• DCOM :: Distributed Component Object Model

Sum of 4 number in a Array equal to a given number

Print combination of 4 numbers which is equal to a given number (say total).

Algorithm:

• Sort the array
• Loop in array assuming first 2 elements(index i,k) are part of valid combination and than finding other 2 elements(index l,r) in array ,a whose sum is equal to total- a[i]-a[k].
• Loop while l < r.
         (a) If (A[l] + A[r] == remaning sum)  then print & l++,r--                                        (b) Else if( A[l] + A[r] <  remaining sum )  then l++
         (c) Else r--
• Do Step 2 and 3 taking other combinations of 2 elements

Implementation

 #include<stdio.h>  
 #include<string.h>  
 #include<iostream>  
 #include<algorithm>  
 using namespace std;  
 void ValidCombo(int n,int a[],int sum)  
 {  
   int temp,flag=0;  
   string str;  
   sort(a,a+n);  
   for(int i=0;i<n;i++)  
   {  
     for(int k=i+1;k<n;k++)  
     {  
       temp= a[i]+a[k];  
       int l, r,count=0;  
       l = k+1;  
       r = n-1;  
       while(l < r)  
       {  
         if(a[l] + a[r] == sum-temp)  
         {  
           cout<<a[i]<<" "<<a[k]<<" "<<a[l]<<" "<<a[r]<<"\n";  
           flag=1;  
           l++;  
           r--;  
         }  
         else if(a[l] + a[r] < sum-temp)  
           l++;  
         else  
           r--;  
       }   
     }  
   }  
   if(flag==0)  
     cout<<"Valid Combination not Possible";  
 }  
 int main()  
 {  
   int n,total;  
   cin>>n;  
   int *a=new int[n];  
   for(int i=0;i<n;i++)  
     cin>>a[i];  
   cin>>total;  
   ValidCombo(n,a,total);  
   delete a;  
   return 0;  
 }  

Please comment if you find anything incorrect.

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.

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

Lowest Common Ancestor

#include<stdio.h>

struct Node
{
    int data;
    Node *left;
    Node *right;
};
int LCA ( Node* head,int n1,int n2 )
{
    if ( head==NULL )
    {
        return 0;
    }
    if ( head->data<n1 && head->data <n2 )
    {
        return LCA ( head->right, n1, n2 ) ;
    }
    if ( head->data>n1 && head->data >n2 )

    {
        return  LCA ( head->left, n1, n2 ) ;
    }
    return head->data;

}
struct Node* newNode ( int data )
{
    struct Node* node = new  Node ;
    node->data  = data;
    node->left  = node->right = NULL;
    return ( node );
}

int main()
{
 
    struct Node *root        = newNode ( 20 );
    root->left               = newNode ( 8 );
    root->right              = newNode ( 22 );
    root->left->left         = newNode ( 4 );
    root->left->right        = newNode ( 12 );
    root->left->right->left  = newNode ( 10 );
    root->left->right->right = newNode ( 14 );

    int n1 = 10, n2 = 14;

    printf ( "LCA of %d and %d is %d \n", n1, n2, LCA ( root, n1, n2 ) );

    n1 = 14, n2 = 8;
 
    printf ( "LCA of %d and %d is %d \n", n1, n2,LCA ( root, n1, n2 ) );

    n1 = 10, n2 = 22;
 
    printf ( "LCA of %d and %d is %d \n", n1, n2, LCA ( root, n1, n2 ) );

    getchar();
    return 0;
}

Find GCD using Euclidean Algorithm

#include<iostream>
using namespace std;

void GcdFinder ( int a,int b )

{

    while ( a!=b )
  {
        if ( a>b ) {
            a=a-b;
        }
        else {
            b=b-a;
        }

    }
    cout<<"GCD Of two numbers is "<<a<<endl;
}
int main()
{
    int a,b;
    cout<<"Enter two numbers\n";
    cin>>a>>b;
    GcdFinder ( a,b );
    getchar();
    return 0;
}

Reverse a Linked List

Reverse a given Linked List.

Implementation
 #include <iostream>
using namespace std;
struct Node
{
    int data;
    Node *next;
};
void Insert ( Node **head,int d )
{
    if ( head==NULL )
    {
        Node *newNode=new Node;
        newNode->data=d;
        newNode->next=NULL;
        *head=newNode;
    }
    else
    {
        Node *newNode=new Node;
        newNode->data=d;
        newNode->next=*head;
        *head = newNode;

    }
}
void Display ( Node *head )
{
    while ( head!=NULL )
    {
        if ( head->next!=NULL )
        {
            cout<<head->data<<"->";
        }
        else {
            cout<<head->data;
        }
        head=head->next;

    }
}

Node * ReverseLinkedList ( Node **head )
{
    Node *p,*q,*r;
    p=*head;
    q= ( *head )->next;
    p->next=NULL;
    while ( q!=NULL )
    {
        r=q->next;
        q->next=p;
        p=q;
        q=r;
    }
    *head=p;
    return *head;

}

int main()
{
    Node *head=NULL;
    Insert ( &head,5 );
    Insert ( &head,25 );
    Insert ( &head,35 );
    Insert ( &head,15 );
    Insert ( &head,20 );
    Insert ( &head,2 );
    Display ( head );
    ReverseLinkedList ( &head );
    cout<<"\n";
    Display ( head );
    getchar();

}

Please comment if you find anything incorrect.

Given a Sorted Linked List, Insert a new element in Sorted Way

Given a sorted Linked List, make sure new element is inserted in sorted way 

Algorithm Used 

1. If Linked list is empty then make the node as head and return it.
2. If value of the node to be inserted is smaller than or equal to value of head node then insert the node at start and make it head. 
3. In a loop, find the appropriate node after which the input data is to be inserted. To find the appropriate node start from head, keep moving until you reach a node who's value is greater than the input node.
4. Insert the node  after the appropriate node found in step 3.

For Example:

Below 15 is to be inserted in sorted linked list.

 

#include <iostream>
using namespace std;
struct Node
{
    Node * next;
    int data;
};
void Insert ( Node **start,int d )
{
    Node *cur;
    if ( ( *start ) ==NULL || ( *start )->data>=d )
    {
        Node *newNode=new Node;
        newNode->data=d;
        newNode->next=*start;
        ( *start ) =newNode;

    }
    else
    {
        cur=*start;
        while ( cur->next!=NULL&& ( cur )->next->data<=d )
        {
            cur= ( cur )->next;

        }
        Node *newNode=new Node;
        newNode->data=d;
        newNode->next= cur->next;
        cur->next= newNode;


    }
}
void Display ( Node *start )
{
    while ( start!=NULL )
    {
        if ( start->next!=NULL ) {
            cout<<start->data<<"->";
        }
        else {
            cout<<start->data;
        }

        start=start->next;
    }
}

int main()
{
    Node *start=NULL;
    Insert ( &start,35 );
    Insert ( &start,20 );
    Insert ( &start,10 );
    Insert ( &start,25 );
    Insert ( &start,15 );
    Display ( start );
    getchar();

}

Please comment if you find anything incorrect.

Reference:

1. http://www.geeksforgeeks.org/given-a-linked-list-which-is-sorted-how-will-you-insert-in-sorted-way/

Round off a floating point number to nearest integer

Given a floating point number , convert it nearest integer. 

Approach
Check if floating number is positive, add 0.5 to it otherwise subtract 0.5. For Example if input is -6.8 output will be  -7 , if input is 7.5 output will be 8
Input:       A floating point number.

Output:    Nearest integer

#include <iostream>

using namespace std;
int round_float ( float r )
{
    return ( r > 0.0 ) ? ( r + 0.5 ) : ( r - 0.5 );
}
int main()
{
    float f;
    cin>>f;
    cout<<round_float ( f );
    getchar();

}

Please comment if you find anything incorrect or have any other inputs

Count Number of bits to be flipped to convert one integer to another

One of the approaches to solve this problem is to simultaneously go through bits of two integers and updating the count of bits that are different but better way is to solve it using XOR functionality.

Approach

• XOR both integers
• Count the number of set bits in resultant integer
  

For Eg : 40 in binary is 101000 and 61 is 111101 , then number of bit swap required is 3
Input   :Two integers
Output: Number of bits to be flipped

#include <iostream>
int main()
{
    int firstInteger,secondInteger,res,flip=0;
    std::cin>>firstInteger>>secondInteger;
    res=firstInteger^secondInteger;
    while ( res>0 )
    {
        if ( res&1==1 )
        {
   flip++;
  }
  res >>=1;
    }
 std::cout<<flip;
 getchar();

}



Please comment if you find anything incorrect.

Just for Knowledge

1. A thin client (sometimes also called a lean, zero or slim client) is a computer or a computer program that depends heavily on some other computer (its server) to fulfill its computational roles
2. Thin clients occur as components of a broader computer infrastructure, where many clients share their computations with the same server. As such, thin client infrastructures can be viewed as providing some computing service via several user interfaces. This is desirable in contexts where individual fat clients have much more functionality or power than the infrastructure requires.
3. A fat client  is a computer designed to take on these roles by itself. 
4. Total number of possible Binary Search Trees with n different keys = Catalan number Cn = (2n)!/(n+1)!*n!
5. A number is Fibonacci if and only if one or both of (5*n² + 4) or (5*n² – 4) is a perfect square.
6. Bi-endian processors can run in both modes little and big endian.
7. Intel based processors are little endians. ARM processors were little endians. Current generation ARM processors are bi-endian. Motorola 68K processors are big endians. PowerPC (by Motorola) and SPARK (by Sun) processors were big endian. Current version of these processors are bi-endians.
8. File formats which have 1 byte as a basic unit are independent of endianness e..g., ASCII files . Other file formats use some fixed endianness forrmat e.g, JPEG files are stored in big endian format.
9. Endianness matters in network programming: Suppose you write integers to file on a little endian machine and you transfer this file to a big endian machine. Unless there is little andian to big endian transformation, big endian machine will read the file in reverse order. You can find such a practical example here. Standard byte order for networks is big endian, also known as network byte order. Before transferring data on network, data is first converted to network byte order (big endian).
10. There are so many variants of Unix like Fedora Core , SUSE Linux etc. To standardize the Unix OS , IEEE has created a standard called Portable Operating System Interface(POSIX).  
     
     
    
     
      
    

Puzzle 1--- Fill the boxes from 1 to 8

You have to fill the boxes from 1 to  8 such that no two adjacent elements are closed to each other either horzintonally vertically or diagonally. Below are the constraints.

Not Possible

                                      




Possible

                                       



Solution                                         .
                                        

Find largest number obtained by changing the bits of a given number

For Example : 5 is represented in binary as 101 but the largest number can be 6(110)
Input   :A number n
Output: Largest number


#include <iostream>
#include <cmath>
using namespace std;
int FindLargest ( int n )
{
    int one=0,t=0,final=0;
    while ( n!=0 )
    {
        if ( n&1==1 )
        {
            one++;
            t++;
            n=n>>1;
        }
        else
        {
            t++;
            n=n>>1;
        }
    }
    for ( int i=t-1; i>=t-one; i-- )
    {
        final+=pow ( 2.0,i );
    }
    return final;
}
int main()
{
    int n;
    cin>>n;

    cout<<FindLargest ( n );

    getchar();

}

Please comment if you find anything incorrect.

Memory Leaks

1 Understand the operator basics. The C++ operator "new" allocates heap memory. The "delete" operator frees heap memory. For every "new," you should use a "delete" so that you free the same memory you allocated:

char* str = new char [30]; // Allocate 30 bytes to house a string.

delete [] str; // Clear those 30 bytes and make str point nowhere.

2 Reallocate memory only if you've deleted. In the code below, str acquires a new address with the second allocation. The first address is lost irretrievably, and so are the 30 bytes that it pointed to. Now they're impossible to free, and you have a memory leak:

char* str = new char [30]; // Give str a memory address.

// delete [] str; // Remove the first comment marking in this line to correct.

str = new char [60]; /* Give str another memory address with
                                                    the first one gone forever.*/

delete [] str; // This deletes the 60 bytes, not just the first 30.

3 Watch those pointer assignments. Every dynamic variable (allocated memory on the heap) needs to be associated with a pointer. When a dynamic variable becomes disassociated from its pointer(s), it becomes impossible to erase. Again, this results in a memory leak:

char* str1 = new char [30];

char* str2 = new char [40];

strcpy(str1, "Memory leak");

str2 = str1; // Bad! Now the 40 bytes are impossible to free.

delete [] str2; // This deletes the 30 bytes.

delete [] str1; // Possible access violation. What a disaster!

4. Be careful with local pointers. A pointer you declare in a function is allocated on the stack, but the dynamic variable it points to is allocated on the heap. If you don't delete it, it will persist after the program exits from the function:

void Leak(int x){

char* p = new char [x];

// delete [] p; // Remove the first comment marking to correct.

}

5.Pay attention to the square braces after "delete." Use "delete" by itself to free a single object. Use "delete" [] with square brackets to free a heap array. Don't do something like this:

char* one = new char;

delete [] one; // Wrong

char* many = new char [30];

delete many; // Wrong!

6. If the leak yet allowed - I'm usually seeking it with deleaker

Software Development- Things to Take care

1. Always do Code Reviews, as it helps catch bugs in early stages of development.
2. 
   

new and delete

1.  Syntax: void*  operator new(size_t size);
     Three forms of using new
   • T* p = new T
   • T* p = new T(value)
   • T* p = new T[size]                                                                
2. new is an operator to Allocate memory for an object or array of objects of type-name from the free store and returns a suitably typed, nonzero pointer to the object.The pointer returned is cast to the data type implicitly
3. When new is used to allocate memory for a C++ class object, the object's constructor is called after the memory is allocated.Invokes default constructor on all the objects in case of an array of objects
4. If unsuccessful, new returns zero or throws an exception.You can change this default behavior by writing a custom exception-handling routine and calling the  _set_new_handler run-time library function with your function name as its argument.
5. To allocate and then frees a two-dimensional array of characters of size w by 10.                                            char (*pchar)[10] = new char[dim][10];                                                                                        delete [] pchar;
6. The type-name cannot contain const, volatile, class declarations, or enumeration declarations. Therefore, the following expression is illegal.
7. The new operator does not allocate reference types because they are not objects.
8. The new operator cannot be used to allocate a function, but it can be used to allocate pointers to functions. The following example allocates and then frees an array of seven pointers to functions that return integers.                                                                                                            int (**p) () = new (int (*[7]) ());                                                                                            delete *p;

Qt

1. Signals and slots are used for communication between objects.They are alternative to the callback technique
2.  A signal is emitted when a particular event occurs. 
3.  A slot is a function that is called in response to a particular signal.
4. All classes that contain signals or slots must mention Q_OBJECT at the top of their declaration. They must also derive (directly or indirectly) from QObject.
5. The signature of a signal must match the signature of the receiving slot. (In fact a slot may have a shorter signature than the signal it receives because it can ignore extra arguments.) Since the signatures are compatible, the compiler can help us detect type mismatches. Signals and slots are loosely coupled: A class which emits a signal neither knows nor cares which slots receive the signal. Qt's signals and slots mechanism ensures that if you connect a signal to a slot, the slot will be called with the signal's parameters at the right time. Signals and slots can take any number of arguments of any type. They are completely type safe.