Saturday, June 23, 2012

Visitor design pattern sample in C++


Visitor design pattern represent an operation to be performed on the elements of an object structure.
Visitor lets you define a new operation without changing the classes of the elements on which it operates.
Using visitor you put all operations to be performed on various elements of an object to a single separate class names "Visitor".

Here I'm publishing a sample code to demonstrate how to use this design pattern to in marketing solution.
Here we have a portfolio of products ( portfolio has many elements/products ) and every product has a method named "Accept" which accepts a visitor and calls it's Visit(..) function by sending itself as argument to it.
Please see following code for more detailed information :
----------------------
#ifndef _VISITOR_H
#define _VISITOR_H
#include <string>
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <list>
using namespace std;
class Tableau;
class KaraPhone;
class  ProductPortfo;
class ProductBase;
class ProductVisitor
{
public:
 virtual void Visit(Tableau* )=0;
 virtual void Visit(KaraPhone* )=0;
 virtual void Visit(ProductPortfo* )=0;
};
class ProductBase
{
public:
 virtual void Accept(class ProductVisitor* )=0;
 string Name;
};
class Tableau:public ProductBase
{
private:
 Tableau(){}
public :
 Tableau(string pName){Name=pName;}
 void Accept(ProductVisitor* pVisitor)
 {
  pVisitor->Visit(this);
 }
 
};
class KaraPhone:public ProductBase
{
private:
 KaraPhone(){}
public :
 KaraPhone(string pName){Name=pName;}
 void Accept(ProductVisitor* pVisitor)
 {
  pVisitor->Visit(this);
 }
};
class ProductPortfo:public ProductBase
{
public:
 ProductBase *mProducts[2];
 
public:
 ProductPortfo()
 {
  mProducts[0]= new Tableau("tableau7");
  mProducts[1]= new KaraPhone("Karaphonev1");
  Name="Products Portfo";
 }
 
 void Accept(ProductVisitor *pVisitor)
 {
  for(int i=0;i<sizeof(mProducts)/sizeof(mProducts[0]);i++)
   mProducts[i]->Accept(pVisitor);
  pVisitor->Visit(this);
 }
};
class PresentorVisitor:public ProductVisitor
{
public :
 void Visit(Tableau *pTableau)
 {
  cout << "PRESENT: best BI solution is " << pTableau->Name;
 }
 void Visit(KaraPhone *pKaraPhone)
 {
  cout << "PRESENT: Karaphone helps you to enefit :" << pKaraPhone->Name;
 }
 void Visit(ProductPortfo *pProd)
 {
  cout << "PRESE tell about company products " << pProd->Name;
 }
};
class POCVisitor:public ProductVisitor
{
public :
 void Visit(Tableau *pTableau)
 {
  cout << " POC: this dashboard is made by " << pTableau->Name;
 }
 void Visit(KaraPhone *pKaraPhone)
 {
  cout << "POC: this benefit is after running this :" << pKaraPhone->Name;
 }
 void Visit(ProductPortfo *pProd)
 {
  cout << "Give  CD of demo softwares :" << pProd->Name;
 }
};

#endif


Friday, June 15, 2012

Rain water trap problem 2D version


Given a 2D matrix where each element represents the elevation(height) on that point, find how many rain water it is able to hold.(Twitter interview question)
For example, given the below 3×3 matrix:
3 3 3
3 0 3
3 3 3
It should hold 3 units of rain water.
I wrote a code for that and I think It works. I tested it against various inputs and got right answer. Please let me know if something appears wrong.
here is my code :

#pragma once
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int> > Visited;
int HowMuchCanHold(vector<vector<int> > &M,int i,int j)
{
 Visited[i][j]=1;
 if(i==0 || j==0 || i==M.size()-1 || j==M[0].size()-1) // we are in borders
  return -1; // drops to earth
 int up=M[i-1][j],down=M[i+1][j],left=M[i][j-1],right=M[i][j+1];
 int minall=1<<10;
 if(!Visited[i-1][j])
  minall=min(minall,up);
 if(!Visited[i+1][j])
  minall=min(minall,down);
 if(!Visited[i][j-1])
  minall=min(minall,left);
 if(!Visited[i][j+1])
  minall=min(minall,right);
 
 int mij=M[i][j];
 if(minall>mij)
  return minall-mij;
 else
  if(minall<mij)
   return -1; // can't hold the drop
 
 int minup=1<<10,mindown=1<<10,minleft=1<<10,minright=1<<10;
 if(mij==up && Visited[i-1][j]==0) // drop may flow up
  minup=HowMuchCanHold(M,i-1,j);
 else
  if(mij!=up)
   minup=up-mij;
 if(mij==down && Visited[i+1][j]==0) // drop may flow down
  mindown=HowMuchCanHold(M,i+1,j);
 else
  if(mij!=down)
   mindown=down-mij;
 if(mij==left && Visited[i][j-1]==0) // drop may flow left
  minleft=HowMuchCanHold(M,i,j-1);
 else
  if(mij!=left)
   minleft=left-mij;
 if(mij==right && Visited[i][j+1]==0) // drop may flow right
  minright=HowMuchCanHold(M,i,j+1);
 else
  if(mij!=right)
   minright=right-mij;
 if(minup<0 || mindown<0 || minleft<0 || minright <0) // drop wil fall from up,down,left or right!
  return -1; // can't hold the drop
  int min1=min(minup,mindown);
  int min2=min(minleft,minright);
  minall=min(min1,min2);
  return minall;
}
int DropTo(vector<vector<int> > &M,int i,int j)
{
  Visited=vector<vector<int> >(M.size(), vector<int>(M[0].size(),0));
  return HowMuchCanHold(M,i,j);
}
int get_watr_trap(vector<vector<int> > M)
{
 int row=M.size();
 int col=M[0].size();
 int total=0;
 int nexthold=0;
 bool find=false;
 while(1)
 {
  find=false;
  for(int i=0;i<row;i++)
  {
   for(int j=0;j<col;j++)
   {
    nexthold=DropTo(M,i,j);
    if(nexthold>0)
    {
     find=true;
     M[i][j]+=nexthold;//fill current cell up to the maxhold
     total+=nexthold;
    }
   }
  }
  if(!find)
   break;
 }
 return total;
}
void test_water_trap()
{
 vector<vector<int> > M(4, vector<int>(4,10));
 M[1][1]=0;
 M[1][2]=2;
 M[2][1]=4;
 M[2][2]=8;
 M[3][0]=2;
 M[3][2]=8;
 int water_trapped=get_watr_trap(M);
 cout << water_trapped << endl;
}


Producer Consumer Pattern implementation using pthread

At this post you will see how to use pthread library for multi-threaded programming and implementing Producer/Consumer pattern in simplest way. you will see how can you avoid busy waiting with condition variables and how to do thread synchronizing. at this example, producer generates random traffic and put it in buffer, and simultaneously consumer retrieves the produced traffic and check if they are suspicious or not. please take care that we can't pass none-static class member as pthread_create function. for handling the problem you need to add a static method to the class and use it in the pthread_create function. this project runs on bot Windows+MinGw and Linux. (( don't forget to add -lpthread for g++ when compiling this file ))
#include <iostream>
#include <pthread.h>
#include <queue>
#include <string>
#include <sstream>
using namespace std;

class Requests
{
private:
 queue<string> mBuffer;
 static const int MAX_BUFFER_LEN=100;
 static const int MAX_PROCESS_LEN=1000;
 int mProcessed;
 int mLen;
 pthread_mutex_t mLock;
 pthread_cond_t mEmptyCond;
 pthread_cond_t mFullCond;
public:
 Requests():mLen(0),mProcessed(0)
 {
  pthread_mutex_init(&mLock,NULL);
  pthread_cond_init(&mFullCond,NULL);
  pthread_cond_init(&mEmptyCond,NULL);
 }
 ~Requests()
 {
  pthread_mutex_destroy(&mLock);
  pthread_cond_destroy(&mFullCond);
  pthread_cond_destroy(&mEmptyCond);
 }
 void Add(string pRequest)
 {
  pthread_mutex_lock(&mLock);
  if(mLen==MAX_BUFFER_LEN)
  {
   cout << "Add waiting because of Full Condition...\n";
   pthread_cond_wait(&mFullCond,&mLock);
  }
  if(ProcessedEnough())
  {
   pthread_mutex_unlock(&mLock);
   return ;
  }
  mProcessed++;
  cout << "Pushing :"<<pRequest<<endl;
  mBuffer.push(pRequest);
  mLen++;
  pthread_mutex_unlock(&mLock);
  pthread_cond_signal(&mEmptyCond);

 }
 string Remove(bool &pProcessFinished)
 {
  pProcessFinished=false;
  pthread_mutex_lock(&mLock);
  if(mLen==0)
  {
   if(ProcessedEnough())
   {
    pProcessFinished=true;
    pthread_mutex_unlock(&mLock);
    pthread_cond_signal(&mFullCond);
    return "";
   }
   cout << "Remove waiting because of Empty Condition...\n";
   pthread_cond_wait(&mEmptyCond,&mLock);
  }

  string ret=mBuffer.front();
  mBuffer.pop();
  cout << ">>>>>>Popping :"<<ret<<endl;
  mLen--;
  pthread_mutex_unlock(&mLock);
  pthread_cond_signal(&mFullCond);

  return ret;
 }
 bool ProcessedEnough()
 {
  return mProcessed > MAX_PROCESS_LEN;
 }
};

