Write an efficient function that deletes all the characters from string src which are given in string remove. Your function should not change the relative order of characters in src. What are the time and space complexities of your solution?

consider function type 

void RemoveChar(char [] src, char []remove)

Input: Gopipodila<-src 

            ila <-remove 

 Output: Goipodi <-src

Algorithm:

im using hashtable and for storing data from remove string then for every charcter in src string whether charecter is present in hash table or not if it is avilable skip that charcter 

Code: 

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define INIT_SIZE 26
#define LF 10
struct ListNode
{
 int data;
 struct ListNode *next;
};
struct HashTbl
{
 int size;
 int nelement;
 struct ListNode **array;
};
struct HashTbl* createHashTable();
int add(struct HashTbl*,int);
int ListInsert(struct ListNode*,int);
void Rehash(struct HashTbl*);
void insert(struct ListNode*,struct ListNode*);
int find(struct HashTbl*,int);
int ListFind(struct ListNode*,int);
int removelst(struct HashTbl*,int);
int ListDelete(struct ListNode*,int);

struct HashTbl* createHashTable()
{
 int i;
 struct ListNode *temp;
 struct HashTbl *htbl;
 htbl=(struct HashTbl*) malloc(sizeof(struct HashTbl));
 htbl->nelement=0;
 htbl->size=INIT_SIZE;
 htbl->array=(struct ListNode**) malloc(INIT_SIZE * sizeof(struct ListNode*));
 for(i=0;i<INIT_SIZE;i++)
 {
  temp=(struct ListNode*) malloc(sizeof(struct ListNode));
  temp->next=NULL;
  htbl->array[i]=temp;
 }
 return(htbl);
}

int add(struct HashTbl *htbl,int key)
{
 int pos;
 if((htbl->nelement)/(htbl->size)>LF)
  Rehash(htbl);
 pos=hash(key,htbl->size);
 if(ListInsert(htbl->array[pos],key))
 {
  (htbl->nelement)++;
  return(1);
 }
 else
  return(0);
}
int hash(int k,int s)
{
 return(k%26);
}

int ListInsert(struct ListNode *p,int k)
{
 struct ListNode *current,*temp;
 current=p;
 while(current->next!=NULL)
 {
  if(current->data==k)
   return(0);
  current=current->next;
 }
 if(current->data==k)
  return(0);
 temp=(struct ListNode*) malloc(sizeof(struct ListNode));
 temp->data=k;
 temp->next=NULL;
 current->next=temp;
 return(1);
}

void Rehash(struct HashTbl *htbl)
{
 int i,newsize,pos;
 struct ListNode *temp,**newarray,*current;
 printf("\nrehashing\n");
 newsize=htbl->size*2;
 newarray=(struct ListNode**) malloc(newsize * sizeof(struct ListNode*));
 for(i=0;i<newsize;i++)
 {
  temp=(struct ListNode*) malloc(sizeof(struct ListNode));
  temp->next=NULL;
  newarray[i]=temp;
 }
 for(i=0;i<htbl->size;i++)
 {
  for(current=htbl->array[i];current->next!=NULL;)
  {
   temp=current->next;
   current->next=temp->next;
   pos=hash(temp->data,newsize);
   insert(newarray[pos],temp);
  }
 }
 htbl->size=newsize;
 free(htbl->array);
 htbl->array=newarray;
}

void insert(struct ListNode *a,struct ListNode *t)
{
 t->next=a->next;
 a->next=t;
}

int find(struct HashTbl *htbl,int key)
{
 int pos;
 pos=hash(key,htbl->size);
 return(ListFind(htbl->array[pos],key));
}

int ListFind(struct ListNode *a,int k)
{
 struct ListNode *current=a->next;
 while(current!=NULL)
 {
  if(current->data==k)
   return(1);
  current=current->next;
 }
 return(0);
}

int removelst(struct HashTbl *htbl,int key)
{
 int pos;
 pos=hash(key,htbl->size);
 return ListDelete(htbl->array[pos],key);
}

int ListDelete(struct ListNode *a,int k)
{
 struct ListNode *current,*prev;
 prev=a;
 current=a->next;
 while(current!=NULL)
 {
  if(current->data==k)
  {
   prev->next=current->next;
   free(current);
   return(1);
  }
  current=current->next;
  prev=prev->next;
 }
 return(0);
}

void main()
{
 int i,l=0;
 char a[20],b[5],c[20];
 struct HashTbl *head;
 head=createHashTable();
 printf("\nHash Table created\n");
 printf("\nEnter string A:");
 scanf("%s",a);
 for(i=0;i<strlen(a);i++)
  add(head,a[i]);
 printf("\nEnter the string B:");
 scanf("%s",b);
 for(i=0;i<strlen(b);i++)
 {
  if(find(head,b[i])==1)
   removelst(head,b[i]);
 }
 for(i=0;i<strlen(a);i++)
 {
  if(find(head,a[i])==1)
  {
   c[l]=a[i];
   l++;
  }
 }
 c[l]='\0';
 printf("\nString after modification: %s\n",c);
}

convert Bst to sorted circular linked list

Write an efficient function to convert binary search tree into sorted circular doubly linked list. Your function should return the address of first node of resultant list. What are the time and space complexities of your solution?

note:
im building tree here statically

code:
#include<stdio.h>
#include<malloc.h>
struct node
{
    struct node *prev;
    int data;
   struct node *next;
};
struct tree
{
    struct tree *left;
    int data;
    struct tree *right;
};
void append(struct tree**,int);
void treelink(struct tree*,struct node*);
void insertlink(struct node*,int);
void display(struct node*);


void main()
{
    struct tree *head;
    struct node *headlink;
    headlink=(struct node*) malloc(sizeof(struct node));
    headlink->prev=headlink;
    headlink->next=headlink;
    head=NULL;
    append(&head,18);
   append(&head,23);
   append(&head,12);
   append(&head,8);
   append(&head,15);
   append(&head,22);
   append(&head,5);
   append(&head,1);
   append(&head,45);
   append(&head,35);
   append(&head,6);
   append(&head,19);
   append(&head,33);
   append(&head,26);
   append(&head,14);

   treelink(head,headlink);
   display(headlink);

}
void display(struct node *q)
{
    struct node *current=q->next;
      while(current!=q)
      {
         printf(" %d ",current->data);
        current=current->next;
       }
}



