Saturday, 24 June 2017

C Program to traverse a matrix in spiral order

C Program to traverse a matrix in spiral order is given below. The program is compiled and checked successfully output is also given below the program.

Example:

A[4][4]= {  1 , 2 , 3 , 4
                   5 , 6 , 7 , 8
                   9 , 10 , 11 , 12
                  13 , 14 , 15 , 16  }

Spiral traversal:    1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10

PROGRAM:

#include<iostream>
using namespace std;
#define M 10
#define N 10

void spiral(int arr[M][N],int m,int n){


    int startrow=0,startcol=0,endrow=n-1,endcol=m-1;

    while(startrow<=endrow && startcol<=endcol)
    {
 
        for(int i=startcol;i<=endcol;i++){
            cout<<arr[startrow][i]<<" ";
        }
        startrow++;

        for(int i=startrow;i<=endrow;i++){
            cout<<arr[i][endcol]<<" ";
        }
        endcol--;

        if(startrow<=endrow){
            for(int i=endcol;i>=startcol;i--){
                cout<<arr[endrow][i]<<" ";
            }
            endrow--;
        }

        if(startcol<=endcol){
            for(int i=endrow;i>=startrow;i--){
                cout<<arr[i][startcol]<<" ";
            }
            startcol++;
        }
    }
}

int main(){
    
    
  

       int m,n;

       cout<<"\nEnter the number or rows and column of the matrix: \n";
       cin>>m>>n;
       int arr[M][N];

       cout<<"\n\nEnter the elements of the matrix: \n\n";
       for(int i=0;i<m;i++)
       {

          for(int j=0;j<n;j++)
          {
            cin>>arr[i][j];
          }
       }
      
      cout<<"\n\nThe spiral traversal of matrix is: \n\n";
      spiral(arr,m,n);
      cout<<"\n";
     
   
     return 0;
}



OUTPUT:




Thursday, 8 June 2017

C++ Program to detect a loop in singly Linked List

Algorithm and the program for detecting any loop inside the singly Linked linked list is given below.
Implementation is simple we will use two pointer. We will increment one pointer by one the other one by two and then check if two pointers are equal or not. If they are equal then linked list has loop inside it otherwise linked list does not contain any loop.

ALGORITHM:
  step 1:     set  node *current1=head
  step 2:     set  node *current2=head
  step 3:     doWhile current1!=NULL && current2!=NULL && current1->next!=NULL:
  step 4:                   current1=current1->next
  step 5:                   current2=current2->next->next
  step 6:                   if(current1==current2):
  step 7:                                return true
  step 8:     endLoop
  step 9:     return false



PROGRAM:

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

struct node{
 int data;
    struct node *next;
};

node* create_newnode(int data);
bool detectLoop(struct node *head);

int main()
{

      /*    Now we are creating the linked list shown below
            with a loop i.e  node 16 is connected back to node 10

            8--> 10--> 12--> 14--> 16
                 ^                 |
                 |                 |
                 -------------------


       */


   struct node *head,*temp;
   head=create_newnode(8);
   head->next=create_newnode(10);
   temp=head->next;
   head->next->next=create_newnode(12);
   head->next->next->next=create_newnode(14);
   head->next->next->next->next=create_newnode(16);
   head->next->next->next->next->next=temp;

      if(detectLoop(head))
      {
             cout<<"\n\nLinked List has loop !\n\n";
      }
      else
      {
             cout<<"\n\nLinked List does not contain loop in\n\n";
      }



      /*  Creating new linked list:
           8--> 10--> 12--> 14--> 16-->NULL

           The linked list shown above does not conatin any loop
      */


      head=create_newnode(8);
   head->next=create_newnode(10);
   head->next->next=create_newnode(12);
   head->next->next->next=create_newnode(14);
   head->next->next->next->next=create_newnode(16);


   if(detectLoop(head))
      {
             cout<<"\n\nLinked List has loop inside it!\n\n";
      }
      else
      {
             cout<<"\n\nLinked List does not has any loop insite it !\n\n";
      }
   
}

node* create_newnode(int data)
{
   
    struct node *newnode;
    newnode=new node();
    newnode->data=data;
    newnode->next=NULL;
    return newnode;

}

