Tuesday 17 February 2015

Implementing Priority Queue in C++



Priority Queue is a data structure which maintains a set S of elements with priorities associated with it.Lower the value higher the priority is.
It have broad applications in computer science in engineering ,i.e process scheduling and many graph algorithms .
Priority queues are usually implemented with heap data structure. 

Heaps have below 2 properties :
1. Every Element i in the heap will be having at most 2 child’s at index i*2 and i*2+1
2. Every child of the element have higher priority value then the parent.

Heaps provide access to highest priority element in O(1) time . while insertion and deletion are log(N) time operations.

Implementation : 
To implement priority queue we can use 2 arrays , one to hold elements while other for priorities.
So, parent of any element can be accessed in constant time by index  (i/2) .
And left child can be access in constant time as i*2 for element with index i in array .
Likewise right child can be accessed in constant time as i*2+1 for  element with index i in array .


Our priority Queue will provide 3 operations :

1. Insert Elements in Priority Queue in O(long N) time.
2. get minimum element from Priority Queue in O(1) time .
3. get Minimum element and delete it from priority queue in O(log N) time .


Lets Implement these operations in C++ 

Consider we are given input in the array with priorities as bellow :

input [] = {5,2,10,3,8,1} 

And data associated with these priorities are :

data = {5,7,11,18,9,20}

1. Insert Element in priority queue

Consider input is coming from input array as defined earlier.

since initially our queue is empty first element will be inserted as it is 
So after inserting 1st element our Priority queue will be  :

5

Now consider inserting next element (2) .it will be inserted at left child of 5 , but since it violets heap property (every child of element can have at least priority equal to parent ) here 2<5 , so we will have to swap these two priorities , Our priority queue will look like :

2
  /
5


Now consider inserting next element 10 , it place to be inserted is right child of 2 . It doesn’t violets heap property so it will be inserted as it is .

2
  /     \
5 10

Now consider inserting next element 3 . It violets heap property since its place in queue is left child of 5 . Here 3<5 , so violating heap property 

whenever we will come across any heap violation we will recursively swap elements with parent until no heap violations are there.
Resulting heap will be :

2
  /     \
3 10
 /
5

Routine used to fix heap property violation :

Heapify_Up(input,i)   //Here input is priority array
let j = i/2
if input[i] < input[j] then
swap input[i] and input[j]
Heapify_Up(input,j)
          end if
end

2. Get minimum element from priority queue 

Return root element of heap.



3. Complete implementation of Priority Queue in C++ 

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cstdlib>
#include <cmath>

template <typename T ,typename P >
class priority_queue
{
public:
    void insert(T element,P priority)
    {
        _data.push_back(element);
        _priority.push_back(priority);
        heapify_up((int)_data.size()-1);
    }
    T getMin(void);
    T extractMin(void);
private:
    std::vector<T> _data;
    std::vector<P> _priority;
    void heapify_up(int index);
    void heapify_down(int index);
};

template <typename T ,typename P >
void priority_queue<T,P>::heapify_up(int index)
{
    if (index == 0)
    {
        return;
    }
    else
    {
        int j = index/2;
        if (_priority[index]<_priority[j])
        {
            int temp = _data[index]; //Swap Data
            _data[index] = _data[j];
            _data[j] = temp;
            
            temp = _priority[index]; //Swap Priorities
            _priority[index] = _priority[j];
            _priority[j] = temp;
            heapify_up(j);
        }
    }
}

template <typename T ,typename P >
void priority_queue<T,P>::heapify_down(int index)
{
    size_t len = _data.size()-1;
    int j = 0;
    if (index*2 > len)
    {
        return;
    }
    else if(index*2 <len)
    {
        int left = index*2;
        int right = index*2 +1;
        if (_priority[left]<=_priority[right])
        {
            j = left;
        }
        else
        {
            j = right;
        }
    }
    else if(index*2 == len)
    {
        j = 2*index;
    }
    
    if (_priority[j] <_priority[index])
    {
        int temp = _data[index]; //Swap Data
        _data[index] = _data[j];
        _data[j] = temp;
        
        temp = _priority[index]; //Swap Priorities
        _priority[index] = _priority[j];
        _priority[j] = temp;
        heapify_down(j);
    }
}