void append(struct tree **q,int n)
{
   struct tree *current,*temp,*parent;
     if(*q==NULL)
      {
           temp=(struct tree*) malloc(sizeof(struct tree));
           temp->data=n;
           temp->left=NULL;
           temp->right=NULL;
          *q=temp;
       }
    else
     {
         current=*q;
        temp=(struct tree*) malloc(sizeof(struct tree));
       temp->data=n;
      temp->left=NULL;
      temp->right=NULL;
     while(current!=NULL)
      {
            parent=current;
            if(n<=current->data)
            current=current->left;
          else
            current=current->right;
        }
     if(n<=parent->data)
     parent->left=temp;
     else
      parent->right=temp;
      }
}

void treelink(struct tree *q,struct node *a)
{
    if(q==NULL)
    return;
    treelink(q->left,a);
    insertlink(a,q->data);
   treelink(q->right,a);
}

void insertlink(struct node *a,int i)
{
   struct node *current=a,*temp;
   while(current->next!=a)
   current=current->next;
   temp=(struct node*) malloc(sizeof(struct node));
   current->next=temp;
   temp->data=i;
   temp->prev=current;
   temp->next=a;
   a->prev=temp;
}

lca in binary tree

Least Common Ancestor(LCA) in a tree is defined as the first node that comes common for both the given nodes while travelling towards the root. Write an efficient function “TreeNode FindLca(TreeNode t, TreeNode p, TreeNode q)” to find the least common ancestor of nodes p and q in a binary tree t. You are not allowed to modify the structure of tree node.

 What are the time and space complexities of your solution? Assume that p and q points to valid nodes in a given binary tree. 

Input:

      3                                      p=ADDR(9) q=ADDR(8)
    /    \
  4      7
 /  \    /  \
5  1  6   8
       /
     9                           

Return value: ADDR(7)

Code:

 #include<stdio.h>
#include<conio.h>
#include<malloc.h>

struct treenode
{
    int data;
    struct treenode *left;
    struct treenode *right;
} *root=NULL;
//building tree

struct treenode * buildtree()
{
    struct treenode *temp1,*temp2,*temp3,*temp4;
    root=(struct treenode *)malloc(sizeof(struct treenode));
    temp1=(struct treenode *)malloc(sizeof(struct treenode));
    temp2=(struct treenode *)malloc(sizeof(struct treenode));
    temp3=(struct treenode *)malloc(sizeof(struct treenode));
    temp4=(struct treenode *)malloc(sizeof(struct treenode));
     root->data=4;
     root->left=temp1;
     temp1->data=5;
     root->right=temp2;
     temp2->data=6;
     temp1->left=temp3;
     temp3->data=7;
     temp3->left=temp3->right=NULL;
     temp1->right=temp4;
     temp4->data=8;
     temp4->left=temp4->right=NULL;
      temp2->left=temp2->right=NULL;
  printf("tree buildedsuccessfull");
       return root;
}

//this for given value find address which having those values
struct treenode * findaddress1(struct treenode *root,int i)
{
    if(root==NULL) return NULL;
    if(root->data==i) return root;
    root->left=findaddress1(root->left,i);
    root->right=findaddress1(root->right,i);
    if(root->left!=NULL)
    return root->left;
    else if(root->right!=NULL)
    return root->right;
    else return NULL;
  
}

//finding lca
struct treenode * lcabinary(struct treenode *root,int i,int j)
{
    struct treenode *rh,*lh;
    if(root==NULL) return NULL;
  
    if(root->data==i) return root;
    if(root->data==j) return root;
  
    lh=lcabinary(root->left,i,j);
    rh=lcabinary(root->right,i,j);
  
  
    if(lh!=NULL&&rh!=NULL) return root;
    else if(lh!=NULL) return lh;
    else if(rh!=NULL) return rh;
    else if(lh==NULL&&rh==NULL) return NULL;
  
  
}
void preorder(struct treenode *root)
{
    if(root==NULL)
    return;
  
   printf("%d|%u     ",root->data,root);//this for our reference
    preorder(root->left);
    preorder(root->right);
}

void main()
{
    int i,k=1,j;
    struct treenode *root,*temp1,*temp2,*temp;
    while(k)
    {
        printf("\n enter 1 to build tree");
        printf("\n enter 2 to print in preorder");
        printf("\n enter 3 to find lca");
        scanf("%d",&k);
        switch(k)
        {
            case 1:
                root=buildtree();
                break;
              
            case 2:
                preorder(root);
                break;
          
            case 3:
              
                printf("enter value of address 1");
                scanf("%d",&i);
                    printf("enter value of address 2");
                scanf("%d",&j);
                temp=lcabinary(root,i,j);
                printf("lca is %u and data %d ",temp,temp->data);
            }
        }
}

Finding max levelsum in binary tree

Given a binary tree, write an efficient function that returns the maximum level sum. If tree is empty return 0. Assume that all values in binary tree are positive integers. What are the space and time complexities of your solution?

Input:
              3 

            /    \ 

          4      7

        /   \    /  \

      5     1 1   2 

Return value: 11

Code:

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define QUEUESIZE 20

struct treenode
{
    int data;
    struct treenode *left;
    struct treenode *right;
} *root=NULL;

int *queue[QUEUESIZE];
int rear=-1,front=-1;
//queue finctions

void enque(struct treenode *root)
{
    if(rear<QUEUESIZE)
    {
        queue[++rear]=root;
       
        }
        else printf("queue overflow");
    }
   
int deque()
{
    int i;
    if(front!=rear)
    i=queue[++front];
    else printf("underfolw");
    return i;
}

int isqempty()
{
    if(front==rear)
    return 1;
   
    return 0;
}

//for building tree statically
struct treenode * buildtree()
{
    struct treenode *temp1,*temp2,*temp3,*temp4,*temp5,*temp6;
     root=(struct treenode *)malloc(sizeof(struct treenode));
      temp1=(struct treenode *)malloc(sizeof(struct treenode));
       temp2=(struct treenode *)malloc(sizeof(struct treenode));
        temp3=(struct treenode *)malloc(sizeof(struct treenode));
         temp4=(struct treenode *)malloc(sizeof(struct treenode));
          temp5=(struct treenode *)malloc(sizeof(struct treenode));
           temp6=(struct treenode *)malloc(sizeof(struct treenode));
    
