Tuesday, 31 October 2017

Super Reduced String Hacker Rank Solution in C/C++


Write a c program a string consisting of lowercase English alphabetic letters. In one operation, he can delete any pair of adjacent letters with same value. For example, string "aabcc" would become either "aab" or "bcc" after operation. To do this, he will repeat the above operation as many times as it can be performed and to find & print’s non-reducible form. Note: If the final string is empty, print Empty String.
Input: aaabccddd
Output: abd
Input: baab
Output: Empty String

Solution in C:

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main() 
{
    char* s = (char *)malloc(512000 * sizeof(char));
    scanf("%s", s);
    int l,i=0,flag;
   l=strlen(s);
   do    
   {
       flag=0;
       for(i=0;i<l-1;)
      {
           if(s[i]==s[i+1])
           {
                flag=1;
                for(int j=i;j<l-2;j++)
                     s[j]=s[j+2];
                 l=l-2;
            }
            else
                  i++;
       }
        s[l]='\0';
} while(flag==1&&l>0);
if(l!=0)
    printf("%s",s);
else  
    printf("Empty String");
    return 0;
}

Solution in C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    string s;
    cin>>s;
    for(int i=1;i<s.length();i++)
    {
        if(s[i] == s[i-1])
        {
            s.erase(i-1,2);
            i=0;
        }
    }
    if(s.length() == 0)
        cout<<"Empty String";
    else
        cout<<s;
    return 0;
}

CO4 Assignment 3rd question solution

Implement the following functions. Their meanings are given below.
a) int strCount (char *filename);
returns a count of no. of strings in a text file identified by the filename in the parameter.
b) int sentenceCount (char *filename);
returns a count of no. of sentences in the identified text file. A sentence is detected when
the last character of a word is the full stop.

Solution:


#include <stdio.h>
#include <stdlib.h>
int strCount (char *filename)
{
               FILE *fp;
               char ch;
               int wordcount=0;
               fp = fopen(filename,"r");

   // If file opened successfully, then write the string to file
               if ( fp )
               {
                              while ((ch=getc(fp)) != EOF)
                                                            if (ch == ' ' || ch == '\n') { ++wordcount; }
               }
               else
    {
               printf("Failed to open the file\n");
    }

    printf("No. of Words : %d \n", wordcount+1);
    fclose(fp);
}
int sentenceCount (char *filename)
{
               FILE *fp;
               char ch;
               int sentenceCount=0;
               fp = fopen(filename,"r");

   // If file opened successfully, then write the string to file
               if ( fp )
               {
                              while ((ch=getc(fp)) != EOF)
                                                            if (ch == '.') { ++sentenceCount; }
               }
               else
    {
               printf("Failed to open the file\n");
    }

    printf("No. Of sentences : %d \n", sentenceCount);
    fclose(fp);
              
}
int main()
{
               char filename[100];
               printf("Enter a filename :");
               gets(filename);
               strCount(filename);
               sentenceCount (filename);
}

Outputs:

CO4 Assignment Second question solution

There are 100 records present in a file with the following structure:
struct date
{
int d, m, y ;
} ;
struct employee
{
int empcode[6] ;
char empname[20] ;
struct date join_date ;
float salary ;
} ;
Write a program to read these records, arrange them in ascending order of join_date and write them in to a target file.

Solution:



#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
main()
{
struct doj
{
int day,mon, year;
};
struct employee
{
int num;
char name[30];
struct doj d;
float salary;
};
struct employee s[100],temp;
int n,i,j,p;
FILE *fp,*fp1;
fp=fopen("emp.txt","a+");
fp1=fopen("target.txt","a+");
printf("\n Enter number of employees");
scanf("%d",&n);
for(i=0;i<n;i++)
{
               printf("\n Enter Number");
               scanf("%d",&s[i].num);
               printf("\n Enter Name");
               scanf("%s",s[i].name);
               printf("\n Enter Date of joining(dd-mm-yy");
               scanf("%d%d%d",&s[i].d.day,&s[i].d.mon,&s[i].d.year);
               printf("enter salary");
               scanf("%f",&s[i].salary);
               fprintf(fp,"%d\t%s\t%d-%d-%d\t %f\n",s[i].num,s[i].name,s[i].d.day,s[i].d.mon,s[i].d.year,s[i].salary);
}

for(p=0;p<n-1;p++)
{
               for(j=0;j<n-p-1;j++)
               {
                              if(s[j].d.year>s[j+1].d.year||s[j].d.year==s[j+1].d.year&&s[j].d.mon>s[j+1].d.mon||s[j].d.year==s[j+1].d.year&&s[j].d.mon==s[j+1].d.mon&&s[j].d.day>s[j+1].d.day)
                              {
                                             temp=s[j];
                                             s[j]=s[j+1];
                                             s[j+1]=temp;
                              }
               }
}
for(i=0;i<n;i++)
fprintf(fp1,"%d\t%s\t%d-%d-%d\t %f\n",s[i].num,s[i].name,s[i].d.day,s[i].d.mon,s[i].d.year,s[i].salary);
fclose(fp);
fclose(fp1);
getch();
}

Monday, 30 October 2017

Trees : non linear data structure: Basic Terminology and introduction



Trees: Linked Lists, stacks, and queues, are all linear structures:
In Linked Lists, stacks, and queues, one item follows another.
But Trees are non-linear structure:
  • More than one item can follow another.
  • The number of items that follow can vary from one item to another.
Trees have many uses:
  • representing family trees
  • represents hierarchical relationship


  • each letter represents one node
  • the lines drawn from one node to another are called edges
  • the topmost node is the root (node A)
  • the bottom nodes  are the leaves (nodes D, E, F)
  • E and F are siblings as they have a common parent i.e, C . (B,I,C are also siblings)
A path is  sequence of (zero or more) connected nodes; for example, here are 2 of the paths in the tree shown below
The length of a path is the number of nodes in the path, e.g.:
in A->B->D in the above figure, the length of the path is 2
and in C->E , the length of the path is 1


The depth of a node is the number of edges from the node to the tree's root node. A root node will have a depth of 0.  

The height of a node is the number of edges on the longest path from the node to a leaf. A leaf node will have a height of 0
















 Given two connected nodes like this:
Node A is called the parent, and node B is called the child.
The descendants of a node n are all nodes reachable from n (n's children, its children's children, etc.).

  

 A subtree of a given node includes one of its children and all of that child's descendants.

Degree of a node:  is the number of children the node has. Leaf nodes has zero degree
Degree of a tree is the maximum degree  a node has in the tree.
The entire tree is levelled in such a way that the root node is at level 0, then its immediate childres are at level1 and so on
Binary tree: is a tree in which each node has 0 ,1 or 2 children.
Types of binary tree:
1. Full binary tree: degree of every node is 2 except the leaf node and all the leaf nodes must be at same level.
2. complete binary tree: A complete binary tree is a binary tree in which every level, except possibly the last level is completely filled and the filling is done in the order of root, left, right. Root is filled first and then its left child and then its right child and so on.

Tree traversals:
1. inorder : left, root, right
2. preorder: root, left , right
3. post order: left, right, root

Q) draw all possible binary trees with 3 nodes.


Q) draw all possible binary trees with 4 nodes: