Sunday, February 1, 2015

Regular expression implementation for '*' and '?' wildcard characters

Assuming we have two string - a normal string which will be matched against a regular expression string. The idea is simple: iterate through both string simultaneously. If:

  • current char in regex is '?', skip current characters from both strings
  • current char in regex is '*', find the next matching character in original string
  • else match the current character.

The implementation of the above idea is captured in code at the link

Sliding window implementation:

Problem: Given an array and subarray size, find the max. sum from subarrays.
Solution: 
Naive solution is to iterate through all the subarrays and find the sums. Each time, compare the sum with the previous max and update accordingly. The solution is quadratic in nature.
A better solution implementing sliding window where in each iteration, remove the first integer in the last array and add the value of the newly added array in the subarray.
An implementation of it is here in the link.

Friday, July 6, 2012

SOLID design principles

To understand what these principles are, I have kept them inline comments in the code. I will keep updating the code portions that will act as examples to quickly understand each of them.
The format of the code is as follows:
SOLID principles one line definitions
Pick each letter from SOLID, i.e., each principle and create separate namespace followed by partition line as a series of "=".

namespace SOLIDDesignPrinciples
{
    // S: Single responsibility principle (SRP)
    // A class/method should concentrate on one task - doing one thing only

    // O: Open/Close principle (OCP)
    // A component should be open for extension but close for change
    // Change a class behavior using inheritance/polymorphism

    // L: Liskov Substitution principle (LSP)
    // S is derived from B then object of B can be replaced with objects of S

    // I: Interface Segregation principle (ISP)
    // No client should be forced to use/depend on methods it doesn't use. Keep interfaces small and cohesive

    // D: Dependency Inversion principle (DIP)
    // A. High level modules should not depend upon low level modules. Both should depend upon abstractions.
    // B. Abstractions should not depend upon details. Details should depend upon abstractions.
    // Use lots of interfaces and abstractions
    class MainClass
    {
        public static void Main (string[] args)
        {
            Console.WriteLine ("Hello World!");
        }
    }
}

====================================================================
namespace SOLIDDesignPrinciples
{
    namespace SingleResponsibilityPrinciple
    {
        /// <summary>
        /// Single responsibility - this class will act as a single responsibility class.
        /// As an example, let it be an employee class. There can be many implementations to it,
        /// where in the class, in addition to keeping employee's basic info, we will calculate bonus, taxes etc.
        /// Note that this class becomes complex if we calculate information related to the basic information.
        /// Rather, we can have separate classes for each job.
        /// We will have two classes in order to follow SRP.
        /// </summary>
        public class EmployeeInformation
        {
            public int Salary { get; set; }

            public int Age { get; set; }

            public string Name { get; set; }

            public EmployeeInformation ()
            {
            }
        }
   
        public class Calculations
        {
            private EmployeeInformation empInfo;

            public EmployeeInformation EmployeeInformation
            { get; private set; }

            public Calculations (EmployeeInformation empInfo)
            {
                this.empInfo = empInfo;
            }

            public int Tax { get; private set; }

            public void CalculateTax ()
            {
                // Implementation here
            }

            public int Bonus { get; private set; }

            public void CalculateBonus (int percentage)
            {
                // Implementation here
            }
        }
    }
}
====================================================================

Saturday, June 30, 2012

3SUM algorithm

Problem is:
Given an array of integers, find subset of 3 elements of the array such that sum of those three elements is zero.
Brute force:
1. Find all 3-element subsets in the set S.
2. For each subset, find some of each subset
3. Print the one whose sum is zero
Alternative and improved:
1. Sort the list.
2. Following is the algorithm

-25 -10 -7 -3 2 4 8 10  (a+b+c==-25)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-22)
 . . .
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-7)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-7)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-3)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==2)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==0)


where bold one is 'a' and red ones are 'b' and 'c' - shown in the parenthesis on the right.

Following is the working code:

class tuple
{
private:
int i;
int j;
int k;
public:
tuple() { i = 0; j = 0; k = 0; }
tuple(int a, int b, int c) { i = a; j = b; k = c; }
int GetI() { return i; }
int GetJ() { return j; }
int GetK() { return k; }
void SetI(int a) { i = a; }
void SetJ(int b) { j = b; }
void SetK(int c) { k = c; }
};

int compare (const void* a, const void *b)
{
return (*(int*)a - *(int*)b);
}

tuple* SUM (int *a, int n)
{
if (a == NULL) return NULL;
if (n <= 2) return NULL;

qsort (a, n, sizeof(int), compare);
cout << "Sorting complete \n";
cout << "Sorted array is:\n";
for (int i = 0; i < n; i++)
cout << a[i] << '\t';

cout << endl;

for (int i = 0; i < n - 3; i++)
{
int j = i + 1;
int k = n - 1;
while (j < k)
{
if (a[i] + a[j] + a[k] == 0)
return new tuple(i, j, k);
if (a[i] + a[j] + a[k] < 0)
j++;

if (a[i] + a[j] + a[k] > 0)
k--;
}
}

return NULL;
}


Tuesday, June 26, 2012

Find number of inversions in a given list of integers

Inversion: pairs (i,j) of array indices with i<j and A[i] > A[j] 
The task is to find number of such pairs.

