Assignment operator - for not corrupting the state of object

If we have an object say a1 of type Array and if we have a line like a1 = a1 somewhere, the program results in unpredictable behavior because there is no self assignment check in the above code. To avoid the above issue, self assignment check must be there while overloading assignment operator. For example, following code does self assignment check.

// Overloaded assignment operator for class Array (with self

// assignment check)

Array& Array::operator = (const Array &rhs)

{

  /* SELF ASSIGNMENT CHECK */

  if(this != &rhs)

  {

    // Deallocate old memory

    delete [] ptr;

    // allocate new space

    ptr = new int [rhs.size];

    // copy values

    size = rhs.size;

    for(int i = 0; i < size; i++)

      ptr[i] = rhs.ptr[i];   

  } 

  return *this;

}

There is minor issue with above code. Even though we are doing self assignment 
check, there is a probability of corrupting the state of current/left
had side object.

We are doing 

delete[] ptr; //which is the member of Array class.

And then we are re-allocating the memory, what if there is a exception thrown
during allocation of memory?? BAD_ALLOW,NO_MEM?

To avoid such problems, first copy the ptr to local_ptr , allocate memory
 an then delete the old memory.

Array& Array::operator = (const Array &rhs)

{

  /* SELF ASSIGNMENT CHECK */

  if(this != &rhs)

  {
int *local_ptr = ptr;

    // allocate new space

    ptr = new int [rhs.size];

    // Deallocate old memory

    delete [] local_ptr;

    // copy values

    size = rhs.size;

    for(int i = 0; i < size; i++)

      ptr[i] = rhs.ptr[i];   

  } 

  return *this;

}




What is rule of three in c++?

Rule of three says, if you happen to write either one of the following , then you better write all of them

1.Destructor
2.Copy Constructor
3.Assignment Operator


The reason is, if you write any of the above, then it is assumed that you want to perform something which is not achieved by the default versions provided by the compiler.

Thread synchronization in Java - better approach

Following is the getInstance method to get the Singleton Object. The advantage of this logic is we avoid checking for the synchronization for every call to getInstance.


Singleton getInstance()
{

     synchronize
    {
           if(instance == null)
           {
                instance = new Singleton();
           }
    }
return instance;
}

In the above code, we always get into synchronization block even though its not required for every call.

To avoid this modify the above code like

Singleton getInstance()
{
 if(instance == null)  //Additional check to not enter into synchronization block.
{
        synchronize
       {
            if(instance == null)
            {
                 instance = new Singleton();
            }
       }
}
return instance;
}

When you HAVE TO write assignment operator?

When we have const or references in assignment operator , then compiler force you to write your own assignement operators. The reason is , const and reference variables can not be re-assigned once we initialized them during construction.

IsBST(Check wether the given tree is BST)

To Check whether given tree is BST or not, we need to change if its left sub tree has any value greater than root or right sub tree has any value less than root.

Ex:
                             10
                 5                        20
            3         15         18           25

If we need node by node comparion with left/rgith sub-tress, we will get true for the above tree, where as we have 15, which is on the left sub tree and is greater than the root(10).

To solve this use one of the following approaches:
Approach 1:
========
bool isBST(Node *root)
{
return BSTUtil(root,INT_MIN,INT_MAX)
}
bool BSTUtil(Node *root, int min,int max)
{
if(root==NULL)
return true;

if(root->data<min || root->data>max)
return false;
return BSTUtil(root->left,min,root->data) && BSTUtil(root->right,root->data,max);
}

We call multiple methods in above approach , which gives the correct results. To make it even simpler use the following approach.

• Go to the left most leaf node in the tree 
• Check that is value is greater than the INT_MIN(lastData);
• Assign the node data to lastData(which is current min value)
• Go back to parent node, as it is the leaf and checks it value greater than lastData
• Assign root->data to lastData
• Now go to the right of the node(if it has) and check its data is greater than the lastData.

Approach 2:
========
bool isBST(Node *root)
{
    static int lastData= INT_MIN;
    if(root==NULL)
        return 1;
    isBST(root->left);
        if(root->data>prev)
            lastData=root->data;
        else{
            cout<<"NOT BST"<<endl;
            return 0;
        }
    return isBST(root->right);
}

Coin Change Problem

Coin Change Problem:


Given set of n coins what is the minimum no of coins required to make an amount P.

This problem can be solved using Dynamic programming, we need to find out the minimum no of coins for the
amount less than P and add 1 additional coin. So to start with, lets consider some example

Coins = {1,2,3}
Amount = 5

C(0)=0 // no coins for amount 0.

To make change of p , say C(P) = Min{ C(p-Vi) } + 1 for i from 1 to n, i<=P
C(1) = Min { C(1-1) } + 1 = C(0) + 1 = 1
C(2) = Min { C(2-1),C(2-2)}+1 = Min { C(1),C(0) } + 1 = Min { 1,0 } + 1 = 1
C(3) = Min { C(3-1),C(3-2),C(3-3)}+1 = Min { C(2),C(1),C(0) } + 1 = Min { 1,1,0 } + 1 = 1
C(4) = Min { C(4-1),C(4-2),C(4-3)}+1 = Min { C(3),C(2),C(1) } + 1 = Min { 1,1,1 } + 1 = 2
C(5) = Min { C(5-1),C(5-2),C(5-3)}+1 = Min { C(4),C(3),C(2) } + 1 = Min { 2,1,1 } + 1 = 2

So, to make a change of 5 using denominations (1,2,3) , we need min of 2 coins.

C++ Code:

int coinChange(int a[],int n,int Sum)
{
    int *S = new int[Sum+1];
    for(int i=0;i<Sum+1;i++)
        S[i]=INT_MAX;

    S[0]=0; // To make amount of zero we need 0 coins.
   
    for(int i=a[0];i<=Sum;i++)  //Start with a[0] thats the min amount for which you get can get change.
    {
        for(int j=0;j<n;j++)
        {
            if(i>=a[j] && S[i-a[j]]+1<S[i])
            {
            S[i]=S[i-a[j]]+1;
            cout<<" I is :"<<i<<" min coins for "<<i<<" is :"<<S[i]<<endl;
            }
        }
    }
    return S[Sum];
}

int main()
{
int arr[] = {5,10, 20}; 
int m = sizeof(arr)/sizeof(arr[0]); 
int n = 30; 
cout<<" Min coins to make "<<n<<" is :"<<coinChange(arr,3,n)<<endl;
return(0);
}

Java Code:
public class CoinChange {

    public static void main(String args[])
    {
        int []denominations = {1,3,5,8,9};
        int value = 28;
        System.out.println("The minimum number of coins required to make change of "+value+" is:"+findMinimumCoinsRequired(denominations,value));
    }

    private static int findMinimumCoinsRequired(int[] denominations, int value) {
       
        int []dp = new int[value+1];       
        dp[0] = 0;

        for(int i = 1; i <= value; i++ )
        {
            dp[i] = Integer.MAX_VALUE;
            for( int j = 0; j < denominations.length; j++ )
            {
                if( denominations[j] <=  i  )
                {
                    dp[i] = Math.min(dp[i], dp[i - denominations[j]]+1);
                }
            }
        }
        return dp[value];
    }
}