class TrafficProducer
{
private :
 Requests *mRequestBuffer;
public:
 TrafficProducer(Requests *pReq):mRequestBuffer(pReq)
 {

 }
 void * ProduceTraffic()
 {
  int i=0;

  while(! mRequestBuffer->ProcessedEnough())
  {
   Sleep(rand()%10);
   ostringstream os;
   os << i++;
   mRequestBuffer->Add(os.str());

  }
  return NULL;
 }
 static void * Run(void *pContext)
 {
  return static_cast<TrafficProducer *>(pContext)->ProduceTraffic();
 }
};
class TrafficInspector
{
private :
 Requests *mRequestBuffer;
public:
 TrafficInspector(Requests *pReq):mRequestBuffer(pReq)
 {

 }
 void * InspectTraffic()
 {
  int i;
  string s;
  while(1)
  {
   Sleep(rand()%5);
   bool finished;
   s= mRequestBuffer->Remove(finished);
   if(finished)
    return NULL;
   i=atoi(s.c_str());
   if(i%19 == 0)
   {
    cout << "suspicios data recieved:"<<i<<endl;
   }
  }
  return NULL;
 }
 static void * Run(void *pContext)
 {
  return static_cast<TrafficInspector*>(pContext)->InspectTraffic();
 }
};
int main() {
 Requests reqBuff;
 TrafficProducer producer(&reqBuff);
 TrafficInspector consumer(&reqBuff);
 pthread_t th_producer;
 pthread_t th_consumer;
 pthread_create(&th_producer,NULL,TrafficProducer::Run,static_cast<void*>(&producer));
 pthread_create(&th_consumer,NULL,TrafficInspector::Run,static_cast<void*>(&consumer));
 pthread_join(th_producer,NULL);
 pthread_join(th_consumer,NULL);

 cout << "Finished" << endl; 
 return 0;
}



Thursday, June 14, 2012

Count Leading Zero bits in an integer

How to count all zeros from left to right until reach first set (1) bit? we name it counting leading zeros :
int clz (int x)
{
 if (x ==0)
  return 32;
 int n=0;
 if ((x & 0xFFFF0000) == 0) { n += 16; x =x << 16;} //1111 1111 1111 1111 0000 0000 0000 0000 // 16 bits from left are zero! so we omit 16left bits
 if ((x & 0xFF000000) == 0){ n = n +  8; x = x <<  8;} // 8 left bits are 0
 if ((x & 0xF0000000) ==0){ n = n +  4; x = x <<  4;} // 4 left bits are 0
 if ((x & 0xC0000000) == 0){ n =n +  2, x = x <<  2;}  // 110000....0 2 left bits are zero
 if ((x & 0x80000000) == 0){n = n +  1, x = x <<  1;} // first left bit is zero
 return n;
}

Find all links inside a HTML source using Google RE2

Here is a small code to show you how to find all links inside a HTML source code using Google's Regular Expression library (RE2) :
-----------------------------------------------------------------
string text=" html source goes here <a href='http://google.com/top-l/?search=xyz&x=t'>site link</a> testing <a   href= '../news/show?id=4'>ms</a>";
 re2::RE2 linksre("<a[\s\w]*href=\s*'([\w:/{1,2}.\?=\-&%]*)'[\s\w]*>");
string res;
re2::StringPiece html(text);
while(RE2::FindAndConsume(&html, linksre ,&res))
{
cout << "("<<res<<")"<<endl;
}
-----------------------------------------------------------------

