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];
    }
}

Static blocks in C++

Java Code:

Class NewObjectType{

static{
Factory.register("MyType", new NewObejctType);
}
 //Rest of the code goes here.
}

This is fine, your class registers with factory, but how will you achieve this in C++????
How to get static blocks in C++?

Here is the solution/code for it:

#include "stdafx.h"
#include <iostream>
#include<map>

using namespace std;
class Abs{
public:
    static void reg();
};

class Factory{
    static std::map<int,Abs*> map;
public:
    static void regsiter(int id,Abs *a)
    {
        cout<<"child registered"<<endl;
        map.insert(make_pair(id,a));
    }
};

std::map<int,Abs*> Factory::map;

class child:public Abs{
    static int ret;
public:
    child()
    {
        display();
    }
    void display()
    {
        cout<<"child"<<endl;
    }
    static int reg()
    {
        cout<<"static method called"<<endl;
        Factory::regsiter(10,new child());
        return 0;
    }
};

 int child::ret = child::reg();

int _tmain(int argc, _TCHAR* argv[])
{
    return 0;
}

Factory Pattern - Better way

when we write factory pattern, generally we write if-else bock to create the objects of the input type
something like

Base* Factory::getObject(int type)
{
if(type==1)
return new TypeOne();
else if(type==2)
return new TypeTwo();
...
...
}

But in this case, we need to modify the factory class every time we add a new object type, this violates the principle of Dependency Inversion, where higher level objects should not depend on the lower level objects.

 So how to get the new objects returned from Factory without modifying it?

The solution is using the registration mechanism, when ever a new object type is introduced , you register that with factory with a id/type value. This way factory maintains all the new obejcts with some type/id.
 You can you java reflection if you register with class name or can you protptype pattern to clone the new objects.
Java Code:

Class NewObjectType{

static{
Factory.register("MyType", new NewObejctType);
}
 //Rest of the code goes here.
}

This is fine, your class registers with factory, but how will you achieve this in C++????
How to get static blocks in C++?

Here is the solution/code for it:

#include "stdafx.h"
#include <iostream>
#include<map>

using namespace std;
class Abs{
public:
    static void reg();
};

class Factory{
    static std::map<int,Abs*> map;
public:
    static void regsiter(int id,Abs *a)
    {
        cout<<"child registered"<<endl;
        map.insert(make_pair(id,a));
    }
};

std::map<int,Abs*> Factory::map;

class child:public Abs{
    static int ret;
public:
    child()
    {
        display();
    }
    void display()
    {
        cout<<"child"<<endl;
    }
    static int reg()
    {
        cout<<"static method called"<<endl;
        Factory::regsiter(10,new child());
        return 0;
    }
};

 int child::ret = child::reg();

int _tmain(int argc, _TCHAR* argv[])
{
    return 0;
}

Parking lot design

Point Of Sale design