bool detectLoop(struct node *head)
{
    
    struct node *current1,*current2;
    current1=head;
    current2=head;
    while(current1!=NULL && current2!=NULL && current2->next!=NULL)
    {
          current1=current1->next;
          current2=current2->next->next;
          if(current1==current2)
          {
                return true;
          }
    }
    return false;
}


OUTPUT:


Wednesday, 7 June 2017

Python Program for Insertion at any position in Singly Linked List

Python program for insertion node at any position in singly linked list is given below. In this program the class LinkedList contains a method insert which will insert the new element at the desired position the program along with output is given.

If you don't know how to create a singly linked list in python then click this link:  Python program to create a singly linked list

PROGRAM:

class Node:
 def __init__(self,data):
  self.data=data
  self.next=None

class LinkedList:
 def __init__(self):
  self.head=None
  self.size=0



 def append(self,data):
  if(self.head==None):
   newnode=Node(data)
   self.head=newnode
  else:
   current=self.head
   while(current.next!=None):
    current=current.next
   current.next=Node(data)
  self.size=self.size+1



 def insert(self,data,position):
  if(position==0):
   newnode=Node(data)
   newnode.next=self.head
   self.head=newnode
  elif(position>self.size):
   print("\n\nIndex is out of range\n\n")
  elif(position==self.size):
   self.append(data)
  else:
   current=self.head
   count=0
   while(current!=None):
    if(count==position-2):
     break
    else:
     count+=1
     current=current.next
   newnode=Node(data)
   newnode.next=current.next
   current.next=newnode


 def printlist(self):
  current=self.head
  while(current!=None):
   print current.data,
   current=current.next
mylinklist=LinkedList()
mylinklist.append(4)
mylinklist.append(5)
mylinklist.append(8)
mylinklist.append(10)
print("\n\nThe linked list before insertion:\n\n")
mylinklist.printlist()
mylinklist.insert(6,3)
print("\n\nThe linked list after insertion:\n\n")
mylinklist.printlist()
mylinklist.insert(10,4)
print("\n\nThe linked list after insertion:\n\n")
mylinklist.printlist()
mylinklist.insert(2,0)
print("\n\nThe linked list after insertion:\n\n")
mylinklist.printlist()
mylinklist.insert(12,8)




OUTPUT:


Tuesday, 6 June 2017

Implementation of Floyd Warshall Algorithm - C++

Floyd Warshall algorithm is used to find the shortest distance between the every pair of vertices in a given weight directed graph which does not contain any cycles of negative length ( The total length of any cycle in the graph should not be negative). The idea is very simple we  will pick all the vertices one by one and include the picked vertex between two every other pair of vertices as an intermediate vertex and update the distance matrix if the distance between the two vertex becomes smaller than before. Implementation of Floyd Warshall algorithm is very simple which is its main advantage. Implementation of Floyd Warshall algorithm in C++ is given below.


Algorithm


step 1:    Initialize Distance matrix i.e.   D(i,j) = adjacency(i,j)
step 2:    do For  k=1 to k=n:
step 3:              do For i=1 to i=n:
step 4:                       do For j=1 to j=n:
step 5:                               if    D[i][k]+D[k][j] < D[i][j]:
step 6:                                      set   D[i][j] = D[i][k]+D[k][j]
step 7:    Exit.




Example: 

                     

The implementation of the floyd warshall algorithm for the above example and its output is given below

Note:  1000 here representing infinity i.e there is not edge between those two vertex.

PROGRAM:

#include <iostream>
#include <stdio.h>
using namespace std;

class graph
{
   int adjacency[10][10],distance[10][10],n,i,j,k;
   public:
        void get_data();
        void floydwarshall();
        void print();
};

void graph::get_data()
{
  printf("\nEnter the total number of vertices: ");
  scanf("%d",&n);
  printf("\nEnter the adjacency matrix (If there is no \nedge betweent two vertex then enter 1000): \n\n");
  for(i=1;i<=n;i++)
  {
       for(j=1;j<=n;j++)
       {
             scanf("%d",&adjacency[i][j]);
       }
  }
}