output is :
(http://google.com/top-l/?search=xyz&x=t)
(../news/show?id=4)

Thursday, June 7, 2012

Min Coin Change problem using DP and backtracking

Suppose we have set of coins S={c1,c2,c3,...cn} and M
we need to find smallest number of coins to change M.
or find all <kj,cj> such that Sum ( kj*cj ) = M

Solution:
I used dynamic programming to solve the problem and also used backtracking to return all <kj,cj>:

for more information have a look at :
http://www.algorithmist.com/index.php/Min-Coin_Change

----------------------------------------------
map<int,int> min_coins(vector<int> pCoins,int pSum,int *pMinRequired)
{
 map<int,int> trace;//(pCoins.size());
 vector<int> mins(pSum+1);
 vector<int> prev(pSum+1);
 fill(mins.begin(),mins.end(),INFINITY);
 for(int i=0;i<pCoins.size();i++)
  trace.insert(make_pair<int,int>(pCoins[i],0));
 mins[0]=0;
 sort(pCoins.begin(),pCoins.end());
 for(int i=1;i<=pSum;i++)
 {
  int bestCoin=-1;
  for(int v=0;v<pCoins.size() && pCoins[v]<=i  ;v++)
   if(mins[i-pCoins[v]]+1<mins[i])
   {
    mins[i]=mins[i-pCoins[v]]+1;
    bestCoin=v;
    prev[i]=i-pCoins[v];
   }
   if(bestCoin !=-1)
    trace[i]=pCoins[bestCoin];
 }
 *pMinRequired= mins[pSum];
 int curr=pSum;
 map<int,int> ret;
 while(curr>0)
 {
  ret[trace[curr]]++;
  curr=prev[curr];
 }
 return  ret;
}

 void test_coins()
{
 vector<int> coins;
 coins.push_back(1);
 coins.push_back(5);
 coins.push_back(10);
 coins.push_back(25);
 int minreq,sum=30;
 map<int,int> result=min_coins(coins,sum,&minreq);
 cout << " min required for "<<sum<<"$ is to pick "<<minreq<<" coins as :"<<endl;
 for(map<int,int>::iterator it=result.begin();it!=result.end();it++)
  cout <<" pick "<<it->second <<" coins of "<<it->first<<endl;

}
---------------------------------------------

Sunday, June 3, 2012

How to implement T9 contact search in C++ using Trie-Trees ?
Design Patterns: Observer Pattern
please see more information in my G+ ProPro Page :

Observer Pattern in my G+ ProPro Page

Saturday, June 23, 2012

Visitor design pattern sample in C++


Visitor design pattern represent an operation to be performed on the elements of an object structure.
Visitor lets you define a new operation without changing the classes of the elements on which it operates.
Using visitor you put all operations to be performed on various elements of an object to a single separate class names "Visitor".

Here I'm publishing a sample code to demonstrate how to use this design pattern to in marketing solution.
Here we have a portfolio of products ( portfolio has many elements/products ) and every product has a method named "Accept" which accepts a visitor and calls it's Visit(..) function by sending itself as argument to it.
Please see following code for more detailed information :
----------------------
#ifndef _VISITOR_H
#define _VISITOR_H
#include <string>
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <list>
using namespace std;
class Tableau;
class KaraPhone;
class  ProductPortfo;
class ProductBase;
class ProductVisitor
{
public:
 virtual void Visit(Tableau* )=0;
 virtual void Visit(KaraPhone* )=0;
 virtual void Visit(ProductPortfo* )=0;
};
class ProductBase
{
public:
 virtual void Accept(class ProductVisitor* )=0;
 string Name;
};
class Tableau:public ProductBase
{
private:
 Tableau(){}
public :
 Tableau(string pName){Name=pName;}
 void Accept(ProductVisitor* pVisitor)
 {
  pVisitor->Visit(this);
 }
 
};
class KaraPhone:public ProductBase
{
private:
 KaraPhone(){}
public :
 KaraPhone(string pName){Name=pName;}
 void Accept(ProductVisitor* pVisitor)
 {
  pVisitor->Visit(this);
 }
};
class ProductPortfo:public ProductBase
{
public:
 ProductBase *mProducts[2];
 
public:
 ProductPortfo()
 {
  mProducts[0]= new Tableau("tableau7");
  mProducts[1]= new KaraPhone("Karaphonev1");
  Name="Products Portfo";
 }
 
 void Accept(ProductVisitor *pVisitor)
 {
  for(int i=0;i<sizeof(mProducts)/sizeof(mProducts[0]);i++)
   mProducts[i]->Accept(pVisitor);
  pVisitor->Visit(this);
 }
};
class PresentorVisitor:public ProductVisitor
{
public :
 void Visit(Tableau *pTableau)
 {
  cout << "PRESENT: best BI solution is " << pTableau->Name;
 }
 void Visit(KaraPhone *pKaraPhone)
 {
  cout << "PRESENT: Karaphone helps you to enefit :" << pKaraPhone->Name;
 }
 void Visit(ProductPortfo *pProd)
 {
  cout << "PRESE tell about company products " << pProd->Name;
 }
};
class POCVisitor:public ProductVisitor
{
public :
 void Visit(Tableau *pTableau)
 {
  cout << " POC: this dashboard is made by " << pTableau->Name;
 }
 void Visit(KaraPhone *pKaraPhone)
 {
  cout << "POC: this benefit is after running this :" << pKaraPhone->Name;
 }
 void Visit(ProductPortfo *pProd)
 {
  cout << "Give  CD of demo softwares :" << pProd->Name;
 }
};

#endif


Friday, June 15, 2012

Rain water trap problem 2D version


Given a 2D matrix where each element represents the elevation(height) on that point, find how many rain water it is able to hold.(Twitter interview question)
For example, given the below 3×3 matrix:
3 3 3
3 0 3
3 3 3
It should hold 3 units of rain water.
I wrote a code for that and I think It works. I tested it against various inputs and got right answer. Please let me know if something appears wrong.
here is my code :

#pragma once
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int> > Visited;
int HowMuchCanHold(vector<vector<int> > &M,int i,int j)
{
 Visited[i][j]=1;
 if(i==0 || j==0 || i==M.size()-1 || j==M[0].size()-1) // we are in borders
  return -1; // drops to earth
 int up=M[i-1][j],down=M[i+1][j],left=M[i][j-1],right=M[i][j+1];
 int minall=1<<10;
 if(!Visited[i-1][j])
  minall=min(minall,up);
 if(!Visited[i+1][j])
  minall=min(minall,down);
 if(!Visited[i][j-1])
  minall=min(minall,left);
 if(!Visited[i][j+1])
  minall=min(minall,right);
 
 int mij=M[i][j];
 if(minall>mij)
  return minall-mij;
 else
  if(minall<mij)
   return -1; // can't hold the drop
 
 int minup=1<<10,mindown=1<<10,minleft=1<<10,minright=1<<10;
 if(mij==up && Visited[i-1][j]==0) // drop may flow up
  minup=HowMuchCanHold(M,i-1,j);
 else
  if(mij!=up)
   minup=up-mij;
 if(mij==down && Visited[i+1][j]==0) // drop may flow down
  mindown=HowMuchCanHold(M,i+1,j);
 else
  if(mij!=down)
   mindown=down-mij;
 if(mij==left && Visited[i][j-1]==0) // drop may flow left
  minleft=HowMuchCanHold(M,i,j-1);
 else
  if(mij!=left)
   minleft=left-mij;
 if(mij==right && Visited[i][j+1]==0) // drop may flow right
  minright=HowMuchCanHold(M,i,j+1);
 else
  if(mij!=right)
   minright=right-mij;
 if(minup<0 || mindown<0 || minleft<0 || minright <0) // drop wil fall from up,down,left or right!
  return -1; // can't hold the drop
  int min1=min(minup,mindown);
  int min2=min(minleft,minright);
  minall=min(min1,min2);
  return minall;
}
int DropTo(vector<vector<int> > &M,int i,int j)
{
  Visited=vector<vector<int> >(M.size(), vector<int>(M[0].size(),0));
  return HowMuchCanHold(M,i,j);
}
int get_watr_trap(vector<vector<int> > M)
{
 int row=M.size();
 int col=M[0].size();
 int total=0;
 int nexthold=0;
 bool find=false;
 while(1)
 {
  find=false;
  for(int i=0;i<row;i++)
  {
   for(int j=0;j<col;j++)
   {
    nexthold=DropTo(M,i,j);
    if(nexthold>0)
    {
     find=true;
     M[i][j]+=nexthold;//fill current cell up to the maxhold
     total+=nexthold;
    }
   }
  }
  if(!find)
   break;
 }
 return total;
}
void test_water_trap()
{
 vector<vector<int> > M(4, vector<int>(4,10));
 M[1][1]=0;
 M[1][2]=2;
 M[2][1]=4;
 M[2][2]=8;
 M[3][0]=2;
 M[3][2]=8;
 int water_trapped=get_watr_trap(M);
 cout << water_trapped << endl;
}


Producer Consumer Pattern implementation using pthread

At this post you will see how to use pthread library for multi-threaded programming and implementing Producer/Consumer pattern in simplest way. you will see how can you avoid busy waiting with condition variables and how to do thread synchronizing. at this example, producer generates random traffic and put it in buffer, and simultaneously consumer retrieves the produced traffic and check if they are suspicious or not. please take care that we can't pass none-static class member as pthread_create function. for handling the problem you need to add a static method to the class and use it in the pthread_create function. this project runs on bot Windows+MinGw and Linux. (( don't forget to add -lpthread for g++ when compiling this file ))
#include <iostream>
#include <pthread.h>
#include <queue>
#include <string>
#include <sstream>
using namespace std;

