Simple Thread Example

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>


void *print_message_function( void *ptr );


main()
{
     pthread_t thread1, thread2;
     char *message1 = "Thread 1";
     char *message2 = "Thread 2";
     int  iret1, iret2;


    /* Create independent threads each of which will execute function */
     iret1 = pthread_create( &thread1, NULL, print_message_function, (void*) message1);
     iret2 = pthread_create( &thread2, NULL, print_message_function, (void*) message2);

     /* Wait till threads are complete before main continues. Unless we  */
     /* wait we run the risk of executing an exit which will terminate   */
     /* the process and all threads before the threads have completed.   */
     pthread_join( thread1, NULL);
     pthread_join( thread2, NULL);


     printf("Thread 1 returns: %d\n",iret1);
     printf("Thread 2 returns: %d\n",iret2);
     exit(0);
}


void *print_message_function( void *ptr )


{
     char *message;
     message = (char *) ptr;
     printf("%s \n", message);
return 0;
}

Union can not participate in Inheritance

#include<iostream.h>

class A{
public:
int a;
};

//struct B:public A
union B:public A
{
void dis()
{
cout<<a<<endl;
}
};

int main()
{
B a;
a.dis();
return 0;
}

How to read/write using Pipe's in C

#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <stdlib.h>
int main(void)
{
        int     fd[2], nbytes;
        pid_t   childpid;
        char    string[] = "Hello, world!\n";
        char    readbuffer[80];

        pipe(fd);

        if((childpid = fork()) == -1)
        {
                perror("fork");
                exit(1);
        }

        if(childpid == 0)
        {
                /* Child process closes up input side of pipe */
                close(fd[0]);

                /* Send "string" through the output side of pipe */
                write(fd[1], string, (strlen(string)+1));
                exit(0);
        }
        else
        {
                /* Parent process closes up output side of pipe */
                close(fd[1]);

                /* Read in a string from the pipe */
                nbytes = read(fd[0], readbuffer, sizeof(readbuffer));
                printf("Received string: %s", readbuffer);
        }

        return(0);
}

Inner Class Example

#include<iostream.h>
#include<stdio.h>
class OutSide;
namespace N{
class Outer
{
public:
    Outer(){
}
public:
    class Inner{
    friend class ::OutSide;
    private:
    int x;
    };
private:
    Inner inner;
public:
static Outer& instance()
{
    static Outer *obj=new Outer();
    obj->a=10;
    return *obj;
}
friend class ::OutSide;
private:
int a;
};
}

class OutSide
{
public:
OutSide(){}
void fun()
{
N::Outer obj;
std::cout<<N::Outer::instance().inner.x<<std::endl;
std::cout<<N::Outer::instance().a<<std::endl;
}
};

int main()
{
OutSide obj;
obj.fun();
}

Binary Tree Operations

The following items are included in this Binary Search Tree example code.
It's based on the tree in the picture above.

    * Look Up (lookUp())
      One advantage of a binary search tree is that the lookup operation is fast and simple. This is particularly useful for data storage. This look up is a fast operation because we eliminate half the nodes from our search on each iteration by choosing to follow the left subtree or the right subtree. It is an O(log(n)) operation.

    * New Node (newTreeNode())
      Makes the root node.

    * Insert Node (insertTreeNode())
      Insertion begins as a search would begin; if the root is not equal to the value, we search the left or right subtrees as before. Eventually, we will reach an external node and add the value as its right or left child, depending on the node's value. In other words, we examine the root and recursively insert the new node to the left subtree if the new value is less than the root, or the right subtree if the new value is greater than or equal to the root.
      O(log(n)) operation

    * Is The Given Tree BST? (isBST())
      The code isBST() is the answer to the question:
      Given a binary tree, programmatically you need to prove it is a binary search tree.
      If the given binary tree is a binary search tree,then the inorder traversal should output the elements in increasing order.
      We make use of this property of inorder traversal to check whether the given binary tree is a BST or not.

    * Size (treeSize())
      Size of a binary tree is the total number of nodes in the tree.

    * Maximum/Minimum Depth (maxDepth()/minDepth())
      The number of nodes along the longest/shortest path from the root node down to the farthest leaf node. The maxDepth of the empty tree is 0.

    * Is balanced? (isBalanced())
      A balanced binary tree is commonly defined as a binary tree in which the height of the two subtrees of every node never differ by more than 1.
      In this example, I used maxDepth(node)-minDepth(node) <= 1

    * Minimum/Maximum Value (maxTree()/ minTree())

    * In Order Successor/Predecessor (succesorInOrder()/predecessorInOrder())
      A node which has the next higher/lower key.

    * Lowest Common Ancestor (lowestCommonAncestor())

    * Clear (Delete Node)
      O(log(n)) operation


      pre_post_in_order
    * In Order print (printTreeInOrder())
      Inorder traversal performs the operation first on the node's left descendants, then on the node itself, and finally on its right descendants. In other words, the left subtree is visited first, then the node itself, and then the node's right subtree.

    * Pre Order print (printTreePreOrder())
      Preorder traversal involves walking around the tree in a counterclockwise manner starting at the root. Sticking close to the edge, and printing out the nodes as we encounter them. For the tree shown above, the result is F B A D C E G I H.
      Traversal operation performed first on the node itself, then on its left descendants, and finally on its right descendants. In other words, a node is always visited before any of its children.

    * Post Oder print (printTreePostOrder())
      Postorder traversal performs the operation first on the node's left descendants, then on the node's right descendants, and finally on the node itself. In other words, all of a node's children are visited before the node itself.
    * Converting Binary Search Tree into an Array (TreeToArray())
      How do you put a Binary Search Tree in an array in an efficient manner.
      Hint :: If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise). It's not the most efficient way.

    * Paths from the root to leaves (printAllPaths(), pathFinder())
      Given a binary tree, print out all of its root-to-leaf paths, one per line. Uses a recursive helper to do the work.
    * Find n-th maximum node (NthMax())
      How do you find out the fifth maximum element in a Binary Search Tree in efficient manner.
      Note: You should not use any extra space. i.e., sorting Binary Search Tree and storing the results in an array and listing out the fifth element.

    * Is Sub Tree? (isSubTree())

    * Mirror Tree (mirror())
      Change a tree so that the roles of the left and right hand pointers are swapped at every node.

    * Make a new tree with minimal depth from a sorted array (createMinimalBST(())

    * Traversing level-order: Breadth-first traversal
      It's nice when we have a tree with ordering properties such as a BST or a heap. Often we're given a tree that isn't BST or a heap. For instance, we may have a tree that is a representation of a family tree or a company job hierarchy. We have to use different techniques to retrieve data from this kind of tree. One common class of problems involves searching for a particular node. There are two very common search algorithms.
      One way to search a tree is to do a breadth-first search (BFS). In a BFS we start with the root, move left to right across the second level, then move left to right across the third level, and so on. We continue the search until either we have examined all of the nodes or we find the node we are searching for. The time to find a node is O(n), so this type of search is best avoided for large trees. A BFS also uses a large amount of memory because it is necessary to track the child nodes for all nodes on a given level while searching that level.
      BreadthFirstTraversal()
    * Depth-First Search
      Another common way to search for a node is by using a depth-first search (DFS). A depth-first search follows one branch of the tree down as many levels as possible until the target node is found or the end is reached. When the search can't go down any farther, it is continued at the nearest ancestor with unexplored children. DFS has much lower memory requirements than BFS because it is not necessary to store all of the child pointers at each level. In addition, DFS has the advantage that it doesn't examine any single level last (BFS examines the lower level last). This is useful if we suspect that the node we are searching for will be in the lower levels. In this case, a DFS would usually find the target node more quickly than a BFS.
      InOrder(), PreOrder(), PostOrder()



Here is the file for Binary Tree example below: BinaryTree.cpp.

/* Binary Tree */

#include <iostream>
#include <deque>
#include <climits>
using namespace std;

struct Tree
{
char data;
Tree *left;
Tree *right;
Tree *parent;
};

Tree* lookUp(struct Tree *node, char key)
{
if(node == NULL) return node;

if(node->data == key) return node;
else {
if(node->data < key)
return lookUp(node->right, key) ;
else
return lookUp(node->left, key);
}
}

Tree* leftMost(struct Tree *node)
{
if(node == NULL) return NULL;
while(node->left != NULL)
node = node->left;
return node;
}

struct Tree *newTreeNode(int data)
{
Tree *node = new Tree;
node->data = data;
node->left = NULL;
node->right = NULL;
node->parent = NULL;

return node;
}

struct Tree* insertTreeNode(struct Tree *node, int data)
{
static Tree *p;
Tree *retNode;

if(node != NULL) p = node;

if(node == NULL)  {
retNode = newTreeNode(data);
    retNode->parent = p;
return retNode;
}
if(data <= node->data ) {
p = node;
node->left = insertTreeNode(node->left,data);
}
else {
p = node;
node->right = insertTreeNode(node->right,data);
}
return node;
}

void isBST(struct Tree *node)
{
static int lastData = INT_MIN;
if(node == NULL) return;

isBST(node->left);

/* check if the given tree is BST */
if(lastData < node->data)
lastData = node->data;
else {
cout << "Not a BST" << endl;
return;
}

isBST(node->right);
return;
}

int treeSize(struct Tree *node)
{
if(node == NULL) return 0;
else
return treeSize(node->left) + 1 + treeSize(node->right);
}

int maxDepth(struct Tree *node)
{
if(node == NULL) return 0;

int leftDepth = maxDepth(node->left);
int rightDepth = maxDepth(node->right);

return leftDepth > rightDepth ?
leftDepth + 1 : rightDepth + 1;
}

int minDepth(struct Tree *node)
{
if(node == NULL) return 0;

int leftDepth = minDepth(node->left);
int rightDepth = minDepth(node->right);

return leftDepth < rightDepth ?
leftDepth + 1 : rightDepth + 1;
}

bool isBalanced(struct Tree *node)
{
if(maxDepth(node)-minDepth(node) <= 1)
return true;
else
return false;
}

/* Tree Minimum */
Tree* minTree(struct Tree *node)
{
if(node == NULL) return NULL;
while(node->left)
node = node -> left;
return node;
}

/* Tree Maximum */
Tree* maxTree(struct Tree *node)
{
while(node->right)
node = node -> right;
return node;
}

/* In Order Successor - a node which has the next higher key */
Tree *succesorInOrder(struct Tree *node)
{
/* if the node has right child, seccessor is Tree-Minimum */
if(node->right != NULL) return minTree(node->right);

Tree *y = node->parent;
while(y != NULL && node == y->right) {
node = y;
y = y->parent;
}
return y;
}

/* In Order Predecessor - a node which has the next lower key */
Tree *predecessorInOrder(struct Tree *node)
{
/* if the node has left child, predecessor is Tree-Maximum */
if(node->left != NULL) return maxTree(node->left);

Tree *y = node->parent;
/* if it does not have a left child,
predecessor is its first left ancestor */
while(y != NULL && node == y->left) {
node = y;
y = y->parent;
}
return y;
}

Tree *lowestCommonAncestor(Tree *root, Tree *p, Tree *q)
{
Tree *left, *right;
if(root == NULL) return NULL;
if(root->left == p || root->left == q
|| root->right == p || root->right == q) return root;
else {
left = lowestCommonAncestor(root->left,p,q);
right = lowestCommonAncestor(root->right, p,q);
if(left && right)
return root;
else
return (left) ? left : right;
}
}

void clear(struct Tree *node)
{
if(node != NULL) {
clear(node->left);
clear(node->right);
delete node;
}
}
/* print tree in order */
/* 1. Traverse the left subtree.
   2. Visit the root.
   3. Traverse the right subtree.
*/

void printTreeInOrder(struct Tree *node)
{
static int lastData = INT_MIN;
if(node == NULL) return;

printTreeInOrder(node->left);
cout << node->data << " ";
printTreeInOrder(node->right);
}

/* print tree in postorder*/
/* 1. Traverse the left subtree.
   2. Traverse the right subtree.
   3. Visit the root.
*/
void printTreePostOrder(struct Tree *node)
{
if(node == NULL) return;

printTreePostOrder(node->left);
printTreePostOrder(node->right);
cout << node->data << " ";
}

/* print in preorder */
/* 1. Visit the root.
   2. Traverse the left subtree.
   3. Traverse the right subtree.
*/
void printTreePreOrder(struct Tree *node)
{
if(node == NULL) return;

cout << node->data << " ";
printTreePreOrder(node->left);
printTreePreOrder(node->right);
}

/* printing array */
void printThisPath(int path[], int n)
{
for(int i = 0; i < n; i++)
cout << (char)path[i] << " ";
cout << endl;
}

/* recursion routine to find path */
void pathFinder(struct Tree *node, int path[], int pathLength)
{
if(node == NULL) return;
path[pathLength++] = node->data;

/* Leaf node is the end of a path.
  So, let's print the path */
if(node->left == NULL && node->right == NULL)
printThisPath(path, pathLength);
else {
pathFinder(node->left, path, pathLength);
pathFinder(node->right, path, pathLength);
}
}

/*printing all paths :
Given a binary tree, print out all of its root-to-leaf
paths, one per line. Uses a recursive helper to do the work. */

void printAllPaths(struct Tree *root)
{
int path[100];
pathFinder(root,path,0);
}

bool matchTree(Tree *r1, Tree *r2)
{
/* Nothing left in the subtree */
if(r1 == NULL && r2 == NULL)
return true;
/* Big tree empty and subtree not found */
if(r1 == NULL || r2 == NULL)
return false;
/* Not matching */
if(r1->data != r2->data)
return false;
return (matchTree(r1->left, r2->left) &&
matchTree(r1->right, r2->right));
}

bool subTree(Tree *r1, Tree *r2)
{
/*Big tree empty and subtree not found */
if(r1 == NULL)
return false;
if(r1->data == r2->data)
if(matchTree(r1, r2)) return true;
return (subTree(r1->left, r2) || subTree(r1->right, r2));
}

bool isSubTree(Tree *r1, Tree *r2)
{
/* Empty tree is subtree */
if(r2 == NULL)
return true;
else
return subTree(r1, r2);
}

/* change a tree so that the roles of the left
and right hand pointers are swapped at every node */
void mirror(Tree *r)
{
if(r == NULL) return;

Tree *tmp;
mirror(r->left);
mirror(r->right);

/* swap pointers */
tmp = r->right;
r->right = r->left;
r->left = tmp;
}

/* create a new tree from a sorted array */
Tree *addToBST(char arr[], int start, int end)
{
if(end < start) return NULL;
int mid = (start + end)/2;

Tree *r = new Tree;
r->data = arr[mid];
r->left = addToBST(arr, start, mid-1);
r->right = addToBST(arr, mid+1, end);
return r;
}

Tree *createMinimalBST(char arr[], int size)
{
return addToBST(arr,0,size-1);
}

/* Breadth first traversal using queue */
void BreadthFirstTraversal(Tree *root)
{
if (root == NULL) return;
deque <Tree *> queue;
queue.push_back(root);

while (!queue.empty()) {
Tree *p = queue.front();
cout << p->data << " ";
queue.pop_front();

if (p->left != NULL)
queue.push_back(p->left);
if (p->right != NULL)
queue.push_back(p->right);
}
cout << endl;
}

/* find n-th max node from a tree */
void NthMax(struct Tree* t)
{      
static int n_th_max = 5;
static int num = 0;
if(t == NULL) return;      
NthMax(t->right);      
num++;      
if(num == n_th_max)              
cout << n_th_max << "-th maximum data is " << t->data << endl;      
NthMax(t->left);
}

/* Converting a BST into an Array */
void TreeToArray(struct Tree *node, int a[]){
static int pos = 0;
 
if(node){
TreeToArray(node->left,a);
a[pos++] = node->data;
TreeToArray(node->right,a);
      }
}

int main(int argc, char **argv)
{
char ch, ch1, ch2;
Tree *found;
Tree *succ;
Tree *pred;
Tree *ancestor;
char charArr[9]
= {'A','B','C','D','E','F','G','H','I'};

Tree *root = newTreeNode('F');
insertTreeNode(root,'B');
insertTreeNode(root,'A');
insertTreeNode(root,'D');
insertTreeNode(root,'C');
insertTreeNode(root,'E');
insertTreeNode(root,'G');
insertTreeNode(root,'I');
insertTreeNode(root,'H');

/* is the tree BST? */
isBST(root);

/* size of tree */
cout << "size = " << treeSize(root) << endl;

/* max depth */
cout << "max depth = " << maxDepth(root) << endl;

/* min depth */
cout << "min depth = " << minDepth(root) << endl;

/* balanced tree? */
if(isBalanced(root))
cout << "This tree is balanced!\n";
else
cout << "This tree is not balanced!\n";

/* min value of the tree*/
if(root)
cout << "Min value = " << minTree(root)->data << endl;

/* max value of the tree*/
if(root)
cout << "Max value = " << maxTree(root)->data << endl;

ch = 'B';
found = lookUp(root,ch);
if(found) {
cout << "Min value of subtree " << ch << " as a root is "
<< minTree(found)->data << endl;
cout << "Max value of subtree " << ch << " as a root is "
<< maxTree(found)->data << endl;
}

ch = 'B';
found = lookUp(root,ch);
if(found) {
succ = succesorInOrder(found);
if(succ)
cout << "In Order Successor of " << ch << " is "
<< succesorInOrder(found)->data << endl;
else
cout << "In Order Successor of " << ch << " is None\n";
}

ch = 'E';
found = lookUp(root,ch);
if(found) {
succ = succesorInOrder(found);
if(succ)
cout << "In Order Successor of " << ch << " is "
<< succesorInOrder(found)->data << endl;
else
cout << "In Order Successor of " << ch << " is None\n";
}

ch = 'I';
found = lookUp(root,ch);
if(found) {
succ = succesorInOrder(found);
if(succ)
cout << "In Order Successor of " << ch << " is "
<< succesorInOrder(found)->data << endl;
else
cout << "In Order Successor of " << ch << " is None\n";
}

ch = 'B';
found = lookUp(root,ch);
if(found) {
pred = predecessorInOrder(found);
if(pred)
cout << "In Order Predecessor of " << ch << " is "
<< predecessorInOrder(found)->data << endl;
else
cout << "In Order Predecessor of " << ch << " is None\n";
}

ch = 'E';
found = lookUp(root,ch);
if(found) {
pred = predecessorInOrder(found);
if(pred)
cout << "In Order Predecessor of " << ch << " is "
<< predecessorInOrder(found)->data << endl;
else
cout << "In Order Predecessor of " << ch << " is None\n";
}

ch = 'I';
found = lookUp(root,ch);
if(found) {
pred = predecessorInOrder(found);
if(pred)
cout << "In Order Predecessor of " << ch << " is "
<< predecessorInOrder(found)->data << endl;
else
cout << "In Order Predecessor of " << ch << " is None\n";
}

/* Lowest Common Ancestor */
ch1 = 'A';
ch2 = 'C';
ancestor =
lowestCommonAncestor(root,
lookUp(root,ch1), lookUp(root,ch2));
if(ancestor)
cout << "The lowest common ancestor of " << ch1 << " and "
<< ch2 << " is " << ancestor->data << endl;

ch1 = 'E';
ch2 = 'H';
ancestor =
lowestCommonAncestor(root,
lookUp(root,ch1), lookUp(root,ch2));
if(ancestor)
cout << "The lowest common ancestor of " << ch1 << " and "
<< ch2 << " is " << ancestor->data << endl;

/* print tree in order */
cout << "increasing sort order\n";
printTreeInOrder(root);
cout << endl;

/* print tree in postorder*/
cout << "post order \n";
printTreePostOrder(root);
cout << endl;

/* print tree in preorder*/
cout << "pre order \n";
printTreePreOrder(root);
cout << endl;

/* lookUp */
ch = 'D';
found = lookUp(root,ch);
if(found)
cout << found->data << " is in the tree\n";
else
cout << ch << " is not in the tree\n";

/* lookUp */
ch = 'M';
found = lookUp(root,ch);
if(found)
cout << found->data << " is in the tree\n";
else
cout << ch << " is not in the tree\n";

/* printing all paths :
Given a binary tree, print out all of its root-to-leaf
paths, one per line. Uses a recursive helper to do the work. */
cout << "printing paths ..." << endl;
printAllPaths(root);

/* find n-th maximum node */
NthMax(root);


/* convert the tree into an array */
int treeSz = treeSize(root);
int *array = new int[treeSz];
TreeToArray(root,array);
cout << "New array: ";
for (int i = 0; i < treeSz; i++)
cout << (char)array[i] << ' ';
cout << endl;
delete [] array;

/* subtree */
Tree *root2 = newTreeNode('D');
insertTreeNode(root2,'C');
insertTreeNode(root2,'E');
cout << "1-2 subtree: " << isSubTree(root, root2) << endl;

Tree *root3 = newTreeNode('B');
insertTreeNode(root3,'A');
insertTreeNode(root3,'D');
insertTreeNode(root3,'C');
insertTreeNode(root3,'E');
cout << "1-3 subtree: " << isSubTree(root, root3) << endl;

Tree *root4 = newTreeNode('B');
insertTreeNode(root4,'D');
insertTreeNode(root4,'C');
insertTreeNode(root4,'E');
cout << "1-4 subtree: " << isSubTree(root, root4) << endl;

cout << "2-3 subtree: " << isSubTree(root2, root3) << endl;
cout << "3-2 subtree: " << isSubTree(root3, root2) << endl;

/* swap left and right */
mirror(root);

/* deleting a tree */
clear(root);

/* make a new tree with minimal depth */
Tree *newRoot = createMinimalBST(charArr,9);

/* Traversing level-order.
We visit every node on a level before going to a lower level.
This is also called Breadth-first traversal.*/
cout << "printing with Breadth-first traversal" << endl;
BreadthFirstTraversal(newRoot);

return 0;
}

From the run, we get:

size = 9
max depth = 4
min depth = 2
This tree is not balanced!
Min value = A
Max value = I
Min value of subtree B as a root is A
Max value of subtree B as a root is E
In Order Successor of B is C
In Order Successor of E is F
In Order Successor of I is None
In Order Predecessor of B is A
In Order Predecessor of E is D
In Order Predecessor of I is H
The lowest common ancestor of A and C is B
The lowest common ancestor of E and H is F
increasing sort order
A B C D E F G H I
post order
A C E D B H I G F
pre order
F B A D C E G I H
D is in the tree
M is not in the tree
printing paths ...
F B A
F B D C
F B D E
F G I H
5-th maximum data is E
New array: A B C D E F G H I
1-2 subtree: 1
1-3 subtree: 1
1-4 subtree: 0
2-3 subtree: 0
3-2 subtree: 1
printing with Breadth-first traversal
E B G A C F H D I

KMP Algorithm

// C++ code of KMP String Matching Algorithm
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>

using namespace std;


void FailureFunction(char P[], int F[],int m){
 int i,j;
 F[0]=0; //  assignment is important!
 j=0;
 i=1;
 while(i<m){ // that i is less than the length of pattern
  if(P[i]==P[j]){
   F[i]=j+1;
   i++;
   j++;
  }else if(j>0){
   j=F[j-1];
  }else {
   F[i]=0;
   i++;
  }
 }
}

int KMP(char T[], char P[]){
 int i,j,F[100]; // the maximum size of Pattern String
 int m=strlen(P);
 int n=strlen(T);
 FailureFunction(P,F,m);
 i=0;
 j=0;
 while(i<n){
  if(T[i]==P[j]){
   if(j==m-1)
    return i-j; // means, in (i-j)th position, there is a match occur
   else{
    i++;
    j++;
   }
  }else if(j>0){
   j=F[j-1];
  }else{
   i++;
  }
 }
 return -1; // No match found
}


int main()
{
 char T[1000],P[100];

 while(gets(T)){
  gets(P);
  int pos=KMP(T,P);
  if(pos!=-1)
   cout<<"String Occur at position: "<<pos<<endl;
  else
   cout<<"No match found"<<endl;

 }
 
// End of main function........
return 0;
}

**********************************/

Algorithm : Kadane Algo for max sum sub array

#include<stdio.h>

int maxSubArraySum(int a[], int size)

{

   int max= 0, sum = 0;

   int i;

   for(i = 0; i < size; i++)

   {

     sum = sum + a[i];

     if(sum < 0)

        sum = 0;

     if(max < sum )

        max = sum;

    }

    return max_so_far;

}

 

int main()

{

   int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};

   int max_sum = maxSubArraySum(a, 8);

   printf("Maximum sum is %d\n", max_sum);

   getchar();

   return 0;

}