template <typename T ,typename P >
priority_queue<T,P>::getMin(void )
{
    return _data[0];
}

template <typename T ,typename P >
priority_queue<T,P>::extractMin(void )
{
    T result = _data[0];
    
    int temp = _data[0];
    _data[0] = _data[_data.size()-1];
    _data[_data.size()-1] = _data[0];
    
    temp = _priority[0];
    _priority[0] = _priority[_priority.size()-1];
    _priority[_priority.size()-1] = _priority[0];
    
    _data.pop_back();
    _priority.pop_back();
    heapify_down(0);
    
    return result;
}

int main(void)
{
    priority_queue<int,int> queue;
    
    queue.insert(5, 5);
    queue.insert(7, 2);
    queue.insert(11, 10);
    queue.insert(18, 3);
    queue.insert(9, 8);
    queue.insert(20, 1);
    
    std::cout<<queue.extractMin();
    std::cout<<queue.extractMin();
    
    return 0;
}





Sunday 24 August 2014

Insert Sorted Array in Balanced Binary Search Tree


Binary Search Tree :
It is tree which have one unique root node and all other nodes have at most two children’s ,with restriction that left children must be less than node and right children must be equal to or greater than node .

For Example :

                                   10
                                 /     \
                               8      12
                             /   \
                           7      9
          
                     Fig 1.0


In Figure 1.0 node with value 10 is root of tree.node with value 8 is its left child and node with value 12 is its right child.


Binary search Tree Insertion :
To insert any node in binary search tree , first we will define tree node structure .Lets assume our binary search tree will contain only integer values .We can then define tree node like this :

struct NODE
{
    int data;
    struct NODE *left;
    struct NODE *right;
};

here "data" is value to be stored in node , while pointers left and right are pointing to left subtree and right subtree respectively.

Binary search tree insertion will consists of accounting two cases , first if tree is empty ,other one if tree already have some node .

Lets take first case , if tree is empty :
In this case,all we need to do is create new node and make this node as root of tree.

struct NODE *root;
root = new struct NODE;
root->data = 10;
root->left = root->right = NULL;


Second case , If tree already contains some node :
In this case , we will recursively find position of node to be inserted .If this node to be inserted is less than root node , we will try to find recursive suitable position in left subtree of root node , else we will try to find suitable position recursively in right subtree.

Consider fig .1.0 Above , and we want to insert node with value 5 into it .
First we will compare it with root node which have value 10 , since 5 <10 , we will search left subtree recursively.
Next we will compare it with 8 , since 5<8 , we will search in left subtree of 8 , which here found to be 7 . In our  last comparision we will compare it with 7 . As 5<7 .
we will insert node with value 5 as left child of node with value 7.
Result of this insertion will be :


                                    10
                                 /     \
                               8      12
                             /   \
                           7      9
                         /
                        5

                     Fig 2.0

Complete function to insert a node in binary search tree :

struct NODE* insertNode(struct NODE *root,int val)
{
    if(root == NULL)
    {
        root = new struct NODE;
        root->data = val;
        root->left = root->right = NULL;
        return root;
    }
    else
    {
        if(val<root->data)
        {
             root->left = insertNode(root->left,val);
             return root;
        }
        else 
        {
             root->right = insertNode(root->right,val);
             return root;
        }
    }
}


To call this insertion function,use below statements in your code :
struct NODE*root = NULL;
root = insertNode(root,10);


In order Traversal of BST:
Now that we have inserted nodes in our binary search tree , we must be having some way to view tree (i.e print nodes in any specific order) .

There are tree ways to traverse a binary search :
1)Pre Order traversal (Node , Left Child , Right child)
2)Post Order traversal (Left Child,Right child, Node)
3)In Order traversal (Left child,Node ,Right child) - Print in sorted order

Consider Fig 2.0 Again :

                                   10
                                 /     \
                               8      12
                             /   \
                           7      9
                         /
                        5

Pre Order Traversal : 10,8,7,5,9,12
Post Order Traversal : 5,7,9,8,12,10
In Order Traversal : 5,7,8,9,10,12

Traditionally In Order traversal is used to display a tree , I will do the same :
Recursively print call left subtree , print node then recursively call right subtree.