class Requests
{
private:
 queue<string> mBuffer;
 static const int MAX_BUFFER_LEN=100;
 static const int MAX_PROCESS_LEN=1000;
 int mProcessed;
 int mLen;
 pthread_mutex_t mLock;
 pthread_cond_t mEmptyCond;
 pthread_cond_t mFullCond;
public:
 Requests():mLen(0),mProcessed(0)
 {
  pthread_mutex_init(&mLock,NULL);
  pthread_cond_init(&mFullCond,NULL);
  pthread_cond_init(&mEmptyCond,NULL);
 }
 ~Requests()
 {
  pthread_mutex_destroy(&mLock);
  pthread_cond_destroy(&mFullCond);
  pthread_cond_destroy(&mEmptyCond);
 }
 void Add(string pRequest)
 {
  pthread_mutex_lock(&mLock);
  if(mLen==MAX_BUFFER_LEN)
  {
   cout << "Add waiting because of Full Condition...\n";
   pthread_cond_wait(&mFullCond,&mLock);
  }
  if(ProcessedEnough())
  {
   pthread_mutex_unlock(&mLock);
   return ;
  }
  mProcessed++;
  cout << "Pushing :"<<pRequest<<endl;
  mBuffer.push(pRequest);
  mLen++;
  pthread_mutex_unlock(&mLock);
  pthread_cond_signal(&mEmptyCond);

 }
 string Remove(bool &pProcessFinished)
 {
  pProcessFinished=false;
  pthread_mutex_lock(&mLock);
  if(mLen==0)
  {
   if(ProcessedEnough())
   {
    pProcessFinished=true;
    pthread_mutex_unlock(&mLock);
    pthread_cond_signal(&mFullCond);
    return "";
   }
   cout << "Remove waiting because of Empty Condition...\n";
   pthread_cond_wait(&mEmptyCond,&mLock);
  }

  string ret=mBuffer.front();
  mBuffer.pop();
  cout << ">>>>>>Popping :"<<ret<<endl;
  mLen--;
  pthread_mutex_unlock(&mLock);
  pthread_cond_signal(&mFullCond);

  return ret;
 }
 bool ProcessedEnough()
 {
  return mProcessed > MAX_PROCESS_LEN;
 }
};