     root->data=4;
     root->left=temp1;
     temp1->data=5;
     root->right=temp2;
     temp2->data=6;
     temp1->left=temp3;
     temp3->data=7;
     temp3->left=temp3->right=NULL;
     temp1->right=temp4;
     temp4->data=8;
     temp4->left=NULL;
     temp4->right=NULL;
      temp2->left=temp5;
      temp5->data=6;
      temp2->right=temp6;
      temp6->data=10;
      temp5->left=temp5->right=temp6->left=temp6->right=NULL;
  printf("\n tree buildedsuccessfull"); 
       return root;
}
//levelsum

void printlevel(struct treenode *root)
{
    int sum=0,maxsum=root->data;
    struct treenode *temp;
    enque(root);
    enque(NULL);
    temp=deque();
    while(!isqempty())
    {
        sum=0;
        while(temp!=NULL)
        {
            sum=sum+temp->data;
        if(temp->left!=NULL)
        enque(temp->left);
       
        if(temp->right!=NULL)
        enque(temp->right);
       
    //    printf("%d   ",temp->data);
        temp=deque();
       
         }
         if(maxsum<sum)
         maxsum=sum;
        
         if(temp==NULL)
        {
        enque(NULL);
        temp=deque();
        }
        }
        printf("\n maximum sum is %d",maxsum);
}

//main

void main()
{
    struct treenode *root;
    int i=1;
    while(i)
    {
        printf("\n enter 1 to build elements");
        printf("\n enter 2 print elements in level wise");
        scanf("%d",&i);
   
    switch(i)
    {
    case 1:
         root=buildtree();
         break;
       
    case 2:
        printlevel(root);
        break;   
    }
     }
}
   

Write an efficient function that takes a binary tree as input and displays the elements of tree level by level, but from last level to first. What are the time and space complexities of your solution? 

Input: 

       3

    /    \

  4      7 

 /  \     /  \

5   1  6   8 

Output: 5 1 6 8 4 7 3


code:


#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define QUEUESIZE 20

struct treenode
{
    int data;
    struct treenode *left;
    struct treenode *right;
} *root=NULL;


//queue functions
int *queue[QUEUESIZE];
int rear=-1,front=-1;

void enque(struct treenode *root)
{
    if(rear<QUEUESIZE)
    {
        queue[++rear]=root;
       
        }
        else printf("queue overflow");
    }
   
int deque()
{
    int i;
    if(front!=rear)
    i=queue[++front];
    else printf("underfolw");
    return i;
}

int isqempty()
{
    if(front==rear)
    return 1;
   
    return 0;
}


struct treenode * buildtree()
{
    struct treenode *temp1,*temp2,*temp3,*temp4,*temp5,*temp6;
     root=(struct treenode *)malloc(sizeof(struct treenode));
      temp1=(struct treenode *)malloc(sizeof(struct treenode));
       temp2=(struct treenode *)malloc(sizeof(struct treenode));
        temp3=(struct treenode *)malloc(sizeof(struct treenode));
         temp4=(struct treenode *)malloc(sizeof(struct treenode));
          temp5=(struct treenode *)malloc(sizeof(struct treenode));
           temp6=(struct treenode *)malloc(sizeof(struct treenode));
    
     root->data=4;
     root->left=temp1;
     temp1->data=5;
     root->right=temp2;
     temp2->data=6;
     temp1->left=temp3;
     temp3->data=7;
     temp3->left=temp3->right=NULL;
     temp1->right=temp4;
     temp4->data=8;
     temp4->left=NULL;
     temp4->right=NULL;
      temp2->left=temp5;
      temp5->data=6;
      temp2->right=temp6;
      temp6->data=10;
      temp5->left=temp5->right=temp6->left=temp6->right=NULL;
  printf("\n tree buildedsuccessfull"); 
       return root;
}
//no nodes
int noofnodes(struct treenode *root)
{
    if(root==NULL) return 0;
   
    return noofnodes(root->left)+noofnodes(root->right)+1;
}


//
void printfrombottam(struct treenode *root)
{
int *array[QUEUESIZE],i=0,j=0;
struct treenode *k;
array[j++]=root;
//k=noofnodes(root);
while(i<j)
{
   
    if(root->right!=NULL)
    array[j++]=root->right;
   
    if(root->left!=NULL)
    array[j++]=root->left;
   
    root=array[++i];
   
}   
for(i=j-1;i>=0;i--)
{
    k=array[i];
    printf("%d   ",k->data);
}   
}//end


//main

void main()
{
    struct treenode *root;
    int i=1;
    while(i)
    {
        printf("\n enter 1 to build elements");
        printf("\n enter 2 print elements in level wise");
        scanf("%d",&i);
   
    switch(i)
    {
    case 1:
         root=buildtree();
         break;
       
    case 2:
        printfrombottam(root);
        break;   
    }
     }
}

Zigzag traversal of tree or spiralorder traversal of binary tree

Idea:
maintain array keep all theelemnts in arry then traverse array in way to get spiral order 

example:

For the given tree,
(1)
(2) (3)
(4) (5) (6) (7)
(8) (9)
Spiral traversal is
1, 2, 3, 7, 6, 5, 4, 8, 9 ….

Array elements after inserting elements will be

1  null  2  3   null  7  6  5  4  null  8  9  null

In array after every level insert null  then traverse in forward direction till null and go next null traverse backward direction to null continue same process



Code:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define QUEUESIZE 20

struct treenode
{
    int data;
    struct treenode *left;
    struct treenode *right;
} *root=NULL;


//building tree

struct treenode * buildtree()
{
    struct treenode *temp1,*temp2,*temp3,*temp4,*temp5,*temp6;
     root=(struct treenode *)malloc(sizeof(struct treenode));
      temp1=(struct treenode *)malloc(sizeof(struct treenode));
       temp2=(struct treenode *)malloc(sizeof(struct treenode));
        temp3=(struct treenode *)malloc(sizeof(struct treenode));
         temp4=(struct treenode *)malloc(sizeof(struct treenode));
          temp5=(struct treenode *)malloc(sizeof(struct treenode));
           temp6=(struct treenode *)malloc(sizeof(struct treenode));
    