Complete function to print nodes in In Order Traversal :

void printTree(struct NODE* root)
{
    if(root != NULL)
    {
        printTree(root->left);
        std::cout<<root->data<<std::endl;
        printTree(root->right);
    }
}

Level Order Traversal Of BST :
As we are trying to solve problem of inserting sorted array into balanced binary search tree ,Printing nodes in In Order traversal wont make , a guarantee that we have indeed inserted nodes in balanced BST , since In Order traversal always prints nodes in sorted ascending order.

To Overcome this situation , I will be printing nodes in level order traversal .Print Node level by level , start from level 0 (i.e Root Node)

Consider Fig 2.0 Again :

                                   10
                                 /     \
                               8      12
                             /   \
                           7      9
                         /
                        5

Level Order traversal of this tree  would be :

Level Order Traversal : 10,8,12,7,9,5

To accomplish this , idea I have used , is to use a queue . First insert root node in queue , then insert left child of it in queue , and insert right child of it in queue .
Loop while queue is not empty remove front element from queue , print it , and insert left and right children into queue .

See the complete Function to print tree in Level Order :

void printLevelOrder(struct NODE* root)
{
    std::queue<struct NODE *> levelOrderQueue;
    
    if(root == NULL)
        return;
    levelOrderQueue.push(root);
    while(!levelOrderQueue.empty())
    {
        struct NODE * node = levelOrderQueue.front();
        levelOrderQueue.pop();
        std::cout<<node->data<<std::endl;
        if(node->left != NULL)
            levelOrderQueue.push(node->left);
        if(node->right != NULL)
            levelOrderQueue.push(node->right);
    }
}

Insert Sorted Array into Balanced Binary search tree:
Here comes main topic of discussion. Its tricky and short part .The idea is to recursively find middle element of array , and insert it into binary search tree , using above function.

Lets say we have sorted array :
int arr[] = {1,2,3,4,5,6,7};

and we want to insert it into balanced binary search tree .
recursively find middle element of array and insert it into BST.Here middle element is calculated as
int mid = (low+high)/2.

Where low is lower bound and high is upper bound of array .
So in our case low is 0 and high is  6  (In C++ upper bound of array is size of array -1)

so mid will be 3.

So root of our tree would be : arr[3] , which turns out to be : 4

Now recursively devide the array in 2 subarrays : array from index low to mid-1 and array from index mid+1 to high . Apply the same procedure of finding middle element and insert that into tree.

Resulting tree would be :

                                     4
                                   /   \
                                  2    6
                                /   \   /  \
                              1    3 5   7

                           Fig 3.0

Wow what a balanced binary search tree.

Complete Function to insert sorted array into balanced binary search tree : 

struct NODE* getBalancedBinaryTreeFromSortedArray(struct NODE*root,int* arr,int low,int high)
{
    
    if(low<=high)
    {
        int mid = (int)((low+high)/2);
        root = insertNode(root,arr[mid]);
        root = getBalancedBinaryTreeFromSortedArray(root,arr,low,mid-1);
        root = getBalancedBinaryTreeFromSortedArray(root,arr,mid+1,high);
    }

    return root;
}

Here int *arr is sorted array, low is lower bound of array (i.e 0) and high is upper bound of array ( which is size of array  -1)

Use below statements to use it in your code :

int arr[] = {1,2,3,4,5,6,7};
root = getBalancedBinaryTreeFromSortedArray(root,arr,0,6);

For printing node of tree :
printLevelOrder(root);


Complete Working Program in C++ :

/**
* Author : Nitendra Bhosle
* Program : To Insert sorted array into balanced binary search tree
**/

#include <iostream>
#include <queue>

using namespace std;

struct NODE
{
    int data;
    struct NODE *left;
    struct NODE *right;
};

struct NODE* insertNode(struct NODE *root,int val)
{
    if(root == NULL)
    {
        root = new struct NODE;
        root->data = val;
        root->left = root->right = NULL;
        return root;
    }
    else
    {
        if(val<root->data)
        {
             root->left = insertNode(root->left,val);
             return root;
        }
        else 
        {
             root->right = insertNode(root->right,val);
             return root;
        }
    }
}