class TrafficProducer
{
private :
 Requests *mRequestBuffer;
public:
 TrafficProducer(Requests *pReq):mRequestBuffer(pReq)
 {

 }
 void * ProduceTraffic()
 {
  int i=0;

  while(! mRequestBuffer->ProcessedEnough())
  {
   Sleep(rand()%10);
   ostringstream os;
   os << i++;
   mRequestBuffer->Add(os.str());

  }
  return NULL;
 }
 static void * Run(void *pContext)
 {
  return static_cast<TrafficProducer *>(pContext)->ProduceTraffic();
 }
};
class TrafficInspector
{
private :
 Requests *mRequestBuffer;
public:
 TrafficInspector(Requests *pReq):mRequestBuffer(pReq)
 {

 }
 void * InspectTraffic()
 {
  int i;
  string s;
  while(1)
  {
   Sleep(rand()%5);
   bool finished;
   s= mRequestBuffer->Remove(finished);
   if(finished)
    return NULL;
   i=atoi(s.c_str());
   if(i%19 == 0)
   {
    cout << "suspicios data recieved:"<<i<<endl;
   }
  }
  return NULL;
 }
 static void * Run(void *pContext)
 {
  return static_cast<TrafficInspector*>(pContext)->InspectTraffic();
 }
};
int main() {
 Requests reqBuff;
 TrafficProducer producer(&reqBuff);
 TrafficInspector consumer(&reqBuff);
 pthread_t th_producer;
 pthread_t th_consumer;
 pthread_create(&th_producer,NULL,TrafficProducer::Run,static_cast<void*>(&producer));
 pthread_create(&th_consumer,NULL,TrafficInspector::Run,static_cast<void*>(&consumer));
 pthread_join(th_producer,NULL);
 pthread_join(th_consumer,NULL);

 cout << "Finished" << endl; 
 return 0;
}