A) Brute force way is to start from the left and find out for each element, the number of pairs. At the end, we will have the total count.

B) Another way is to use device-and-conquer paradigm. Divide the list into two. Keep dividing till we reach single element. Then the merge comes for sorting the array. While merging, if the left element is more than the element from the right then we know that the all the elements in the right are smaller than the bigger element, hence we have that count of inversions.
I have outlined the procedure on paper as below:
The code for the same is below:
int MergeAndCount(int *arr, int l, int m, int r);
int MergeSort(int *arr, int l, int r)
{
if (arr == NULL) return 0;
if (l >= r) return 0;

int mid = (l+r)/2;

int left = MergeSort(arr, l, mid);
int right = MergeSort(arr, mid + 1, r);
int mc = MergeAndCount(arr, l, mid, r);
return (left + right + mc);
}

int MergeAndCount(int *arr, int l, int m, int r)
{
if (arr == NULL) return 0;
if (l >= r) return 0;

int icounter = 0;
int tl = l;
int tm = m + 1;
int tr = r;
int temp = 0;
int *tarr = new int [r - l + 1];
while (tl <=m && tm <= r)
{
if (arr[tl] <= arr[tm])
{
tarr[temp++] = arr[tl++];
}
else
{
icounter += m - tl + 1;
tarr [temp++] = arr[tm++];
}
}

while (tl <= m)
tarr[temp++] = arr[tl++];
while (tr <= r)
tarr[temp++] = arr[tr++];

// Now copy back the array
temp = 0;
while (l <= r)
{
arr[l++] = tarr[temp++];
}

delete tarr;
return icounter;
}

I hope it helps.

Monday, June 25, 2012

Longest Palindrome Substring size

In this post, I am going to concentrate on longest palindrome substring's size.
Here is the example:
Let the string be "GEEGGEEROREEGOF"
There are two palindromes in this string:
1. GEEG
2. GEEROREEG

A) One approach is to find all substrings --> Filter them for the one that are palindromes --> Find which one of them is longest and we have the answer.
B) The previous one was brute force. Then I come across this link: http://www.geeksforgeeks.org/archives/19155. The guy has explained beautifully. And it worked.
The idea is that start from the two ends and find out if the characters match. Once we have a match, we start finding recursively if that's a palindrome and if we have the longest one.
Here is the code in C++:

#include<iostream>
#include<string>
using namespace std;

int max (int x, int y) { return (x > y)? x : y; }

// Returns the length of the longest palindromic subsequence in seq
int lps(string seq, int i, int j)
{
   // Base Case 1: If there is only 1 character
   if (i == j)
     return 1;

   // Base Case 2: If there are only 2 characters and both are same
   if (seq[i] == seq[j] && i + 1 == j)
     return 2;

   // If the first and last characters match
   if (seq[i] == seq[j])
      return lps (seq, i+1, j-1) + 2;

   // If the first and last characters do not match
   return max( lps(seq, i, j-1), lps(seq, i+1, j) );
}

Friday, June 15, 2012

Discuss and implement phone book

In this post, I will discuss how to design data structure for a phone book and then implement the same.
A phone book, or some times called the contacts book is a collection of people information on the phone or any other device. So, for the purpose of simplicity, I will use the phone book as a collection of a set {Name, phone number, email} where any of them can be empty. The fastest implementation I found is using TRIE. So, I decided to implement the same.  Following is the implementation, which is pretty straight forward and self explanatory:


// This shows TRIE data structure implementation in C++
// The TRIE is implemented using two different classes.
// 1. Class for each node - this contains a vector of pointers to the same class and a character value
// 2. The container class that holds the root of the TRIE.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Node
{
public:
Node() { c = ' ';}
~Node();
inline vector <Node *> GetChildren() { return child; }
Node *FindChild(char);
void AddChild(char);

private:
vector <Node *> child;
char c;
};

class TrieRoot
{
public:
void AddWord(string s);
bool IsWordPresent(string s);
TrieRoot() { node = new Node(); }
~TrieRoot() { delete node; }

private:
Node *node;
};

Node * Node::FindChild(char c)
{
if (child.empty()) return NULL;
for (unsigned int i = 0; i < child.size(); i++)
{
if ( child[i]->c == c ) 
return child[i];
}
return NULL;
}

void Node::AddChild(char c)
{
Node *temp = new Node();
temp->c = c;
child.push_back(temp);
}

void TrieRoot::AddWord (string s)
{
if (s.empty()) return;
Node *temp = node;
for(unsigned int i = 0; i < s.size(); i++)
{
Node *temp1 = temp->FindChild(s[i]);
if (temp1 == NULL)
{
temp->AddChild(s[i]);
temp = temp->FindChild(s[i]);
}
else
{
temp = temp1;
}
}

return;
}

// Breadth first search
bool TrieRoot::IsWordPresent(string s)
{
if (s.empty()) return false;
Node *temp = node;
for (unsigned int i = 0; i < s.size(); i++)
{
Node *temp1 = temp->FindChild(s[i]);
cout << "Charater to search for: " << s[i] << endl;
if (temp1 == NULL
return false;
}
temp = temp1;
}

return true;
}

Node::~Node()
{
if (!child.empty())
for (unsigned int i = 0; i < child.size(); i++)
delete child[i];
}