void graph::floydwarshall()
{
 
   for(i=1;i<=n;i++)
   {
        for(j=1;j<=n;j++)
        {
             distance[i][j]=adjacency[i][j];
        }
   }

   /* Updating distance matrix by taking intermediate vertex 'k'
      between every other vertices pair */

   for(k=1;k<=n;k++)
   {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(distance[i][k]+distance[k][j]<distance[i][j])
                {
                      distance[i][j]=distance[i][k]+distance[k][j];
                }
            }
        }
   }
}
void graph::print()
{
 
  printf("\n\nThe final distance matrix is: \n\n");
  for(i=1;i<=n;i++)
  {
      for(j=1;j<=n;j++)
      {
          printf("%d\t\t",distance[i][j]);
      }
      printf("\n");
  }
}

int main()
{
  graph graph;
  graph.get_data();
  graph.floydwarshall();
  graph.print();
  return 0;
}


OUTPUT:


Saturday, 27 May 2017

C++ Program to find the first Non-repeating character in a string

C++ Program and algorithm to find the first non-repeating character of  a string is given below and this question has been already asked in the interviews of following companies:-

Amazon, Goldman Sachs, DE shaw, MAQ software, MakeMyTrip, Payu, TejasNetwork, OLA, OATS System, Teradata, InfoEdge

Source:  geeksforgeeks

ALGORITHM:

1.  Declare an array arr[256]={0} /*initialize every element to zero */
2.  do For i=1 to len(string):
3.           arr[string[i]]=arr[string[i]]+1
4.  do For i=1 to len(string):
5.           if(arr[string[i]]==1):
6.                      char c=string[i]
7.                      break
8.  print 'c'.


Note:  we are using array of size 256 because we are indexing characters of string using their ASCII value. For more click here


PROGRAM:

#include <iostream>
#include <map>
#include <string.h>
using namespace std;

int main() 
{
 
 
       char string[100];
       int arr[256]={0};
       
          cout<<"\n\nEnter the String:\n\n";
       cin>>string;
       for(int j=0;j<strlen(string);j++)
       {
            arr[string[j]]++;
       }
       char c;
       for(int j=0;j<strlen(string);j++)
       {
            if(arr[string[j]]==1)
            {
                c=string[j];
                break;
            }
       }
       cout<<"\n\n";
       cout<<c<<"\n\n";

       
       return 0;
}


OUTPUT:


C++ Program for reversing an array in O(n) Time

Algorithm and its implementation to reverse an array in O(n) time is given below:

ALGORITHM:


step 1:    set j=0
step 2:    set k=n-1 /*n is the total number of elements in array */
step 3:    do While j<k:
step 4:             set: temp=array[j]
step 5:             set: array[j]=array[k]
step 6:             set: array[k]=temp
step 7:             set: j=j+1
step 8:             set: k=k-1    


PROGRAM:

#include <iostream>
using namespace std;

int main() {
  int t;    /*t is the test cases */
  cin>>t;
  for(int i=0;i<t;i++)
  {
       int n;    /*n is the number of elements */
       cin>>n;
       int arr[n];
       for(int j=0;j<n;j++)
       {
            cin>>arr[j];
       }
       int temp;
       int j=0;
       int k=n-1;
       while(j<k)
       {
           temp=arr[j];
           arr[j]=arr[k];
           arr[k]=temp;
           j++;
           k--;
       }
       cout<<"\n\nArray after reversal is: \n\n";
       for(j=0;j<n;j++)
       {
           cout<<arr[j]<<" ";
       }
       cout<<"\n\n";
  }
  return 0;
}


OUTPUT:


C++ Program to Check if two trees are Mirror


C++ Program to check if given two trees are mirror or not is given below along with its algorithm and output.

Asked in:  DE shaw, Amazon

Example of two mirror trees:

                5                                                   5                                 
              /    \                                               /   \
            /        \                                           /       \
          4          3                                       3         4
                    /    \                                   /   \
                  /        \                               /       \
                 1         2                           2          1

             (a)                                              (b)



         
                    
ALGORITHM

