Ronzii's Blog

Just your average geek's blog

Mirror Tree Comparision

int checkMirror(Node* a, node* b)
{
	if(a==NULL && b==NULL)
		return 1;
	else if(a==NULL || b==NULL)
		return 0;
	else if(a->data == b->data)
	{
		return checkMirror(a->left,b->right) && checkMirror(a->right,b->left);
	}
	return 0;
}
Advertisements

February 26, 2012 Posted by | C++ | , , | Leave a comment

Rabin Karp Algorithm

#include<cstdio>
#include<iostream>
#include<cstring>
#define d 256
using namespace std;
void search(string pattern, string text, int prime)
{
    int M = pattern.length();
    int N = text.length();
    int h = 1;
    //The value of h would be "pow(d, M-1)%prime"
    for(int i=0; i<M-1; i++)
    {
        h = (h*d)%prime;
    }
    int p = 0,t = 0,i,j;
    // Calculate the hash value of pattern and first window of text
    for(i=0; i<M; i++)
    {
        p = (d*p+pattern[i])%prime;
        t = (d*t+text[i])%prime;
    }
    cout<<p<<endl;
    for(i=0; i<=(N-M); i++)
    {
        if ( p == t )
        {
            // Chaeck the hash values of current window of text and pattern
            // If the hash values match then only check for characters on by one
            for (j = 0; j < M; j++)
            {
                if (text[i+j] != pattern[j])
                    break;
            }
            if (j == M)  // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]
            {
                printf("Pattern found at index %d \n", i);
            }
        }
        // Calulate hash value for next window of text: Remove leading digit,
        // add trailing digit
        if(i<(N-M))
        {
            t = ((t - text[i]*h)*d + text[i+M])%prime;
            if(t<0)
            {
                t = t+prime;
            }
        }
    }
}
int main()
{
    string txt = "abacadabrabrarabraabracadcabracadabrabrabracad";
    string pat = "rabrabracad";
    int q = 103;  // A prime number
    search(pat, txt, q);
    return 0;
}

February 26, 2012 Posted by | C++ | , , , , , | Leave a comment

Given an array of strings of 0s and 1s. Return the maximum number of elements in a subset of the array given number of Zero’s and One’s

#include<iostream>
#include<string>
#include<vector>
using namespace std;
string input[] = {"01","10","0","110","00","001"};
void printPairArray(vector< pair<int,int> > a)
{
    for(vector< pair<int,int> >::iterator itr=a.begin(); itr!=a.end(); itr++)
    {
        cout<<itr->first<<" "<<itr->second<<endl;
    }
}
void printStringArray(string a[], int length)
{
    for(int i=0; i<length; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
vector< pair<int,int> > createPair()
{
    vector< pair<int,int> > v;
    int length = sizeof(input)/sizeof(string);
    for(int i=0; i<length; i++)
    {
        int n0 = 0;
        int stringLength = input[i].length();
        string temp = input[i];
        for(int j=0; j<stringLength; j++)
        {
            if(temp[j]=='0')
            {
                n0++;
            }
        }
        int n1 = stringLength - n0;
        v.push_back(pair<int,int>(n0,n1));
    }
    return v;
}
void getSubset(vector< pair<int,int> > v, string output[],int v_size,int start,
               int x, int y,int X, int Y)
{
    if(x==X && y==Y)
    {
        printStringArray(output,v_size);
    }
    else if(x>X || y>Y)
    {
    }
    else
    {
        for(int i = start; i<v.size(); i++)
        {
            output[v_size] = input[i];
            getSubset(v,output, v_size+1,i+1,x+v[i].first,y+v[i].second,X,Y);
        }
    }
}
int main()
{
    vector< pair<int,int> > v = createPair();
    int length = sizeof(input)/sizeof(string);
    string output[length];
    getSubset(v,output,0,0,0,0,4,3);
    return 0;
}

February 26, 2012 Posted by | C++ | , , | Leave a comment

Given an array A[], find (i, j) such that A[i] < A[j] and (j – i) is maximum.

#include<iostream>
#include<vector>
using namespace std;
void printArray(vector<int> a)
{
    for(vector<int>::iterator itr=a.begin(); itr!=a.end(); itr++)
    {
        cout<<*itr<<" ";
    }
    cout<<endl;
}
void MaxDifference(vector<int> a)
{
    int n = a.size();
    vector<int> Lmin(n,0);
    vector<int> Rmax(n,0);
    Lmin[0] = a[0];
    for(int i=1; i<n; i++)
        Lmin[i] = min(a[i],Lmin[i-1]);
    Rmax[n-1] = a[n-1];
    for(int j=n-2; j>=0; j--)
        Rmax[j] = max(a[j],Rmax[j+1]);
    printArray(Lmin);
    printArray(Rmax);
    int i=0,j=0,maxdiff=0;
    while(i<n && j<n)
    {
        if(Lmin[i]<Rmax[j])
        {
            maxdiff = max(maxdiff,j-i);
            j++;
        }
        else
        {
            i++;
        }
    }
    cout<<maxdiff;
}
int main()
{
    int a[] = {3,1,4,5,2,1,2};
    vector<int> v(a,a+sizeof(a)/sizeof(int));
    printArray(v);
    MaxDifference(v);
    return 0;
}

February 26, 2012 Posted by | C++ | , , , , | Leave a comment