void printLevelOrder(struct NODE* root)
{
    std::queue<struct NODE *> levelOrderQueue;
    
    if(root == NULL)
        return;
    levelOrderQueue.push(root);
    while(!levelOrderQueue.empty())
    {
        struct NODE * node = levelOrderQueue.front();
        levelOrderQueue.pop();
        std::cout<<node->data<<std::endl;
        if(node->left != NULL)
            levelOrderQueue.push(node->left);
        if(node->right != NULL)
            levelOrderQueue.push(node->right);
    }
}

void printTree(struct NODE* root)
{
    if(root != NULL)
    {
        printTree(root->left);
        std::cout<<root->data<<std::endl;
        printTree(root->right);
    }
}

struct NODE* getBalancedBinaryTreeFromSortedArray(struct NODE*root,int* arr,int low,int high)
{
    
    if(low<=high)
    {
        int mid = (int)((low+high)/2);
        root = insertNode(root,arr[mid]);
        root = getBalancedBinaryTreeFromSortedArray(root,arr,low,mid-1);
        root = getBalancedBinaryTreeFromSortedArray(root,arr,mid+1,high);
    }

    return root;
}

int main()
{
   struct NODE*root = NULL;
   
   /*root = insertNode(root,10);
   root = insertNode(root,5);
   root = insertNode(root,1);
   root = insertNode(root,7);
   root = insertNode(root,3);
   root = insertNode(root,2);
   root = insertNode(root,12);
   root = insertNode(root,11);
   root = insertNode(root,13);*/
   
   int arr[] = {1,2,3,4,5,6,7};
   
   root = getBalancedBinaryTreeFromSortedArray(root,arr,0,6);
   
   //printTree(root);
   
   std::cout<<"\nLevel Order"<<std::endl;
   
   printLevelOrder(root);
   
   return 0;
}








Saturday 14 December 2013

Program to Convert Decimal Numbers to Binary


#include <iostream>
#include <string>

std::string convertTobinary(long num)
{
std::string binaryVal = "";

if(num == 0) return "0";

while(num != 0)
{
if(num %2 == 0)
binaryVal = "0" + binaryVal;
else
binaryVal = "1" + binaryVal;
num /= 2;
}

return binaryVal;
}

int main(int argc, char **argv)
{
std::cout<<"\n binaryVal : "<<convertTobinary(100);
return 0;
}

Sunday 1 December 2013

Longest Common Sub-Sequence implementation in C++


Problem : Given two sequence of elements (usually characters), find the longest subsequence present in both of them. A subsequence is a sequence that appears in the same order,as appeared in original sequence's  .

Example : Strings  "abc","abd","cde" are sub-sequence of string "abcdefghi".

Solution :  With dynamic programming we can solve this problem in O(m*n) time , where m is length of first sequence and n is length of second sequence.


C++ Solution  :

char *get_lcs(char *first_str,char *sec_str,int str_len1,int str_len2)
{
 int m,n,i,j;
 char temp_lcs[100][100];
 int temp_len_lcs[100][100];
 char ret_str[100];

 memset(temp_lcs,'\0',sizeof(temp_lcs));
 memset(temp_len_lcs,0,sizeof(temp_len_lcs));

 for(m = 0;m<str_len1;m++)
 {
  temp_len_lcs[m][0] = 0;
 }

 for(n = 0;n<str_len2+1;n++)
 {
  temp_len_lcs[0][n] = 0;
 }

 for(m = 0;m<str_len1;m++)
 {
  for(n = 1;n<str_len2+1;n++)
  {
   if(first_str[m] == sec_str[n-1])
   {
    temp_len_lcs[m][n] = temp_len_lcs[m-1][n-2] + 1;
    temp_lcs[m][n-1] = '=';
   }
   else
   {
    if(temp_len_lcs[m-1][n-1] >= temp_len_lcs[m][n-2])
    {
     temp_len_lcs[m][n-1] = temp_len_lcs[m-1][n-1];
     temp_lcs[m][n-1] = '+';
    }
    else
    {
     temp_len_lcs[m][n-1] = temp_len_lcs[m][n-2];
     temp_lcs[m][n-1] = '-';
    }
   }
  }
 }


 memset(ret_str,'\0',sizeof(ret_str));

 i = m;
 j = n;

 while(1)
 {
  if(i == 0 || j == 0)
  {
   break;
  }
  else
  {
   if(temp_lcs[i-1][j-1] == '=')
   {
    i--;
    j--;
    strncat(ret_str,(first_str+i),1);
 
   }
   else if(temp_lcs[i-1][j-1] == '+')
   {
    --i;
   }
   else
   {
    --j;
   }
  }
 }

 return strrev(ret_str);

}