function CHECK(roota, rootb):
       IF  roota=NULL and rootb=NULL:
                   return true
       IF  roota=NULL or rootb=NULL:
                   return false
      return  (roota.data=rootb.data && CHECK(roota.left,rootb.right) &&
                                                             CHECK(roota.right,rootb.left))


PROGRAM:

#include <bits/stdc++.h>
using namespace std;


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

node *create_new_node(int data);
bool check_for_mirror(struct node *root1,struct node *root2);

int main()
{
      /*creating first binary tree*/

      node *root1=create_new_node(5);
      root1->left=create_new_node(3);
      root1->left->left=create_new_node(2);
      root1->left->right=create_new_node(1);
      root1->right=create_new_node(4);


      /*creating second binary tree*/


      node *root2=create_new_node(5);
      root2->left=create_new_node(4);
      root2->right=create_new_node(3);
      root2->right->left=create_new_node(1);
      root2->right->right=create_new_node(2);

      if(check_for_mirror(root1,root2))
      {
            printf("\n\nTrees are mirrors\n\n");
      }
      else
      {
            printf("\n\nTrees are not mirrors\n\n");
      }

      return 0;
}
node *create_new_node(int data)
{ 
       
       node *newnode=new node();
       newnode->data=data;
       newnode->left=newnode->right=NULL;
       return newnode;
}

bool check_for_mirror(struct node *root1,struct node *root2)
{
    if(root1==NULL && root2==NULL)
    {
         return true;
    }
    if(root1==NULL || root2==NULL)
    {
         return false;
    }

    return (root1->data==root2->data &&
             (check_for_mirror(root1->left,root2->right) &&
              check_for_mirror(root1->right,root2->left)));
}


OUTPUT


Thursday, 11 May 2017

Program for Insertion and Deletion at the beginning of Singly Linked List in Python

python program for the insertion and deletion operation at the beginning of singly linked list is given below. In this program we have two method. insert_at_beg() to insert the element in the beginning and delete_at_beg() to delete the element at the beginning of the linked list.

PROGRAM:

class Node:
 def __init__(self,data):
  self.data=data
  self.next=None

class LinkedList:
 def __init__(self):
  self.head=None
  
 def insert(self,data):
  if(self.head==None):
   self.head=Node(data)
  else:
   current=self.head
   while(current.next!=None):
    current=current.next
   current.next=Node(data)

 def insert_at_beg(self,data):
  newnode=Node(data)
  newnode.next=self.head
  self.head=newnode

 def delete_at_beg(self):
  current=self.head
  self.head=current.next
  del current

 def printlist(self):
  current=self.head
  while(current!=None):
   print current.data,
   current=current.next

myLinkList=LinkedList()
myLinkList.insert(25)
myLinkList.insert(45)
myLinkList.insert(78)
print("\n\nCreated Linked List is: \n")
myLinkList.printlist()
print("\n\nEnter the element you want to insert at the beginning: ")
element=int(input())
myLinkList.insert_at_beg(element)
print("\n\nThe updated Linked List after insertion at beginning: \n")
myLinkList.printlist()
print("\n\nThe updated Linked List after deletion at beginning:\n")
myLinkList.delete_at_beg()
myLinkList.printlist()


OUTPUT:


Read also: python program to create a singly Linked List 

Wednesday, 10 May 2017

Python Program to create a Singly Linked List

Python program is given below to create a singly Linked List. This program contains two classes first is class Node and the second is class LinkedList, Both the classes are discussed below.


Node Class:
Each node object must hold at least two pieces of information. First the data item in the node and the second is reference to the next node. A refrence to None means here that there is no next node. Note in the constructor that a node is initially created with next to None.

LinkedList class:
Whenever an object of LinkedList class is created it will initialize to none i.e there is no node in linked list. you can look at self.head=None. Whenever you will add a node in the LinkedList. First insert() method in the LinkedList will check if there a node is already created or not. If not then it will assign the head node to current else it will go forward till no node is found.

PROGRAM:

class Node:
 def __init__(self,data,next=None):
  self.data=data
  self.next=None