Thursday, June 14, 2012

Count Leading Zero bits in an integer

How to count all zeros from left to right until reach first set (1) bit? we name it counting leading zeros :
int clz (int x)
{
 if (x ==0)
  return 32;
 int n=0;
 if ((x & 0xFFFF0000) == 0) { n += 16; x =x << 16;} //1111 1111 1111 1111 0000 0000 0000 0000 // 16 bits from left are zero! so we omit 16left bits
 if ((x & 0xFF000000) == 0){ n = n +  8; x = x <<  8;} // 8 left bits are 0
 if ((x & 0xF0000000) ==0){ n = n +  4; x = x <<  4;} // 4 left bits are 0
 if ((x & 0xC0000000) == 0){ n =n +  2, x = x <<  2;}  // 110000....0 2 left bits are zero
 if ((x & 0x80000000) == 0){n = n +  1, x = x <<  1;} // first left bit is zero
 return n;
}

Find all links inside a HTML source using Google RE2

Here is a small code to show you how to find all links inside a HTML source code using Google's Regular Expression library (RE2) :
-----------------------------------------------------------------
string text=" html source goes here <a href='http://google.com/top-l/?search=xyz&x=t'>site link</a> testing <a   href= '../news/show?id=4'>ms</a>";
 re2::RE2 linksre("<a[\s\w]*href=\s*'([\w:/{1,2}.\?=\-&%]*)'[\s\w]*>");
string res;
re2::StringPiece html(text);
while(RE2::FindAndConsume(&html, linksre ,&res))
{
cout << "("<<res<<")"<<endl;
}
-----------------------------------------------------------------

output is :
(http://google.com/top-l/?search=xyz&x=t)
(../news/show?id=4)

Thursday, June 7, 2012

Min Coin Change problem using DP and backtracking

Suppose we have set of coins S={c1,c2,c3,...cn} and M
we need to find smallest number of coins to change M.
or find all <kj,cj> such that Sum ( kj*cj ) = M

Solution:
I used dynamic programming to solve the problem and also used backtracking to return all <kj,cj>:

for more information have a look at :
http://www.algorithmist.com/index.php/Min-Coin_Change

----------------------------------------------
map<int,int> min_coins(vector<int> pCoins,int pSum,int *pMinRequired)
{
 map<int,int> trace;//(pCoins.size());
 vector<int> mins(pSum+1);
 vector<int> prev(pSum+1);
 fill(mins.begin(),mins.end(),INFINITY);
 for(int i=0;i<pCoins.size();i++)
  trace.insert(make_pair<int,int>(pCoins[i],0));
 mins[0]=0;
 sort(pCoins.begin(),pCoins.end());
 for(int i=1;i<=pSum;i++)
 {
  int bestCoin=-1;
  for(int v=0;v<pCoins.size() && pCoins[v]<=i  ;v++)
   if(mins[i-pCoins[v]]+1<mins[i])
   {
    mins[i]=mins[i-pCoins[v]]+1;
    bestCoin=v;
    prev[i]=i-pCoins[v];
   }
   if(bestCoin !=-1)
    trace[i]=pCoins[bestCoin];
 }
 *pMinRequired= mins[pSum];
 int curr=pSum;
 map<int,int> ret;
 while(curr>0)
 {
  ret[trace[curr]]++;
  curr=prev[curr];
 }
 return  ret;
}

 void test_coins()
{
 vector<int> coins;
 coins.push_back(1);
 coins.push_back(5);
 coins.push_back(10);
 coins.push_back(25);
 int minreq,sum=30;
 map<int,int> result=min_coins(coins,sum,&minreq);
 cout << " min required for "<<sum<<"$ is to pick "<<minreq<<" coins as :"<<endl;
 for(map<int,int>::iterator it=result.begin();it!=result.end();it++)
  cout <<" pick "<<it->second <<" coins of "<<it->first<<endl;

}
---------------------------------------------