     root->data=4;
     root->left=temp1;
     temp1->data=5;
     root->right=temp2;
     temp2->data=6;
     temp1->left=temp3;
     temp3->data=7;
     temp3->left=temp3->right=NULL;
     temp1->right=temp4;
     temp4->data=8;
     temp4->left=NULL;
     temp4->right=NULL;
      temp2->left=temp5;
      temp5->data=6;
      temp2->right=temp6;
      temp6->data=10;
      temp5->left=temp5->right=temp6->left=temp6->right=NULL;
  printf("\n tree buildedsuccessfull"); 
       return root;
}

//print
void print(int *a[],int n)
{
    struct treenode *temp;
    int k=0,i,j,m;
    for(j=0;j<n;)
    {
        if(a[j]==NULL)
        {
            k++;
            j++;
            }
       
        else if(k%2==0)
        {
            temp=a[j];
            j++;
            printf("%d   ",temp->data);
          }   
        else if(k%2==1)
        {
            i=j;
            while(a[i]!=NULL)
            i++;
            for(m=i-1;m>=j;m--)
            {
                temp=a[m];
            printf("%d    ",temp->data);
             }
            j=i;
           
            }
       
        }
}
//zizag order

void zigzag(struct treenode *root)
{
int *array[QUEUESIZE],i=0,j=-1;
struct treenode *k;
array[++j]=root;
array[++j]=NULL;
 while(i<j)
 {
    if(root!=NULL)
    {
    if(root->left!=NULL)
    array[++j]=root->left;
   
    if(root->right!=NULL)
    array[++j]=root->right;
   
    root=array[++i];
    }
    else
    {
    array[++j]=NULL;
    root=array[++i];
    }
   }
  
print(array,j);
}//end

//main

void main()
{
    struct treenode *root;
    int i=1;
    while(i)
    {
        printf("\n enter 1 to build elements");
        printf("\n enter 2 print elements in zigzag order");
        scanf("%d",&i);
   
    switch(i)
    {
    case 1:
         root=buildtree();
         break;
       
    case 2:
        zigzag(root);
        break;   
    }
     }
}

Finding number nodes in a tree and height of tree and find number of full nodes

fullnodes:

nodes which have both left and right childrens if a node contains left or right is null or both are
null those nodes are not full nodes

code:

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

struct treenode
{
    int data;
    struct treenode *left;
    struct treenode *right;
} *root=NULL;
//static tree building function
struct treenode * buildtree()
{
    struct treenode *temp1,*temp2,*temp3,*temp4,*temp5;
     root=(struct treenode *)malloc(sizeof(struct treenode));
      temp1=(struct treenode *)malloc(sizeof(struct treenode));
       temp2=(struct treenode *)malloc(sizeof(struct treenode));
        temp3=(struct treenode *)malloc(sizeof(struct treenode));
         temp4=(struct treenode *)malloc(sizeof(struct treenode));
    
     root->data=4;
     root->left=temp1;
     temp1->data=5;
     root->right=temp2;
     temp2->data=6;
     temp1->left=temp3;
     temp3->data=7;
     temp3->left=temp3->right=NULL;
     temp1->right=temp4;
     temp4->data=8;
     temp4->left=NULL;
     temp4->right=NULL;
      temp2->left=temp2->right=NULL;
  printf("\n tree buildedsuccessfull"); 
       return root;
}
//no nodes
int noofnodes(struct treenode *root)
{
    if(root==NULL) return 0;
   
    return noofnodes(root->left)+noofnodes(root->right)+1;
}
//height of tree
int height(struct treenode *root)
{
    if(root==NULL) return 0;
    return max(height(root->left),height(root->right))+1;
}
//
int max(int i, int k)
{
    if(i>k)
    return i;
    return k;
}

int fullnodes(struct treenode *root)
{
    int count=0;
    if(root==NULL ) return ;
    else if(root->left!=NULL&&root->right!=NULL)
    count=1;
   
    return fullnodes(root->left)+fullnodes(root->right)+count;
}
int d=0;
int diameter(struct treenode *root,int l)
{ 
    d=l;
    int lh,rh;
     if(root==NULL) return 0;
    lh=diameter(root->left,d);
    rh=diameter(root->right,d);
    if(d<(lh+rh))
    d=lh+rh;
    return max(lh,rh)+1;
   
}

void main()
{
    struct treenode *root;
    int i=1;
    while(i)
    {
    printf("\n enter 2 to build tree");
    printf("\n enter 1 to find no of nodes of given tree");
    printf("\n enter 3 to find height");
    printf("\n enter 4 find full nodes of given tree");
    printf("\n enter 5 find diameter");
    scanf("%d",&i);
    if(i==5)
        {
            diameter(root,d);
         printf("\n %d is diameter",d);
         }
    if(i==4)
    printf("\n full node is %d",fullnodes(root));
    if(i==2)
    root=buildtree();
    if(i==3)
    printf("\n height if tree is %d",height(root));
    if(i==1)
    printf("\n %d is no of nodes in given tree",noofnodes(root));
}
}

Traversing a tree inorder and post and preorder without using recursion

Traversing a tree inorder and post and preorder using non recursive technique:

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define STACKSIZE 20

struct treenode
{
    int data;
    struct treenode *left;
    struct treenode *right;
} *root=NULL;

// stack functions
int top=-1; struct treenode *stack[STACKSIZE];
void push(struct treenode *temp)
{
    if(top<STACKSIZE)
    {
        top++;
        stack[top]=temp;
        }
        else
        printf("stack overflow");
}

int pop()
{
    int i;
    if(top==-1)
    {
        printf("stackunderflow");
        }
    else
    i=stack[top--];
    return i;
   
}
int isstackempty()
{
    if(top==-1)
    return 1;
    else return 0;
}
//end of stackfunctions

struct treenode * buildtree()
{
    struct treenode *temp1,*temp2,*temp3,*temp4,*temp5;
     root=(struct treenode *)malloc(sizeof(struct treenode));
      temp1=(struct treenode *)malloc(sizeof(struct treenode));
       temp2=(struct treenode *)malloc(sizeof(struct treenode));
        temp3=(struct treenode *)malloc(sizeof(struct treenode));
         temp4=(struct treenode *)malloc(sizeof(struct treenode));
    
