Skip to main content

Posts

Showing posts from March, 2014

WildCard Matching algorithm

The logic is quite simple. We do the following 3 basic checks before we do the comparison:

Check for nulls and return if either of the String or Pattern is null
Check if we have reached the end of string. If so, return true
If either of string or pattern are left over, return false
One case that we need to explicitly handle is when string is EMPTY and pattern is made solely of one or more *s.

Comparison:

If it is a char or ?, skip 1 ahead in both string and pattern
If it is a *, return the result of

string+1,pattern+1 - For handling multiple *s
string,pattern+1     - For handling null *
string+1,pattern     - For handling multi-char *



The actual code is pretty simple. The following code has a complexity of around 2^n for an sized string.

[code language="cpp"]
bool OnlyAskterisk(char* Pattern)
{
if (*Pattern == '\0') return true;
if (*Pattern != '*') return false;
else return OnlyAskterisk(Pattern + 1);
}

bool isMatch(char *String, char *Pattern)
{
//Base case checks
if (*Stri…

Hash Table in C++

I have implemented a simple hash-table in C++. I have used the modified version of Bernstein's Hash function for it. For more on the Bernstein's hash, read this http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx





[code language="cpp"]</pre>
class HashTable
{
typedef long long unsigned int HashValueType;
typedef int KeyType;
int BucketSize;
vector<vector<KeyType>> Buckets;

void InsertAtBucket(int ValueParam, int BucketId)
{
Buckets[BucketId].push_back(ValueParam);
}
bool FindAtBucket(int ValueParam, int BucketId)
{
if (Buckets[BucketId].size() <= 0) return false;
vector<KeyType>::iterator Ptr = Buckets[BucketId].begin();
while (Ptr != Buckets[BucketId].end())
{
if ((*Ptr) == ValueParam) return true;
Ptr++;
}
return false;
}
HashValueType HashFunction(void* Input, int Size)
{
HashValueType HValue = 0;
for (int i = 0; i < Size; i++)
HValue = (33 * HValue) + ((char*)Input)[i];
return HValue;;
}
public:

HashTable(int BucketSizePara…

Priority Queue implementation using MaxHeap

The Priority Queue with a MaxRemove() interface can be implemented using a MaxHeap which is a complete binary tree that maintains the maximum (here it would be the maximum of the priority values) of the elements that it contains at its root.

The Code is super simple and is as follows:

[code language="cpp"]

PriorityQueue(int CapacityParam)
{
Data = (int*)malloc(CapacityParam*sizeof(int));
ToH = -1;
Capacity = CapacityParam;
}

void Display()
{
cout << "\nList:\n";
for (int iter = 0; iter <= ToH; iter++)
cout << " " << Data[iter];
}

void HeapifyUp(int Position)
{
if (Position < 1) return;
if (Data[Position]>Data[(Position - 1) / 2])
{
Swap(&(Data[Position]), &(Data[(Position - 1) / 2]));
HeapifyUp((Position - 1) / 2);
}
}

bool Insert(int ParamValue)
{
if (ToH >= Capacity - 1) return false; //QueueOverflow
Data[++ToH] = ParamValue;
HeapifyUp(ToH);
return true;
}

void HeapifyDown(int Position)
{
if (2 * Position + 1 > ToH) ret…