class LinkedList():
 def __init__(self):
  self.head=None

 def insert(self,data):
  if(self.head==None):
   n=Node(data)
   self.head=n
   return
  else:
   current=self.head
   while(current.next!=None):
    current=current.next
   current.next=Node(data)
   return
 def printing(self):
  if(self.head==None):
   print "Linked List is empty"
  else:
   current=self.head
   while(current!=None):
    print current.data,
    current=current.next
myLinkList=LinkedList()
myLinkList.insert(18)
myLinkList.insert(20)
myLinkList.insert(56)
myLinkList.insert(50)
print("\n\nThe created Singly Linked List is: \n\n")
myLinkList.printing()
print("\n\n")


OUTPUT:




See also: Python Program to insert node at any position in the singly Linked List

Simple Java Program to explain Methods Overloading

Basically, methods overloading is used to create methods that have the same name but different parameter lists and definitions. This technique is used when objects are required to perform similiar tasks but using different input parameters. When we call a method in an object Java matches up the method name first and then the number and type of the parameters to decide which one of definition is to execute. This process is known as Polymorphism

To create an overload method, we all have to do is to provide several different method definitions in the class, all with the same name but different in number and types of parameters. Simple java program is given below to explain method overloading. 

PROGRAM:

import java.util.Scanner;

class method_overloading
{
 
   int method(int l)
   {
          return l*l;
   }
   int method(int l,int b)
   {
      return l*b;
   }
   int method(int l,int b,int h)
   {
      return l*b*h;
   }

};
public class main_class
{
   public static void main(String args[])
   {
        Scanner in=new Scanner(System.in);

         method_overloading  m1=new method_overloading();
         int result;

         result=m1.method(20);
         System.out.print("\n\nArea of square is: "+result);

         result=m1.method(30,20);
         System.out.print("\n\nArea of Rectangle is: "+result);

         result=m1.method(20,30,40);
         System.out.print("\n\nVolume of the cuboidal is: "+result+"\n\n");

   }
}


OUTPUT:

 

Tuesday, 9 May 2017

Simple Java Program to explain constructors in Java

We know that all objects that are created must be given initial values. We can do this by two approaches. The first approach uses the dot operator to access the instance variables and then assigns value to them individually. But it can be a tedious approach to initialize all the variables of all the objects individually.

And the second approach is using the help of a method like get_data() initialize each object individually.
          example:          object.get_data(15,10);

It would be more concise and simpler to initialize an object when it is first created. Constructors in java enables and object to initialize itself when it is first created.

Constructor has the same name as the class itself.  Secondly then do not specify a return type even void.

Constructors in java are of two types:-
1.  Default constructor
2.  Parameterized constructor

Default Constructor:- 

A constructor that does not have any parameter is known as default constructor.
Default constructor provides the default values to the object like 0, null etc. depending on the type.

             ex:    Rectangle r1=new Rectangel()

Note: If there is no constructor in a class, compiler automatically creates a default constructor.

EXAMPLE:


import java.util.Scanner;

class Rectangle
{
   int length,breadth;

   void display()
   {
        Scanner in=new Scanner(System.in);
        System.out.print("\n\n");
        System.out.println("length = "+length);
        System.out.println("breadth = "+breadth);
        System.out.print("\n");
   }
};
public class main_class
{
   public static void main(String args[])
   {
         Rectangle r1=new Rectangle();
         r1.display();
   }
}


OUTPUT:



PARAMETERIZED CONSTRUCTOR :

A constructor which have parameter is known as parameterized constructor.

                ex:    Rectangle r1=new Rectange(10,20);

A parameterized constructor is used to assign different values to distinct objects.

EXAMPLE:

import java.util.Scanner;

class Rectangle
{
   int length,breadth;

   Rectangle(int l,int b)
   {
        length=l;
        breadth=b;
   }

   void display()
   {
        Scanner in=new Scanner(System.in);
        System.out.print("\n\n");
        System.out.println("length = "+length);
        System.out.println("breadth = "+breadth);
        System.out.print("\n");
   }
};
public class main_class
{
   public static void main(String args[])
   {
         Rectangle r1=new Rectangle(10,20);
         Rectangle r2=new Rectangle(30,40);
         r1.display();
         r2.display();
   }
}