     root->data=4;
     root->left=temp1;
     temp1->data=5;
     root->right=temp2;
     temp2->data=6;
     temp1->left=temp3;
     temp3->data=7;
     temp3->left=temp3->right=NULL;
     temp1->right=temp4;
     temp4->data=8;
     temp4->left=NULL;
     temp4->right=NULL;
      temp2->left=temp2->right=NULL;
  printf("\n tree buildedsuccessfull"); 
       return root;
}

 void inorder(struct treenode *root)
 {
    struct treenode *temp;
    temp=root;
    while(1)
    {
    while(temp!=NULL)
       {
            push(temp);
            temp=temp->left;
        }
    if(isstackempty()) return;
    temp=pop();
    printf("%d    ",temp->data);
    temp=temp->right;
     }
  }   
void preorder(struct treenode *root)
 {
    struct treenode *temp;
    temp=root;
    while(1)
    {
    while(temp!=NULL)
       { 
            printf("%d   ",temp->data);
            push(temp);
            temp=temp->left;
        }
    if(isstackempty()) return;
    temp=pop();
    temp=temp->right;
     }
  }   
       
void postorder(struct treenode *root)
 {
    struct treenode *temp,*q;
    temp=root;
    while(1)
    {
    while(temp!=NULL)
       {
            push(temp);
            temp=temp->left;
        }
    if(isstackempty()) return;
    temp=pop();
    if(((int)temp)<0)
    {
        temp=((unsigned int)temp)*-1;
    printf("%d    ",temp->data);
    temp=NULL;
     }
     else
     {
            q=temp;
            temp=temp->right;
        q=((unsigned int)q)*-1;
        push(q);
            }
  }
}
 
     
//main
void main()
{
    int k=1,j;
    struct treenode *root;
    while(k)
    {
        printf("\n enter 1 to build tree");
        printf("\n enter 2 to print preorder");
        printf("\n enter 3 to print inorder");
        printf("\n enter 4 print postoreder");
        scanf("%d",&k);
       
        switch(k)
        {
         case 1:
       
            root=buildtree();
            break;
           
        case 2:
            preorder(root);
            break;
       
           case 3:
                  inorder(root);
                break;
           
        case 4:
            postorder(root);
            break;
           
            }
       
       
        }
}

Cisco written question paper 2011:

Cisco written question paper 2011:

The written test had two parts.
Test Date : 21 August 2010
20 questions from aptitude and 30 technical, no negative marking.
Aptitude was quite a lot tricky and technical was Electronics + CS.

Three C programs
1) main()
{
int const a=100;
int *p;
p=&a;
(*p)++;
printf("%d%d",a,*p);
}
Ans: 101 101

Explanation: Pointer can modify an object it pointing to but the variable can't change it when the variable defined as const.

2) ARP is used for?

The Address Resolution Protocol (ARP) is used for determining a network host's Link Layer or hardware address (MAC Address) when only its Internet Layer (IP) or Network Layer address is known. You have written it reversely..

3. End to End delivery is responsibility of which layer?

Transport Layer

4. If virtual address is[0,514] then if page table contains an entry (032) then physical address is:
Ans append binary form of 32 with binary form of 514


5. Floating point representation: Simple one
If 23 bits are used for IEEE representation then whats the range of normalized nos. which can be represented?

Ans.


Smallest Number can be : +/- 2^(-126) to
Highest number +/- (2-2^23)*2^127.
This table will be helpful to identify the range of normalized numbers

Type                  Exponent     Fraction
Zeroes                     0              0
Denormalized numbers       0           non zero
Normalized numbers       1 to 2e − 2     any
Infinities                2e − 1          0
NaNs                      2e − 1       non zero

One semaphores.


Generally 2 technical interviews and one HR. But for some 3 technical and one HR.
Technical interview contained questions like:




1. Full form of SQL
Ans. Structured Query Language

2. Various functions in SQL
Ans. All SQL functions return a single value that is either a number or a string.
a. Standard: These return a value from an expression.
example:
ABS Returns the absolute value of the numeric expression.
num = ABS( expression )

ALL Tests against the values in the value_list. Returns 1 (true) if matches every item. Equivalent to individual tests against each item in the list joined by AND operators. ALL is used particularly to test against sets of values returned by subqueries.
value = ALL ( value_list | subquery )

ANY Tests against the values in the value_list. Returns 1 (true) if matches any item. Equivalent to individual tests against each item in the list joined by OR operators. ANY is used particularly to test against sets of values returned by subqueries.
value = ANY ( value_list | subquery )

INT Returns the truncated integer value for the numeric expression.
num = INT ( expression )

LEN Returns the number of characters (including trailing blanks) in the string expression.
num = LEN( string )

LOWER Returns the string with all uppercase letters converted to their lowercase equivalent.
str = LOWER( string )

b. Aggregation: These compute a value from a number of rows and thus alter the number of rows produced in the output table.
example:
AVG ([UNIQUE] numeric_col) Returns the average or mean value of the non-missing values for numeric columns. If UNIQUE is specified then only unique values are used to calculate the mean.

COUNT ( [ UNIQUE ] col | * ) Returns the number of non-missing values encountered. If UNIQUE is specified, then only the unique values add to the count. An asterisk as the argument returns the number of all rows selected regardless of whether the values are valid, missing or undefined.

MAX (col) Returns the maximum non-missing value encountered. The type of variable returned corresponds to the type of the variable being referenced.

MIN (col) Returns the minimum value of the non-missing values. The type of variable returned corresponds to the type of the variable being referenced.

Decode, ltrim, rtrim, lpad, rpad, truncate etc..


3. Java...
Object oriented analysis and design: usecases, collaboration and sequential diagrams, difference purpose class diagram.

5. Data warehousing?

6. Networking client server basic concepts.

7. C program to count the no. of elements which are repeating more than size/2 times in an array.

8. Derive a mathematical equation to calculate the angle between two hand of clock.

Ans
Angel= 1/2(6H+M) - 6M

H is an integer in the range 0–11 and M is the minute


9. What are different segments in a program.
Ans:

The computer program memory is organized into the following:

  1. Data Segment (Data + BSS + Heap)
             The data area contains global and static variables
 used by the program that are initialized. 
             BSS(Block Started by Symbol): uninitialized data 
starts at the end of the data segment and contains all uninitialized 
global variables and static variables that are initialized to zero 
by default. 
             The Heap area is managed by malloc, realloc, and free,
  2. Stack
             he stack is a LIFO structure, typically located 
in the higher parts of memory. It usually "grows down" with 
every register, immediate value or stack frame being added 
to it. A stack frame consists at minimum of a return address.
  3.Code segment

When we malloc sm size where does it reside.
Where is a.out stored

