WAP to implement stack.

#include<stdio.h>
#include<stdlib.h>
#define MAX 100
struct stack
{
int top;
int items[MAX];
};


struct stack st;
void push(struct stack *ps,int n)
{
   if(ps->top == MAX-1)
        printf("Overflow");
    else
        ps->items[++(ps->top)]=n;
}


int empty(struct stack *ps)
{
    return (ps->top == -1);
}


int pop(struct stack *ps)
{
        if(empty(ps))
        {
            printf("Underflow");
            exit(1);
        }
        else
            return ps->items[(ps->top)--];
}
int main()
{
    st.top== -1;
    int x;
    int i=0;
    push(&st,25);
    push(&st,51);
    push(&st,53);
    push(&st,51);
    push(&st,54);
    push(&st,30);
    push(&st,50);
    push(&st,70);
    push(&st,90);
    push(&st,10);
    push(&st,80);


printf("top: %d\n",st.top);
  for(i=st.top;i>0;i--){
      x=pop(&st);
    printf("%d\n",x);
  }
  return 0;
}

Write a program to find the winner of election. each similar element of an array is treated as a candidate

#include<stdio.h>
#include<stdlib.h>
void winnerSelect(int a[], int size, int max)
{
    int i;
    int maxVote,winCandidate;


    int *candidate;
    candidate=(int*)malloc(sizeof(int)*max);
    for(i=0;i<=max;i++)
    {
        candidate[i]=0;
    }
    maxVote=0;
    winCandidate=a[0];
    for(i=0;i<size;i++)
    {
        candidate[a[i]]++;
        if(candidate[a[i]]>maxVote)
            {
                maxVote=candidate[a[i]];
                winCandidate=a[i];
            }
    }
    printf("Max vote: %d\nWinner candidate : %d\n",maxVote,winCandidate);
    free(candidate);
}


int main()
{
    int a[]={10,12,11,23,23,12,12,11,11,34};
    int size = sizeof(a)/sizeof(int);
    int max=0,i;
    for(i=0;i<size;i++)
    {
        if(a[i]>max)
            max=a[i];
        else
            max=max;
    }
    winnerSelect(a,size,max);
    printf("Size: %d  Max : %d",size,max);
}

Given "a1","b1","c1","a2","b2","c2","a3","b3","c3","a4","b4","c4","a5","b5","c5" , write a program to arrange like a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 c1 c2 c3 c4 c5.........

#include <stdio.h>
int main()
{


    char *str[3*5]={"a1","b1","c1","a2","b2","c2","a3","b3","c3","a4","b4","c4","a5","b5","c5"};


    int n=3,i,j;
    for(i=1;i<=3;i++)
    {
        for(j=i-1;j<15;j++)
        {
            printf("%s ",str[j]);
            j=j+2;
        }
    }
return 0;
}

Write a program to reverse ( in place ) a string.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void reverse(char *begin, char *end)
{
    char temp;
    while(begin<end)
    {
        temp=*begin;
        *begin++ = *end;
        *end-- = temp;
    }
  /*  src=src+strlen(src)-1;
     while(*des++ = *src--);  */
}


reverseword(char *s)
{
    char *start,*temp;
    start=temp=s;
    while(*temp)
    {
        temp++;
        if(*temp==' '|| *temp=='\0')
        {
            reverse(start,temp-1);
            start=temp+1;
        }
    }
    reverse(s,temp-1);
}
int main()
{
char s[]="This is a good boy";
reverseword(s);
printf("%s\n",s);
return 0;
}

Output: boy good a is This

Write a program to evaluate post-fix expression.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAX 50
#define TRUE 1
#define FALSE 0


struct stack{
int top;
double items[MAX];
};


int digit(char symb)
{
    return (symb>='0' && symb<='9');
}


void push(struct stack *ps,double n)
{
    ps->items[++(ps->top)]=n;
}


double pop(struct stack *ps)
{
    return ps->items[(ps->top)--];
}


double oper(int symb, double op1, double op2)
{
    switch (symb)
    {
        case '+':return (op1+op2);
        case '-':return (op1-op2);
        case '*':return (op1*op2);
        case '/':return (op1/op2);
        case '%': return (fmod(op1,op2));
        default: printf("Invalid operation..."); exit(1);
    }
}


double eval(char expr[])
{
struct stack ps;
ps.top=-1;
int c,position;
double oprd1,oprd2,result;
for(position=0; ( c = expr[position] ) != '\0'; position++)
        if(digit(c))
            push(&ps,(double)(c-'0'));
        else
        {
            oprd2 = pop(&ps);
            oprd1 = pop(&ps);
            result = oper(c,oprd1,oprd2);
            push(&ps,result);
        }


return (pop(&ps));
}




int main()
{
char expr[MAX];
int position = 0;
while( (expr[position++]= getchar() )!='\n') // to read expression.
                ;
expr[--position]='\0';
printf("Origional Expression: %s\n",expr);


printf("%f\n", eval(expr));
return 0;
}

Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.

int compareTree(struct node* firstTree, struct node* SecTree){

 if (firstTree==NULL && secTree==NULL) 
     return(true);
 else if (firstTree!=NULL && secTree!=NULL) {

   return(firstTree->data == secTree->data && compareTree(firstTree->left, secTree->left) && compareTree(firstTree->right, secTree->right));
}
    else  return(false);

} 

How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. Note :: You should not use use any extra space. i.e sorting Binary Search Tree and storing the results in an array and listing out the fifth element.

int numOfNode=0;
void maxNode(tree *rootNode)
{
        if(rootNode == NULL)
                return;
        maxNode(rootNode->right);

        numOfNode++;
        if(numOfNode == 5)
                printf("%d\n",rootNode->data);

        maxNode(rootNode->left);

}

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

#include<stdio.h>
void product_digit_exceptIndex(int input[],int output[], int size)
{
    long int i, result;
    result=1;
    for(i=0;i<size;i++)
    {
        output[i]=result;
        result*=input[i];
    }
    result=1;
    for(i=size-1;i>=0;i--)
    {
        output[i]*=result;
        result*=input[i];
    }
}


int main()
{
int input[]={1,2,3,4};
int size = sizeof(input)/sizeof(int);
int output[size];
product_digit_exceptIndex(input,output,size);
int i;
for(i=0;i<size;i++)
{
    printf("%d ",output[i]);
}
return 0;
}

hints: http://placementsindia.blogspot.in/2007/12/solutions-to-few-google-top-interview.html

Write a program to construct tree from its pre-order traversal node.

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


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


struct node *newNode(int data)
{
    struct node *temp= (struct node *)malloc (sizeof(struct node));
    temp->data= data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}


struct node *construct_Tree_Util(int pre[],char preLN[],int *index_ptr,int n)
{
    int index = *index_ptr;
    if(index == n)
        return;
    struct node *temp= newNode(pre[index]);
    (*index_ptr)++;


    if(preLN[index]!='L') // L -> leaf node , if leaf node stop constructing tree ther wise construct tree.
    {
    temp->left = construct_Tree_Util(pre,preLN,index_ptr,n);
    temp->right = construct_Tree_Util(pre,preLN,index_ptr,n);
    }
 return temp;
}




struct node *construct_TRee(int pre[],char preLN[],int n)
{
    int index = 0;
    return construct_Tree_Util(pre,preLN,&index,n);
}


printINOrder(struct node *root)
{
    if(root!=NULL)
    {
    printINOrder(root->left);
    printf("%d ",root->data);
    printINOrder(root->right);
    }


}




int main()
{
struct node *root = NULL;
int pre[]={12,14,18,19,16,17,22};
char preLN[]={'N','N','L','L','N','L','L'};
int n= sizeof(pre)/sizeof(int);
root = construct_TRee(pre,preLN,n);
printINOrder(root);
return 0;
}
  


hints:
http://tech-queries.blogspot.in/2011/06/reconstruct-tree-from-pre-order.html

Write a program to permute a given string without recursion.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define display(X) printf( "\n%s", X );


/**
to remove new line from input string.
*/
void remove_newline( char* input )
{
    char* p = 0 ;
    if( p = strrchr( input, '\n' ) )
        *p = '\0' ;
}


void swap(char* a, char* b)
{
  char temp = *a;
*a = *b;
*b = temp;
}


/**
to permutate string without recursion.
*/
void wordPermutation (const char* input)
{
    int str_len = strlen(input) ;
if ( str_len == 0) /**if string is of zero length.*/
return ;
    /** this one for guard.*/
    char* p = (char*) malloc( str_len);
    {
        int j ;
        for( j = 0; j < str_len; ++j )
            p[j] = j ;
    }


 char* tmp_Buffer = (char*) malloc( str_len + 1 );
strcpy (tmp_Buffer, input);


    /** core algorithm begins */
int i = 1, j = 0;
printf( "\n%s", tmp_Buffer ) ;
while(i < str_len)
{
   p[i]--;
   j = i % 2 * p[i];
   swap( &tmp_Buffer[i], &tmp_Buffer[j] );
   display(tmp_Buffer);


   i = 1;
   while (!p[i])
   {
       p[i] = i;
       i++;
        }
   }
   /** core algorithm ends*/
   printf("\n");
   free( tmp_Buffer ) ;
   free( p ) ;
}


int main ( )
{
 char buffer[BUFSIZ]={'\0'};
printf ("\nEnter the string : \n");
fgets (buffer, BUFSIZ, stdin);
remove_newline (buffer);
wordPermutation (buffer);
return 0;
}