Ronzii's Blog

Just your average geek's blog

Find the k-th Smallest Element in the Union of Two Sorted Arrays

#include<iostream>
#include<climits>
using namespace std;
int findKthSmallest(int A[], int m, int B[], int n, int k)
{
    int i = (int)((double)m / (m+n) * (k-1));
    int j = k-i-1;
    int Ai_1 = (i==0)?INT_MIN:A[i-1];
    int Bj_1 = (j==0)?INT_MIN:B[j-1];
    int Ai = (i==m)?INT_MAX:A[i];
    int Bj = (j==n)?INT_MAX:B[j];
    if(Ai_1<Bj && Bj<Ai) return Bj;
    else if(Bj_1<Ai && Ai<Bj) return Ai;
    if(Ai<Bj) return findKthSmallest(A+i+1,m-i-1,B,n,k-i-1);
    else return findKthSmallest(A,m,B+j+1,n-j-1,k-j-1);
}
int main()
{
    int A[] = {7,9,12,14,15,18,34,71};
    int B[] = {5,9,10,13,15};
    int alength = sizeof(A)/sizeof(int);
    int blength = sizeof(B)/sizeof(int);
    cout<<findKthSmallest(A,alength,B,blength,8);
    return 0;
}
Advertisements

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

Finding the Minimum Window in Text which Contains All Elements from Pattern

#include <iostream>
#include <cstring>
#include <climits>
using namespace std;
int findWindowSize(char t[], char p[])
{
    int text_length = strlen(t);
    int pattern_length = strlen(p);
    int pattern_map[256] = {0};
    int text_map[256] = {0};
    // Count occurences in pattern
    for(int i=0; i<pattern_length; i++)
    {
        pattern_map[p[i]]++;
    }
    int count = 0, minLength = INT_MAX, minIndex = 0, maxIndex =0;
    for(int begin=0,end=0; end<text_length; end++)
    {
        // if character is not present in text, then ignore
        if(pattern_map[t[end]]!=0)
        {
            text_map[t[end]]++;
            // Keep a counter on total length of pattern found till now
            if(pattern_map[t[end]]>=text_map[t[end]])
            {
                count++;
            }
        }
        if(count==pattern_length)
        {
            // Check from the left whether any characters can be ignored
            while(text_map[t[begin]] > pattern_map[t[begin]] || text_map[t[begin]]==0)
            {
                if(text_map[t[begin]]> pattern_map[t[begin]])
                {
                    text_map[t[begin]]--;
                }
                begin++;
            }
            // Calculate minimum
            int min = end-begin+1;
            if(minLength>min)
            {
                minLength = min;
                minIndex = begin;
                maxIndex = end;
            }
        }
    }
    return minLength;
}
int main()
{
    char text[] = "bdacabdccdbac";
    char pattern[] = "ccab";
    cout<<findWindowSize(text,pattern);
    return 0;
}

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

Convert Sorted Circular Doubly Linked List into a Balanced Search Tree

struct node
{
	int value;
	struct node* previous;
	struct node* next;
};
typdef struct node Node;
Node* getMiddle(Node* front)
{
	if(front==NULL)
	{
		return NULL;
	}
	else
	{
		Node* slow = front;
		Node* fast = front->previous;
		do
		{
			fast = fast->next->next;
			slow = slow->next
		}while(fast->value > slow->value && fast!=end && fast!=start);
		return slow;
	}
}
Node* convertDLLToTree(Node* front)
{
	// In case of empty list
	if(front==NULL)
	{	
		return NULL;
	}
	// Single Node - Base Case
	else if(front==front->next && front==front->previous)
	{	
		return front;
	}
	else
	{
		// Get Middle
		Node* middle = getMiddle(front);
		// partition into 2 DLL centered at middle
		middle->previous->next = front; // front->previous = middle->previous
		front->previous->next = middle->next; //
		// Find middle of sub DLL
		middle->previous = convertDLLToTree(front);
		middle->next = convertDLLToTree(middle->next);
		return middle;
	}
}

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

Convert Tree into Sorted Circular Doubly Linked List

struct node
{
	int value;
	struct node* left;
	struct node* right;
};
typedef struct node Node;
// Previous tracks the parent
// Head tracks the head of the Circular DLL
Node* treeToList(Node* current, Node* &previous=NULL, Node* &head=NULL)
{
	if(current==NULL)
	{
		return 0;
	}
	treeToList(current->left,previous,head);
	current->left = previous;
	if(previous)
	{
		previous->right = current;
	}
	else
	{
		// Left most node is head of list
		head = current;
	}
	// Save right subtree pointer for recursive call
	Node* right = current->right;
	// Make list circular
	head->left = current;
	current->right = head;
	previous = current;
	treeToList(right,previous,head);
}

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

Longest Common Substring

#include <iostream>
#include <cstring>
using namespace std;
int LongestCommonSubString(string first,string second)
{
    int n1 = first.length(), n2 = second.length(),max=0;
    if(n1==0||n2==0) return 0;
    if(n1<n2) swap(first,second);
    int *current = new int[n2];
    int *previous = new int[n2];
    for(int i=0; i<n1; i++)
    {
        for(int j=0; j<n2; j++)
        {
            if(first[i]!=second[j])
                current[j] = 0;
            else if(i==0||j==0)
                current[j] = 1;
            else
                current[j] = previous[j-1] + 1;

            if(max<current[j])
                max = current[j];
        }
        swap(previous,current);
    }
    delete [] previous;
    delete [] current;
    return max;
}
int main()
{
    cout<<LongestCommonSubString("handler","sandollar");
    return 0;
}

February 27, 2012 Posted by | C++, Dynamic Programming | , , , , , , , | Leave a comment

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

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