Stack increses in which direction ?
Ans:
Sack starts from highe memory locations and it increases in lower memory locations


Representation of stack and queue using linked list and then perform insertion and deletion

Models in software Eng?.Explain extreme programming
Ans:
Waterfall Model
Iterative Model
Spiral Model

What are triggers?example
Ans:
A Trigger is a named database object which defines some action that the database should take when some databases related event occurs. Triggers are executed when you issues a data manipulation command like INSERT, DELETE, UPDATE on a table for which the trigger has been created. They are automatically executed and also transparent to the user. But for creating the trigger the user must have the CREATE TRIGGER privilege.

3 properties of object oriented analysis and design
Ans:
Data Abstraction
Re usability
Polymorphism

Normal forms in dbms?
Ans:
1 NF
2 NF
3 NF
BCNF
4 NF
and 5 NF

CISCO Placement Paper : Chennai 2011

CISCO Placement Paper : Chennai

1. In the command scanf, h is used for
Ans. Short int

2. A process is defined as
Ans. Program in execution

3. A thread is
Ans. Detachable unit of executable code)

4. What is the advantage of Win NT over Win 95
Ans. Robust and secure

5. How is memory management done in Win95
Ans. Through paging and segmentation

6. What is meant by polymorphism
Ans. Redfinition of a base class method in a derived class

7. What is the essential feature of inheritance
Ans. All properties of existing class are derived

8.What does the protocol FTP do
Ans. Transfer a file b/w stations with user authentification

9.In the transport layer ,TCP is what type of protocol
Ans. Connection oriented

10.Why is a gateway used
Ans. To connect incompatible networks

11.How is linked list implemented
Ans. By referential structures

12.What method is used in Win95 in multitasking
Ans. Non preemptive check

13.What is meant by functional dependency

14.What is a semaphore
Ans. A method synchronization of multiple processes



15.What is the precedence order from high to low ,of the symbols ( ) ++ /
Ans.( ) , ++, /



16.Preorder of A*(B+C)/D-G Ans.*+ABC/-DG

18. B-tree (failure nodes at same level)

19. Dense index (index record appers for every search -key in file)

20.What is the efficiency of merge sort
Ans. O(n log n)

21.A program on swaping ( 10,5 )was given (candidate cannot recollect)

22.In which layer are routers used
Ans.In network layer 23.In which layer are packets formed ( in network layer )

24. heap ( priority queue )

25. Copy constructor ( constant reference )

26.Which of the following sorting algorithem has average sorting behavior, Bubble sort, merge sort, heap sort, exchange sort
Ans. Heap sort

27.In binary search tree which traversal is used for getting ascending order values Inorder, post order, preorder Ans. Inorder

28.What are device drivers used for
Ans.To provide software for enabling the hardware

29. Irrevalent to unix command ( getty)

30.What is fork command in unix
Ans. System call used to create process

31.What is make command in unix
Ans. Used forcreation of more than one file

32.In unix .profile contains
Ans. Start up program

33.In unix echo is used for
( answer C)

34.In unix 'ls 'stores contents in
Ans.inode block QUANTITATIVE SECTION

1. In a class composed of x girls and y boys what part of the class is composed of girls A.y/(x + y) B.x/xy C.x/(x + y) D.y/xy
Ans.C

2.What is the maximum number of half-pint bottles of cream that can be filled with a 4-gallon can of cream(2 pt.=1 qt. and 4 qt.=1 gal) A.16 B.24 C.30 D.64
Ans.D

3. If the operation,^ is defined by the equation x ^ y = 2x + y,what is the value of a in 2 ^ a = a ^ 3 A.0 B.1 C.-1 D.4
Ans.B

4. A coffee shop blends 2 kinds of coffee,putting in 2 parts of a 33p. a gm. grade to 1 part of a 24p. a gm. If the mixture is changed to 1 part of the 33p. a gm. to 2 parts of the less expensive grade,how much will the shop save in blending 100 gms. A.Rs.90 B.Rs.1.00 C.Rs.3.00 D.Rs.8.00
Ans.C

5. There are 200 questions on a 3 hr examination. Among these questions are 50 mathematics problems. It is suggested that twice as much time be spent on each maths problem as for each other question. How many minutes should be spent on mathematics problems A.36 B.72 C.60 D.100
Ans.B

6. In a group of 15,7 have studied Latin, 8 have studied Greek, and 3 have not studied either. How many of these studied both Latin and Greek A.0 B.3 C.4 D.5
Ans.B

7. If 13 = 13w/(1-w) ,then (2w)2 = A.1/4 B.1/2 C.1 D.2
Ans.D

8. If a and b are positive integers and (a-b)/3.5 = 4/7, then (A) b < a (B) b > a

(C) b = a

(D) b >= a

Ans. A

9. In june a baseball team that played 60 games had won 30% of its game played. After a phenomenal winning streak this team raised its average to 50% .How many games must the team have won in a row to attain this average?
A. 12
B. 20
C. 24
D. 30

Ans. C

10. M men agree to purchase a gift for Rs. D. If three men drop out how much more will each have to contribute towards the purchase of the gift/
A. D/(M-3)
B. MD/3
C. M/(D-3)
D. 3D/(M2-3M)
Ans. D

11. A company contracts to paint 3 houses. Mr.Brown can paint a house in 6 days while Mr.Black would take 8 days and Mr.Blue 12 days. After 8 days Mr.Brown goes on vacation and Mr. Black begins to work for a period of 6 days. How many days will it take Mr.Blue to complete the contract?

A. 7
B. 8
C. 11
D. 12
Ans.C

12. 2 hours after a freight train leaves Delhi a passenger train leaves the same station travelling in the same direction at an average speed of 16 km/hr. After travelling 4 hrs the passenger train overtakes the freight train. The average speed of the freight train was?
A. 30
B. 40
C.58
D. 60
Ans. B

13. If 9x-3y=12 and 3x-5y=7 then 6x-2y = ?
A.-5
B. 4
C. 2
D. 8
Ans. D

Analytical Ability

1. The office staff of XYZ corporation presently consists of three bookeepers A, B, C and 5 secretaries D, E, F, G, H. The management is planning to open a new office in another city using 2 bookeepers and 3 secretaries of the present staff. To do so they plan to seperate certain individuals who don't function well together. The following guidelines were established to set up the new office

