CareerCup

char toupper(char c)
{
     if(c>='a' && c<='z')
        return c-32;
     return c;
}

void out(char s[])
{
     int i=0,count=0;
     while(s[i]!='\0')
     {
        if(count==0)
        {
           printf("%c",toupper(s[i]));
           count++;
        }
        else
        {
            if(toupper(s[i])==toupper(s[i-1]))
               count++;
            else
            {
                printf("%d",count);
                count=0;
                i--;
            }
        }
        i++;
     }
     printf("%d\n",count);
}

for every pair of parenthesis there needs to be an operator between them.

int check(char s[])
{
     char c;
     int i=0;
     while(s[i]!='\0')
     {
        if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/' || s[i]=='(')
           push(s[i]);
        if(s[i]==')')
        {
           c=pop();
           if(c=='(' || c==')')
              return 1;
           pop();
        }
        i++;
     }
     if(ind!=0)
        return 0;
     return 1;
}

void rev(char s[])
{
     int len = strlen(s)-1;
     int i=0;
     while(i<len)
     {
         s[i]=s[i]^s[len];
         s[len]=s[i]^s[len];
         s[i]=s[i]^s[len];
         i++;
         len--;
     }
}

void convert(int n)
{
     char s[100];
     int i=0;
     while(n>=0)
     {
        s[i++]='A' + n%26;
        n= n/26-1;
     }
     s[i]='\0';
     rev(s);
     printf("%s\n",s);
}

void change(char s[])
{
     int i=0,n=0;
     while(s[i]!='\0')
         n = n + i*26 + s[i++]-'A';
     printf("%d\n",n);
}

#include<stdio.h>

int getIndex(int a[],int left,int right)
{
    if(left>right)
      return left;
    int mid=(left+right)/2;
    if(a[mid]>=a[mid-1] && a[mid]>=a[mid+1])
       return mid;
    else if(a[mid]>=a[mid-1])
       return getIndex(a,mid+1,right);
    else
       return getIndex(a,left,mid-1);
}

int main()
{
    int a[100],i,n;
    scanf("%d",&n);
    for(i=0;i<n;i++)
       scanf("%d",&a[i]);
    printf("Index of Maximum number is %d\n",getIndex(a,0,n-1));
    getch();
    return 0;
}

Use Selection Rank algoritm

Pick a random element in the array and use it as a ‘pivot’. Move all elements smaller than that element to one side of the array, and all elements larger to the other side.
»»If there are exactly i elements on the right, then you just find the smallest element on that side.
»»Otherwise, if the right side is bigger than i, repeat the algorithm on the right. If the right side is smaller than i, repeat the algorithm on the left for i – right.size().

cc book problem

Use the selection rank algorithm.

Pick a random element in the array and use it as a ‘pivot’. Move all elements smaller than that element to one side of the array, and all elements larger to the other side.
»»If there are exactly i elements on the right, then you just find the smallest element on that side.
»»Otherwise, if the right side is bigger than i, repeat the algorithm on the right. If the right side is smaller than i, repeat the algorithm on the left for i – right.size().

cc book problem

sorry my bad...following code changes the pointers without copying the data

void merge(struct node *head1,struct node *head2)
{
     struct node *start=head1;
     struct node *prev=(struct node *) malloc(sizeof(struct node));
     prev=NULL;
     struct node *temp=(struct node *) malloc(sizeof(struct node));
     while(head1!=NULL && head2!=NULL)
     {
         if(head1->val>head2->val)
         {
            if(prev==NULL)
            {
               temp=head1;
               head1=head2;
               start=head1;
               head2=head2->next;
               head1->next=temp;
            }
            else
            {
                prev->next=head2;
                temp=head2->next;
                head2->next=head1;
                head2=temp;
                prev=prev->next;
            }
         }
         else
         {
             prev=head1;
             head1=head1->next;
         }
     }
     if(head1==NULL)
        prev->next=head2;
     printlist(start);
     printf("\n");
}

int c=0;

struct tnode *addnode(struct tnode *root,int num)
{
       if(root==NULL)
       {
          root=(struct tnode *) malloc(sizeof(struct tnode));
          root->left=NULL;
          root->right=NULL;
          root->val=num;
       }
       else
       {
           if(num<root->val)
           {
              c++;
              if(root->right==NULL)
                 root->left=addnode(root->left,num);
              else
                 root->right=addnode(root->right,num);
           }
           else
              root->right=addnode(root->right,num);
       }
       return root;
}

void getinversion(int a[],int n)
{
    int i=0,count=0;
    struct tnode *root=NULL;
    root=addnode(root,a[0]);
    for(i=1;i<n;i++)
    {
       root=addnode(root,a[i]);
    }
}

void merge(struct node *head1,struct node *head2)
{
     struct node *result=NULL;
     while(head1!=NULL && head2!=NULL)
     {
          if(head1->val < head2->val)
          {
             result = addnode(result,head1->val);
             head1=head1->next;
          }
          else
          {
             result = addnode(result,head2->val);
             head2=head2->next;
          }
     }
     if(head1==NULL)
     {
        while(head2!=NULL)
        {
           result = addnode(result,head2->val);
           head2=head2->next;
        }
     }
     else
     {
         while(head1!=NULL)
        {
           result = addnode(result,head1->val);
           head1=head1->next;
        }
     }
     printlist(result);
     printf("\n");
}

struct node * reverse(struct node *head)
{
     struct node *p=(struct node *) malloc(sizeof(struct node));
     struct node *q=(struct node *) malloc(sizeof(struct node));
     struct node *temp=(struct node *) malloc(sizeof(struct node));
     temp=head;
     p=head->next;
     head->next=NULL;
     while(p!=NULL)
     {
         q=p->next;
         p->next=head;
         head=p;
         p=q;
     }
     return temp;
}

void revert(struct node *head,int k)
{
     int counter=0,found=0;
     struct node *p=(struct node *) malloc(sizeof(struct node));
     struct node *q=(struct node *) malloc(sizeof(struct node));
     struct node *start=(struct node *) malloc(sizeof(struct node));
     while(head!=NULL)
     {
          p=head;
          while(counter++<k-1 && head!=NULL)
             head=head->next;
          if(head==NULL)
             break;
          q=head->next;
          head->next=NULL;
          if(found==0)
          {
             start=head;
             found=1;
          }
          head=q;
          while(--counter>0 && head!=NULL)
             head=head->next;
          if(head==NULL)
             head=q;
          reverse(p)->next=head;
          counter=0;
          head=q;
     }
     while(start != NULL)
     {
        printf("%d\t",start->val);
        start = start->next;
     }
     printf("\n");
}

int getnumber(int n)
{
    if(n==0|| n==1)
       return -1;
    int i=9;
    int num=0;
    int pow=1;
    while(i>0)
    {
        while(n%i==0 && i>1)
        {
           num=i*pow + num;
           pow=pow*10;
           n=n/i;
        }
        i--;
    }
    if(n!=1)
       return -1;
    return num;
}

int doesrect(struct rect ra,struct rect rb)
{
    struct rect temp;
    temp.topx = (ra.topx<rb.topx)?ra.topx:rb.topx;
    temp.topy = (ra.topy<rb.topy)?rb.topy:ra.topy;
    temp.botx = (ra.botx<rb.botx)?rb.botx:ra.botx;
    temp.boty = (ra.boty<rb.boty)?ra.boty:rb.boty;
    if(((temp.botx-temp.topx)>(ra.botx-ra.topx + rb.botx-rb.topx)) || ((temp.topy-temp.boty)>(ra.topy-ra.boty + rb.topy-rb.boty)))
       return 0;
    return 1;
}

Use 2 queues:
queue1: for numbers with 0 at unit place
queue2: for numbers with 7 at unit place
get minimum of these two queues.Check if it is divisible by n. if yes return it else insert in queues as per the critetia.

int check(int a[][100],int i,int j)
{
    int count = a[i-1][j] + a[i+1][j] + a[i][j-1] + a[i][j+1];
    if(count<4)
       return 1;
    return 0;
}

void modify(int a[][100],int i,int j)
{
     if(i<0 || i>=M || j<0 || j>=N || a[i][j]==1)
        return;
     a[i][j]=1;
     modify(a,i-1,j);
     modify(a,i+1,j);
     modify(a,i,j-1);
     modify(a,i,j+1);
}

int poolpresent(int a[][100])
{
    int found=0;
    int i,j;
    for(j=0;j<N;j++)
    {
       for(i=0;i<M;i++)
       {
           if(a[i][j]==0)
           {
              found=1;
              if(i==0 || j==0)
                 return 0;
              if(check(a,i,j))
                 modify(a,i,j);
              else
                 return 0;
           }
       }
    }
    return found;
}

void swap(char *s,char *t)
{
     char temp=*s;
     *s=*t;
     *t=temp;
}

void transpose(char s1[],char s2[])
{
     int i=0,j=0,index=0;
     printf("%s\t",s1);
     while((s1[i]==s2[i]) && i<strlen(s2))
        i++;
     while(i<strlen(s2))
     {
         if(s1[i]==s2[i])
         {
            i++;
            while((s1[i]==s2[i]) && i<strlen(s2))
                  i++;
         }
         else
         {
             j=i;
             while(s1[i]!=s2[i] && j<strlen(s1)-1)
             {
                    swap(&s1[j],&s1[j+1]);
                    printf("%s\t",s1);
                    j++;
             }
         }
     }
     printf("\n");

}