Usage :
Call this function from main  like this

int main(void)
{
 char first_str[100];
 char sec_str[100];
 char lcs[100];

 memset(first_str,'\0',sizeof(first_str));
 memset(sec_str,'\0',sizeof(sec_str));
 memset(lcs,'\0',sizeof(lcs));

 scanf("%s",first_str);
 scanf("%s",sec_str);

 strcpy(lcs,get_lcs(first_str,sec_str,strlen(first_str),strlen(sec_str)));
 std::cout<<lcs<<"\n";

 int a;
 std::cin>>a;
 return 0;
}

Quick sort Implementation in C++


Quick Sort : It is sorting algorithm which takes , O(n*2) time in worst case ,but usually its faster than O(NlogN) algorithms on average case.

It uses , devide and conquer algorithm.
Souce Code : C++ Implementation :

#include <iostream>
#include <cstdio>

using namespace std;

int q_partition(int arr[],int p,int r)
{
    int x,i,j,temp;
   
    x = arr[r];
    i = p-1;
   
    for(j = p;j< (r);j++)
    {
          if(arr[j] <= x)
          {
             i++;
             temp = arr[i];
             arr[i] = arr[j];
             arr[j] = temp;
          }
    }
    temp = arr[i+1];
    arr[i+1] = arr[r];
    arr[r] = temp;
   
    return ++i;
}

void q_sort(int arr[],int p,int r)
{
     if(p < r)
     {
          int q = q_partition(arr,p,r);
          q_sort(arr,p,q-1);
          q_sort(arr,q+1,r);
     }
}

int main(void)
{
    int arr[] = {2,5,1,9,3};
    int i;
   
   
    q_sort(arr,0,4);
    for(i = 0;i<5;i++)
      cout<<"\t"<<arr[i];
   
    int halt;
    cin>>halt;
   
    return 0;
}

Recusive NBit- GrayCode Generator in C++


While Reading tutorials on, one of the , educational institutes website , I have found this interesting property about Gray codes , so i tried implementing it  in C++.

Gray code : The Gray code , is a binary numeral system where two successive values differ in only one bit. It is a non-weighted code.
The reflected binary code was originally designed to prevent spurious output from electromechanical switches. Today, Gray codes are widely used to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.
For More Information please refer wiki : http://en.wikipedia.org/wiki/Gray_code

Recursive Algorithm :
1. Write down the Gray code for N – 1 bits.
2. Copy that same list in reverse order below the original one.
3. Add a 0 bit in front of the codings in the original half of the list and a 1 bit in
front of those in the reversed copy.

C++ Code :

/*
* Author :  Nitendra Bhosle
*/
#include <iostream>
#include <vector>
#include <string>

void nBitGrayCodeGenerator(int n,std::vector<std::string>& resultVec)
{
 //Simple Case
 if(n ==1)
 {
  std::string zero = "0";
  std::string one = "1";
  resultVec.push_back(zero);
  resultVec.push_back(one);
 }
 else //Recursively solve problem by deviding it in simpler problems
 {
  std::vector<std::string> temp ;
  nBitGrayCodeGenerator(n-1,temp);

  for(int i = 0;i<temp.size();++i)
  {
   std::string res = "0"+temp[i];
   resultVec.push_back(res);
  }

  for(int i = temp.size()-1;i>=0;--i)
  {
   std::string res = "1"+temp[i];
   resultVec.push_back(res);
  }
 }
}

int main(void)
{
 std::vector<std::string> resultVec;

 nBitGrayCodeGenerator(4,resultVec);

 for(int i=0;i<resultVec.size();++i)
 {
  std::cout<<"\n"<<resultVec[i];
 }

 int halt;
 std::cin>>halt;

 return 0;
}