OUTPUT:

 

C Program to Print a Linked List in Reverse Order

C Program  tp print the elements of a Linked List along with ouput is given below.

Example:
                   If Linked List is    12 -> 13 - > 15
                   Then output will be:   15->13->12

 Note:  Here we are printling the elements of linked list in reverse order without reversing 
             the linked list

ALGORITHM
 
FUNCTION(ROOT): 
If head=NULL:
         return
Else:
         FUNCTION(ROOT->NEXT)
         printf(root->data)

PROGRAM:
 
#include <stdio.h>
#include <stdlib.h>
struct node
{
   int data;
   struct node *next;
};
void reverse_print(struct node *root);
int main()
{
   struct node *head;

   /*Making  a  Linked List */

   head=(struct node*)malloc(sizeof(struct node));
   head->data=5;
   head->next=(struct node*)malloc(sizeof(struct node));
   head->next->data=9;
   head->next->next=(struct node*)malloc(sizeof(struct node));
   head->next->next->data=11;
   head->next->next->next=(struct node*)malloc(sizeof(struct node));
   head->next->next->next->data=14;
   head->next->next->next->next=NULL;

   printf("\nThe element of Linked List in reverse order are: \n\n");
   reverse_print(head);
   printf("\n");
   return 0;
}
void reverse_print(struct node *head)
{
   if(head==NULL)
   {
       return;
   }
   else
   {
       reverse_print(head->next);
       printf("%d -> ",head->data);
   }
}


OUTPUT:

 

Monday, 8 May 2017

Program to rotate an array to the left by N elements

This program will rotate an array to the left by n elements. C++ program along with output is given below.

Example:
 
            Let A[] ={  3, 5, 6, 12, 89 }
            r = 3   #rotate the array by r elements
           Then output will be :    { 6, 12, 89, 3, 5 }

Algorithm:

For i in range(0,r):
           temp=arr[0]
           for j in range(0,n-1):
                     arr[j]=arr[j+1]
           EndFor
           arr[j]=temp
EndFor


PROGRAM:

#include <stdio.h>
#define MAX 100000
void rotate(int arr[],int n);
int main()
{
   int n,array[MAX],r;

   printf("\nEnter the number of elements in array: ");
   scanf("%d",&n);
   printf("\nEnter the elements of the array: \n");
   for(int j=0;j<n;j++)
   {
         scanf("%d",&array[j]);
   }

      printf("\nEnter the number of elements by which you want to rotate array: ");
      scanf("%d",&r);
   for(int j=1;j<=r;j++)
   {
         rotate(array,n);
   }

      printf("\n\nArray after rotation: \n");
   for(int j=0;j<n;j++)
   {
         printf("%d ",array[j]);
   }
   return 0;
}
void rotate(int arr[],int n)
{
   int temp=arr[0];
   int i;
   for(i=0;i<n-1;i++)
   {
       arr[i]=arr[i+1];
   }
   arr[i]=temp;
}


OUTPUT:

Thursday, 4 May 2017

Implementation of Priority Scheduling Algorithm in Python

In priority scheduling algorithm, a priority is associated with each process and CPU is allocated to the process with the highest priority. If two processes have same priority then they will be execute in first come first serve order.

Example:

              Process             Burst Time            Priority
               P1                          11                          5
               P2                          10                          2
               P3                          15                          3
               P4                          14                          4
               P5                          13                          1

            The above processes will execute in the order   P5, P2,P3,P4,P1


Priorities can be defined either internally or externally. Internally defined priorites use some measurable quantity or quantities to compute the priority of a process. For example time limits, memory requirements, the number of open files, and ratio of I/0 burst to average CPU burst have been used in computing priorities.

External priorities are set by criteria outside the operating system such as importance of the process and amount of fund being paid for computer use.

A major problem with this priority scheduling algorithm is indefinite blocking or starvation. A process that is ready to run but waiting for the CPU can be considered block. Sometimes, priority scheduling algorithm can leave some  low priority process waiting indefinitely.

A solution to starvation or indefinite blockage is aging. Aging is technique of gradually increasing priority of a process that waits in the system for a long time.


PROGRAM:

 
#bt,wt,tat stands for burst time, waiting time, turn around time  respectively

print("Enter the number of processess: ")
n=int(input())
processes=[]
for i in range(0,n):
 processes.insert(i,i+1)

#Input Burst time of every process
print("\nEnter the burst time of the processes: \n")
bt=list(map(int, raw_input().split()))

#Input Priority of every process
print("\nEnter the priority of the processes: \n")
priority=list(map(int, raw_input().split()))
tat=[]
wt=[]

#Sorting processes burst time, on the basis of their priority
for i in range(0,len(priority)-1):
 for j in range(0,len(priority)-i-1):
  if(priority[j]>priority[j+1]):
   swap=priority[j]
   priority[j]=priority[j+1]
   priority[j+1]=swap

   swap=bt[j]
   bt[j]=bt[j+1]
   bt[j+1]=swap

   swap=processes[j]
   processes[j]=processes[j+1]
   processes[j+1]=swap

wt.insert(0,0)
tat.insert(0,bt[0])

#Calculating of waiting time and Turn Around Time of each process
for i in range(1,len(processes)):
 wt.insert(i,wt[i-1]+bt[i-1])
 tat.insert(i,wt[i]+bt[i])

#calculating average waiting time and average turn around time
avgtat=0
avgwt=0
for i in range(0,len(processes)):
 avgwt=avgwt+wt[i]
 avgtat=avgtat+tat[i]
avgwt=float(avgwt)/n
avgwt=float(avgtat)/n
print("\n")
print("Process\t  Burst Time\t  Waiting Time\t  Turn Around Time")
for i in range(0,n):
 print(str(processes[i])+"\t\t"+str(bt[i])+"\t\t"+str(wt[i])+"\t\t"+str(tat[i]))
 print("\n")
print("Average Waiting time is: "+str(avgwt))
print("Average Turn Around Time is: "+str(avgtat))
 
OUTPUT:

 

Wednesday, 3 May 2017

C++ Program to check whether an array is subset of another array - Hashing

In this program we will take two arrays and check whether that array 2 is a subset of array 1 or not. C++ program along with output is also given below.

For example:

1.  Let A1[] ={ 12, 14, 56, 6, 8 },   Let A2[]={ 14, 8, 6}
    Array A2 is subset of A1

1.  Let A1[] ={ 12, 14, 56, 6, 8 },   Let A2[]={ 14, 8, 7}
    Array A2 is not a subset of A1 because 7 is  not present in the A1.

Algorithm:

1.   Create two hash table for array 2 and array 1 where value of arrays will be key and their
      count will be value corresponding to that key.
2.   Traverse the array 2 and check the number of occurrence of each element of array 2 in array 1.
3.   If number of occurrences are same then return true else return false.


PROGRAM:

#include <stdio.h>
#include <unordered_map>
using namespace std;
unordered_map <int,int> map1;
unordered_map <int,int> map2;

int check(int n2,int arr2[]);
int main()
{
   int arr1[10],arr2[10],n1,n2;

   map1.reserve(10);
   map2.reserve(10);

   printf("\nEnter the number of elements in array 1: ");
   scanf("%d",&n1);
   printf("\nEnter the elements of array 1: \n");
   for(int i=0;i<n1;i++)
   {
        scanf("%d",&arr1[i]);
        map1[arr1[i]]++;
   }

   printf("\nEnter the number of elements in array 2: ");
   scanf("%d",&n2);
   printf("\nEnter the elements of array 2:\n");
   for(int i=0;i<n2;i++)
   {
        scanf("%d",&arr2[i]);
        map2[arr2[i]]++;
   }

   if(check(n2,arr2))
   {
        printf("\nArray 2 is an subset of Array 1\n");
   }
   else
   {
        printf("\nArray 2 is not subset of Array 1\n");
   }
   return 0;
}
int check(int n2,int array2[])
{
   for(int i=0;i<n2;i++)
   {
          if(map2[array2[i]]!=map1[array2[i]])
          {
               return 0;
          }
   }
   return 1;
}


OUTPUT: