Graph - Adjacency List

#include<vector>

#include<iostream>

class Graph{

public:

     //n is the number of vertices in graph

     Graph(const int n): numberOfVertices(numerOfVertices),numberofEdges(0),adjList(n)

     {

         

     }

     //# of vertices

     const int Vertices()

     {

         return numberOfVertices;

     }

     //# of Edges

     const int Edges()

     {

          return numberofEdges;

     }

     void addEdge(int v, int w)

     {

          adjList[v].push_back(w);

          adjList[w].push_back(v);

          ++numberofEdges;

     }

     void  adjVertices(int v)

     {

        std::cout<<"Adjacent vertices of"<< v <<std::endl;

        for(auto &x : adjList[v])

           std::cout<< x << std::endl;

     }

private:

    int numberOfVertices;

    int numberofEdges;

    std::vector< std::vector<int> > adjList;

};

int main()

{

     Graph G(10);

     G.addEdge(3, 4);

     G.addEdge(0, 2);

     G.addEdge(0, 4);

     G.addEdge(0, 9);

     G.adjVertices(0);

     G.adjVertices(4);

}

Write String reverse

#include<stdio.h>
char * strrev(char* str)
{
     int length=0;
     char* str1=str;

     while(*str++)
        ++length;

     str=str1;
     char  temp;

     for ( int i=0; i< length/2; ++i)
     {
           temp= *(str +i);
           *(str +i) = *(str+length -1-i);
           *(str+length -1-i)= temp;
     }

     return str1;
}
int main()
{
    char str[]="Hello World!";
    strrev(str);
    printf("Reversed str:%s", str);

    return 0;

}

Write String copy operation.

#include<stdio.h>

char* mystrcpy(char * dest, char* source )
{
   char* dest1=dest;

   while(*dest++ = *source++)
   {
   }
   return dest1;

}
int main()
{

    char str2[30];
    char str1[]="Hello World!";
    char* str3=mystrcpy(str2,str1);
    printf("Str2 : %s\n", str2);
    printf("Str3 : %s", str3);
    return 0;
}

Linked list implementation with following operations:
1. Add Node.
2. Display linked list.
3.Remove duplicate Nodes
4. Delete nth Node from linked list
5. Add 2 numbers and create new linked list  from 2 linked lists, if the first position of number is placed in the head of linked lists.

#include<iostream>
#include<conio.h>
using namespace std;
template<typename T>
struct Node{
       T data;
       Node* next;
};
template<typename T>
class linkedList
{
      private:
          Node<T>* findNode(T x);
         
      public:
          Node<T>* head;
          linkedList();
          ~linkedList();
          void addNode(T info);         
          int  display();
          int removeDuplicate();
          int deleteNthNode(Node<T>*);
          linkedList<T> addTwoLinkedList(linkedList& x);//Assume number in liked list in reverse order.
                                 //The integer in 1's position is in head;
         
};
template <typename T>
linkedList<T> linkedList<T>::addTwoLinkedList(linkedList<T>& x)
{
      linkedList<int> result;
      Node<T> * tmp1=head;
      Node<T>*  tmp2=x.head;
      T val=0;
      T carry=0;
      while(tmp1)
      {
           val+=tmp1->data;
           tmp1=tmp1->next;
           while(tmp2)
           {
               val+=tmp2->data;
               tmp2=tmp2->next;
               break;
           }
           carry= val%10;
           val=val/10;
           if(carry > 0)
              result.addNode(carry);      
      }
      carry=val%10;
      val=val/10;
      if(carry>0)
         result.addNode(carry);
     
      while(tmp2)
      {
          val+=tmp2->data;
          tmp2=tmp2->next;
          carry= val%10;
          val=val/10;
          if (carry >0)
             result.addNode(carry);           
      }
      carry=val%10;
      val=val/10;
      if(carry > 0)
         result.addNode(carry);
      if(val > 0)
        result.addNode(val);  
      return result;
}
template<typename T>
Node<T>* linkedList<T>::findNode(T x)
{
    if( head == NULL)
       return NULL;
    Node<T>* tmp= head;
    while(tmp)
    {
        if(tmp->data==x)
            return tmp;
        else
            tmp=tmp->next;
    }
    return NULL;
}
template<typename T>
int linkedList<T>::deleteNthNode(Node<T>* n)
{
    if(n)
     return 0;
    Node<T>* tmp=n->next;
    n->next=tmp->next;
    n->data=tmp->data;
    delete tmp;
    return 1;
}
template<typename T>
linkedList<T>::linkedList()
{
   head=NULL;
}
template<typename T>
linkedList<T>::~linkedList()
{
   Node<T>* tmp;
   Node<T>* prev=head;
   while(prev)
   {
       tmp= prev;
       prev=prev->next;
       delete tmp;             
   }
                        
}
template<typename T>
void linkedList<T>::addNode(T info)
{
     Node<T>* tmp=new Node<T>();
     tmp->data=info;
     tmp->next=NULL;
     if(head==NULL)
     {
         head=tmp;        
     }
     else
     {
         Node<T>* prev=head;
         Node<T>* tmp1=head->next;
         while(tmp1)
         {
              prev=tmp1;
              tmp1=tmp1->next;
         }
         prev->next=tmp;
     }        
}
template<typename T>
int linkedList<T>::display()
{
     if(head==NULL)
        return 0;
     Node<T>* tmp=head;
     while(tmp)
     {
         cout<<tmp->data<<endl;
         tmp=tmp->next;
     }
     return 1;
}
template<typename T>
int  linkedList<T>::removeDuplicate()
{
    if(head==NULL)
      return 0;
    Node<T>* prev=head;
    Node<T>* tmp;
    for(Node<T>* current=head->next; current !=NULL;)
    {   
         Node<T>* runner;
         for(runner=head; runner !=current; runner=runner->next)
         {
              if(current->data== runner->data)
              {
                   tmp= current;
                   prev->next=current->next;
                   current=current->next;
                   delete tmp;  
                   tmp=NULL;
                   break;               
              }          
         }
         if(current==runner)
         {
                 prev=current;
                 current=current->next;
         }
    }
    return 1;  
}
int main()
{
    linkedList<int> l;
    l.addNode(1);
    l.addNode(1);
    l.addNode(3);
    l.addNode(1);
    cout<<"Display l"<<endl;
    l.display();
   
    linkedList<int> m;
    m.addNode(2);
    m.addNode(3);  
    m.addNode(4);
    m.addNode(5);
    cout<<"Display m:"<<endl;
    m.display();
   
    cout<<"Display sum:"<<endl;
    linkedList<int> sum=l.addTwoLinkedList(m);
    sum.display();
    cout<<"Remove Duplicates"<<endl;
    l.removeDuplicate();
    l.display();
    cout<<"Remove head"<<endl;
    l.deleteNthNode(l.head);
    l.display();
   
    getch();
}

Given a list of ranges and provide anew range and find missing ranges coming in between the newly provided range. For example if you have ranges [5,10], [15,19], [ 17,24] and provide a new range [3,28] . Missing ranges are [3,4],[11,14] and [25,28].

#include<iostream>
#include<map>
#include<utility>
#include<conio.h>
using namespace std;
typedef pair<int,int> int_pair;
int main()
{
    map<int,int> myMap;
    myMap.insert(int_pair(6,10));
    myMap.insert(int_pair(15,19));
    myMap.insert(int_pair(17,24));

    int_pair new1(3,25);
    typedef map<int,int>::iterator it_myMap;
    int left=new1.first;
    int right=0;
    map<int,int>  result;
    int val=0;
    for(it_myMap it =myMap.begin();  it!=myMap.end(); ++it)
    {
        if(((it->first) - left )> 1)
        {
           val=it->first;       
           right= --(val);
           result.insert(int_pair(left,right));
           left=++(it->second);
          
        }
        else
           left= ++(it->second);
    }
    it_myMap it= --(myMap.end());
    if(it->second < new1.second)
       result.insert(int_pair((it->second), new1.second));
    cout<<result.size()<<endl;
   
    for(it_myMap it =result.begin();  it!=result.end(); ++it)
    {
         cout<<it->first<<" "<<it->second<<endl;
    }
    getch();
         
}

Check whether  two given arrays are permutation of each other in O(n) time by using O(1) space.
#include<iostream>
#include<set>
#include<algorithm>

     
bool ArraysPermute(int  array1[],int size1, int  array2[], int size2)
{      
       if( size1  != size2)          
           return false;
       else
       {      
           std::set<int> first_set(array1, array1+size1);
           std::set<int> second_set(array2, array2+size2);
     
           std::pair<std::set<int>::iterator,std::set<int>::iterator> myPair=std::mismatch(first_set.begin(),first_set.end(),second_set.begin());
         
           if( *myPair.first != *myPair.second)
               
                return false;
            else
                return true;
       }
}


int main()
{    
    int array1[] ={1,2,3,5};
    int array2[]={1,2,4,3};
   
    if(ArraysPermute(array1,sizeof(array1)/sizeof(int), array2, sizeof(array2)/sizeof(int)))
        std::cout<< " Arrays are permutation of each other\n";
    else
        std::cout<< " Arrays are not permutation of each other\n";
     
    return 0;
}

Find a set of pairs from a set of integers

The solution is implemented in C++ by using STL ( Standard Template Library).

1. (a,b) and (b,a) are allowed

#include<map>
#include<iostream>

int main()
{
std::multimap<int,int> A;
int num[4]={2,4,5,6};
for(int i=0;i<4;++i)
{
   for(int j=0;j<4;++j)
   {
      if(i!=j)
      {
         A.insert(std::pair<int,int>(num[i],num[j]));
      }
   }
}

for( auto &k : A)
  std::cout<<k.first<<","<<k.second<<"\n";

return 0;
}

2. Either (a,b) or (b,a) is allowed

#include<map>
#include<iostream>

int main()
{
std::multimap<int,int> A;
int num[4]={2,4,5,6};
for(int i=0;i<4;++i)
{
   for(int j=0;j<4;++j)
   {
      if(i!=j)
      {
         A.insert(std::pair<int,int>(num[i],num[j]));
      }
   }
}

for( auto &k : A)
  std::cout<<k.first<<","<<k.second<<"\n";

return 0;
}