Result :  5-Bit GrayCode , generated from the above program

00000
00001
00011
00010
00110
00111
00101
00100
01100
01101
01111
01110
01010
01011
01001
01000
11000
11001
11011
11010
11110
11111
11101
11100
10100
10101
10111
10110
10010
10011
10001
10000

Friday 29 November 2013

Facebook Hacker Cup 2014 – Qualification Round Problem 'Square Detector'


This is easiest problem of this year's hackercup and straightforward to solve  :)

Problem Statement :

You want to write an image detection system that is able to recognize different geometric shapes. In the first version of the system you settled with just being able to detect filled squares on a grid.

You are given a grid of N×N square cells. Each cell is either white or black. Your task is to detect whether all the black cells form a square shape.

Input
The first line of the input consists of a single number T, the number of test cases.

Each test case starts with a line containing a single integer N. Each of the subsequent N lines contain N characters. Each character is either "." symbolizing a white cell, or "#" symbolizing a black cell. Every test case contains at least one black cell.

Output
For each test case i numbered from 1 to T, output "Case #i: ", followed by YES or NO depending on whether or not all the black cells form a completely filled square with edges parallel to the grid of cells.

Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 20

Example
Test cases 1 and 5 represent valid squares. Case 2 has an extra cell that is outside of the square. Case 3 shows a square not filled inside. And case 4 is a rectangle but not a square.

Sample Input :

5
4
..##
..##
....
....
4
..##
..##
#...
....
4
####
#..#
#..#
####
5
#####
#####
#####
#####
.....
5
#####
#####
#####
#####
#####


Sample Output :

Case #1: YES
Case #2: NO
Case #3: NO
Case #4: NO
Case #5: YES

Solving problem :
There are few observations to start with
1. If number of black cells in the given input is not perfect square then print "NO".
2. If black cell found at row index i and column index j , and suppose x is square root of number of black cells and size is size of grid then , If (size-i) < x or (size-j) < x print "NO"

Solution in C++ :

/* Author : Nitendra Bhosle
 * Date : 22/11/2013
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <cmath>

bool isPerfectSquare(int num)
{
int squareArray[] = { 1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400 };

for(int i = 0;i<20;++i)
{
if(num == squareArray[i])
return true;
}

return false;
}

std::string isSquare(const std::vector<std::string>& inputVec)
{
int numOfBalckCells = 0;
int size = inputVec.size();

for(int i=0;i<size;++i)
{
//std::cout<<"\n"<<inputVec[i];
for(int j=0;j<size;++j)
{
if(inputVec[i][j] == '#')
{
++numOfBalckCells;
}
}
}

//std::cout<<"\n numOfBalckCells "<<numOfBalckCells;
if(!isPerfectSquare(numOfBalckCells))
return "NO";

int squaRoot = (int)std::sqrt((double)numOfBalckCells);
//std::cout<<"\n squaRoot "<<squaRoot;
for(int i=0;i<size;++i)
{
for(int j=0;j<size;++j)
{
if(inputVec[i][j] == '#')
{
//std::cout<<"\n i : "<<i<<"\t j : "<<j<<"\t size : "<<size<<"\t squaRoot : "<<squaRoot;
if(((size-i) < squaRoot) || ((size-j) < squaRoot))
return "NO";

for(int l=0;l<squaRoot;++l)
{
for(int m=0;m<squaRoot;++m)
{
//std::cout<<"\n inputVec[i+l][j+m] : "<<inputVec[i+l][j+m];
if(inputVec[i+l][j+m] != '#')
return "NO";
}
}
//Everything Currect
return "YES";
}
}
}
return "YES";
}

int main(int argc, char **argv)
{
int T,N;
char inpArray[30];
std::vector<std::string> inputVec;

std::cin>>T;
for(int testCase=1;testCase<=T;testCase++)
{
std::cin>>N;
inputVec.clear();
for(int i=0;i<N;++i)
{
memset(inpArray,'/0',sizeof(inpArray));
fscanf(stdin,"%s",inpArray);
inputVec.push_back(inpArray);
}

std::cout<<"Case #"<<testCase<<":"<<isSquare(inputVec)<<std::endl;
}
return 0;
}