I. Bookeepers A and C are constantly finding fault with one another and should not be sent together to the new office as a team

II. C and E function well alone but not as a team, they should be seperated

III. D and G have not been on speaking terms and shouldn't go together

IV Since D and F have been competing for promotion they shouldn't be a team

1. If A is to be moved as one of the bookeepers, which of the following cannot be a possible working unit.

A. ABDEH
B. ABDGH
C. ABEFH
D. ABEGH
Ans.B
2. If C and F are moved to the new office, how many combinations are possible
A.1
B.2
C.3
D.4
Ans.A

3. If C is sent to the new office,which member of the staff cannot go with C
A.B
B.D
C.F
D.G
Ans.B

4. Under the guidelines developed, which of the following must go to the new office
A.B
B.D
C.E
D.G
Ans.A

5. If D goes to the new office, which of the following is/are true
I. C cannot go
II. A cannot go
III. H must also go


A.I only

B.II only

C.I and II only

D.I and III only

Ans.D
2. After months of talent searching for an administrative assistant to the president of the college the field of applicants has been narrowed down to 5--A, B, C, D, E .It was announced that the finalist would be chosen after a series of all-day group personal interviews were held.The examining committee agreed upon the following procedure
I.The interviews will be held once a week
II.3 candidates will appear at any all-day interview session
III.Each candidate will appear at least once
IV.If it becomes necessary to call applicants for additonal interviews, no more 1 such applicant should be asked to appear the next week
V.Because of a detail in the written applications,it was agreed that whenever candidate B appears, A should also be present.
VI.Because of travel difficulties it was agreed that C will appear for only 1 interview.

1.At the first interview the following candidates appear A,B,D.Which of the follwing combinations can be called for the interview to be held next week.
A.BCD
B.CDE
C.ABE
D.ABC

Ans.B
2.Which of the following is a possible sequence of combinations for interviews in 2 successive weeks

A.ABC;BDE
B.ABD;ABE
C.ADE;ABC
D.BDE;ACD
Ans.C

3.If A ,B and D appear for the interview and D is called for additional interview the following week,which 2 candidates may be asked to appear with D?
I. A
II B
III.C
IV.E

A.I and II
B.I and III only
C.II and III only
D.III and IV only

Ans.D

4.Which of the following correctly state(s) the procedure followed by the search committee
I.After the second interview all applicants have appeared at least once
II.The committee sees each applicant a second time
III.If a third session,it is possible for all applicants to appear at least twice

A.I only
B.II only
C.III only
D.Both I and II

Ans.A

3. A certain city is served by subway lines A,B and C and numbers 1 2 and 3
When it snows , morning service on B is delayed
When it rains or snows , service on A, 2 and 3 are delayed both in the morning and afternoon
When temp. falls below 30 degrees farenheit afternoon service is cancelled in either the A line or the 3 line,but not both.

When the temperature rises over 90 degrees farenheit, the afternoon service is cancelled in either the line C or the

3 line but not both.

When the service on the A line is delayed or cancelled, service on the C line which connects the A line, is delayed.

When service on the 3 line is cancelled, service on the B line which connects the 3 line is delayed.



Q1. On Jan 10th, with the temperature at 15 degree farenheit, it snows all day. On how many lines will service be

affected, including both morning and afternoon.



(A) 2

(B) 3

(C) 4

(D) 5



Ans. D





Q2. On Aug 15th with the temperature at 97 degrees farenheit it begins to rain at 1 PM. What is the minimum number

of lines on which service will be affected?



(A) 2

(B) 3

(C) 4

(D) 5



Ans. C





Q3. On which of the following occasions would service be on the greatest number of lines disrupted.



(A) A snowy afternoon with the temperature at 45 degree farenheit

(B) A snowy morning with the temperature at 45 degree farenheit

(C) A rainy afternoon with the temperature at 45 degree farenheit

(D) A rainy afternoon with the temperature at 95 degree farenheit



Ans. B





4. In a certain society, there are two marriage groups, red and brown. No marriage is permitted within a group. On marriage, males become part of their wives groups; women remain in their own group. Children belong to the same group as their parents. Widowers and divorced males revert to the group of their birth. Marriage to more than one person at the same time and marriage to a direct descendant are forbidden



Q1. A brown female could have had



I. A grandfather born Red

II. A grandmother born Red

III Two grandfathers born Brown



(A) I only

(B) III only

(C) I, II and III

(D) I and II only



Ans. D





Q2. A male born into the brown group may have



(A) An uncle in either group

(B) A brown daughter

(C) A brown son

(D) A son-in-law born into red group

Ans. A

Q3. Which of the following is not permitted under the rules as stated.

(A) A brown male marrying his father's sister

(B) A red female marrying her mother's brother

(C) A widower marrying his wife's sister

(D) A widow marrying her divorced daughter's ex-husband



Ans. B

Q4. If widowers and divorced males retained their group they had upon marrying which of the following would be permissible ( Assume that no previous marriage occurred)



(A) A woman marrying her dead sister's husband

(B) A woman marrying her divorced daughter's ex-husband

(C) A widower marrying his brother's daughter

(D) A woman marrying her mother's brother who is a widower.

Ans. D

5. I. All G's are H's

II. All G's are J's or K's

III All J's and K's are G's

IV All L's are K's

V All N's are M's

VI No M's are G's

Q1. If no P's are K's which of the following must be true

(A) No P is a G
(B) No P is an H
(C) If any P is an H it is a G
(D) If any P is a G it is a J
Ans. D

Q2. Which of the following can be logically deduced from the stated conditions
(A) No M's are H's

(B) No H's are M's

(C) Some M's are H's

(D) No N's are G's

Ans. D

Q3. Which of the following is inconsistent with one or more conditions
(A) All H's are G's
(B) All H's are M's
(C) Some H's are both M's and G's
(D) No M's are H's
Ans. C

Q4. The statement "No L's are J's" is



I. Logically deducible from the conditions stated

II Consistent with but not deducible from the conditions stated

III. Deducible from the stated conditions together with the additional statements "No J's are K's"

(A) I only
(B) II only
(C) III only
(D) II and III only
Ans. D

Here are some questions from cisco(m.tech.) tech.--24, apti.--20



1. On cmos power( formula- P=CV*Vf

2. Lowest noise margin in which logic family--

a) TTL b) CMOS c) biCMOS d) all have same

3. If CMOS has tr(rise time)=tf.find Wp/Wn. given beta(n)=2*beta(p)

4. gm of a transistor is proportional to

a)Ic b)Vt c)1/Vt d)none

5. If A and B are given in 2's complement find A-B in decimal.

6. Set up time,hold time ,clock to Q delay time (very important)

7. 3 questions on opamp (transfer function)(2 marks each)

8. 2 questions on sequence detector (2 marks each)

9. Logic function boolean expressions(true/false) (3 question-1 mark each)probabily all false

10. In I/O mapped how do you represent memory(1 mark)

11. The design of FSM(finite state machine) will--

a) increase time of design

b) increase delay

c) increase power

d) all of the above

12. K-map minimization

13. Phase locked loop(PLL) 1 question. 

CISCO Placement Questions and Answers 2011

CISCO Placement Questions and Answers

1.

char a =0xAA ;
int b ;
b = (int) a ;
b = b >> 4 ;
printf("%x",b);

What is the output of the above program segment ?

a is of 8 byte,a's binary representation = 1010 1010
since MSB is 1 ,it will be considered as -ve number.
say int is of 32 bytes so to get the actual take out a 's 2 complement..

which will be
1111 1111 1111 1111 1111 1111 0101 0101

when you right shift it by 4 it will become 1111 1111 1111 1111 1111 1111 1111 0101
left most side of 1111 will not be 0 because it is a -ve number so sign bit will be extended..
hence o/p will be fffffff5( 64 bit PC)


2. Output?

int main()
{
char *ptr = " Cisco Systems";
*ptr++;
printf("%sn",ptr);
ptr++;
printf("%sn",ptr);
getchar()
return 0;
}

int main()
{
// Initialization
char *ptr = " Cisco Systems";

// Binding *(ptr++) due to right to left associativity
// The pointer incremented by one and then dereferenced
// The r-value is not caught in any l-value expression
// So the result is discarded, yet the pointer incremented
// Now, ptr points one character past the initial base
// i.e. "Cisco Systems" (there is space)
*ptr++;
printf("%s\n",ptr);
// One more increment
// Now ptr pointing "isco Systems"
ptr++;
printf("%s\n", ptr);
return 0;
}
Result:
Cisco Systems
isco Systems

3. what is a super block?

The superblock is an area in a storage device of a Linux computer, which stores various bits of information about a file system, such as a pointer to the free blocks structure, the number of free inodes, etc. In case the superblock is damaged and cannot be read, an error message is generated by the system. In this case, the E2FSCK utility is used to troubleshoot the issue by passing the superblock parameter manually.

Finding corrupted node in two linked list

How to find the corrupted node in two linked list:





Algorithm:

 solution 1:

 By using hash table we can find when traversing list1 store in hash table and when traversing
second list check whether next address is present in hashtable or not if present address present hashtable that is first corrupted node
time complexity: O(m+n)
space complexity: O(m) or O(n) depends on which list u are storing in hashtable

solution 2:(which possible in only c not possible in java )
Traverse list1 once while traversing make next address of each node negative then move
after that start traverse second linked list untill u find next address as negative that node is first corrupted of two linkedlist

time complexity:O(m+n)
space complexity:O(1)

note: practically we wont get this situation of corrupting i intentionally made corruption between
two linkedlists  then i find that node by using above logic

code for second solution:

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

struct node
{
    int data;
    struct node *next;
} *head1=NULL,*head2=NULL;

struct node * insertlist1(struct node *head,struct node *inter,int i,int k)
{
    struct node *temp,*q;   
    temp=(struct node *)malloc(sizeof(struct node));
    if(k==5)
    {
        inter=temp;
        }
    temp->data=i;
        temp->next=NULL;
    if(head->next==NULL)
    {
        head->next=temp;
       
        }
        else
        {
            q=head->next;
            while(q->next!=NULL)
            q=q->next;
            q->next=temp;
            }
            return inter;
}

//displaying nodes with address because we can see where nodes are corruping
void display(struct node *head)
{
    struct node *temp;
    temp=head->next;
    while(temp->next!=NULL)
    {
        printf("%u | %d | %u    ",temp,temp->data,temp->next);
        temp=temp->next;
        }
    }
   
    //insertion 2
insertlist2(struct node *head,struct node *inter,int i,int k)
{
    struct node *temp,*q;       
    if(k==5)
    {
        temp=inter;
        temp->data=i;
        q=head->next;
        while(q->next!=NULL)
        q=q->next;
        q->next=temp;
        printf("successfully corrupted node maden");
       
        }
    else if(k<5)
{
temp=(struct node *)malloc(sizeof(struct node));

        temp->data=i;
        temp->next=NULL;
    if(head->next==NULL)
    {
        head->next=temp;
       
        }
        else
        {
            q=head->next;
            while(q->next!=NULL)
            q=q->next;
           
            q->next=temp;
            }
}
}

void findcorrupt(struct node *head1,struct node *head2)
{
  
    struct node *temp,*q;
    temp=head1->next;          
    while(temp->next!=NULL)
    {
        q=temp;
        temp=temp->next;
        q->next=((unsigned int)q->next)*-1;
        }  
    temp=head2->next;
    while((int)temp->next>0)
    {
        temp=temp->next;
        }
           
            printf("%d is comman",temp);
            }
       


int main()
{
    int i=1,j,k=1,m=3;
    head1=(struct node*)malloc(sizeof(struct node));
    head1->next=NULL;
    head2=(struct node*)malloc(sizeof(struct node));
    head2->next=NULL;
    struct node *inter=NULL;
    while(i)
    {
    printf("\n enter 1 insert element in list1");
    printf("\n enter 2 insert element in list2");
    printf("\n enter 3 to display list1");
    printf("\n enter 4 to display list2");
    printf("\n enter 5 find corrupted node");
    printf("\n enter 0to exit");
    scanf("%d",&i);
   
    switch(i)
    {
    case 1:
        printf("enter elementtoinsert");
        scanf("%d",&j);
        inter=insertlist1(head1,inter,j,k++);
        break;
       
    case 2:
        printf("enter element to insert");
        scanf("%d",&j);
        insertlist2(head2,inter,j,m++);
        break;
       
    case 3:
        display(head1);
        break;
       
    case 4:
        display(head2);
        break;
       
    case 5:
        findcorrupt(head1,head2);
        break;
       
        }
    }
}