Question

The intersection of two lists L1 and L2, L1 ∩ L2, is defined as the list containing elements in both L1 and L2 only. Given two sorted lists L1 and L2, write a function, called intersection, to compute L1 ∩ L2 using only the basic list operations. The intersection function is defined as follows template list intersection( const list & L1, const list & L2);

C++

Answer 1

//since you haven't mentioned more aboout list
//i have created list class.
//see the list.h for the methods that are implemented.
//every method that performs on list object are present in list.h
//dont' confuse.

--------------- list.h ------------

#ifndef __list_h
#define __list_h
#include<iostream>
using namespace std;
class list
{
   public:
       int *array;
       int maxSize;
       int length;
       list(int size)
       {
           //check if size is greater than 0 if negative
           //size is given set to default size;
           size = size>0?size: 5;
           maxSize = size;
           array = new int[maxSize];
           length = 0;
       }
       //overload the operator [] to access the array elements.
       int operator[] (int ind)
       {
           if(!isEmpty() && ind >= 0 && ind < length)
           {
               return array[ind];
           }
           else
           {
               cout<<"\nError: Index out of range."<<endl;
               return -1;
           }
          
       }
       //push the value if there is space and
       //insert in sorted order.
       void push(int val)
       {
           if(length < maxSize)
           {
               int i;
               for(i = length-1; (i>=0 && array[i] > val);i--)
               {
                   array[i+1] = array[i];
               }
               array[i+1] = val;
               length++;
           }
           else
           {
               cout<<"\nList is full\n";
           }
       }
       //remove element at given index.
       void remove(int ind)
       {
           if(!isEmpty() && ind >= 0 && ind < length)
           {
               for(int i = ind;i<length-1;i++)
               {
                   array[i] = array[i+1];
               }
               length--;
           }
       }
       //remove all occurances of val in list.
       void removeAll(int val)
       {
           if(length > 0)
           {
               int ind = indexOf(val);
               if(ind != -1)
               {
                   while(array[ind] != val)
                   {
                       remove(ind);
                   }
               }
               else
               {
                   cout<<"\nValue:"<<val<<" not found"<<endl;
               }
           }
           else
           {
               cout<<"\nList is empty"<<endl;
           }
       }
       //print the array elements.
       void print()
       {
           cout<<"\nList of Size: "<<length<<"\n"<<endl;
           if(length == 0)
           {
               cout<<"\n{}"<<endl;
               return;
           }
           cout<<"{ ";
           for(int i = 0;i<length;i++)
           {
               cout<<array[i];
               if(i<length-1)
               {
                   cout<<" , ";
               }
           }
           cout<<" }\n";
       }
       //returns the index of given value
       //it uses binary search to locate the
       //the values since array is in sorted order.
       int indexOf(int val)
       {
           int left = 0;
           int right = length-1;
           int middle;
          
           while(left <=right)
           {
               middle = left + (right - left) / 2;
               if(array[middle] == val)
               {
                   return middle;
               }
               if(array[middle] < val)
               {
                   left = middle + 1;
               }
               else
               {
                   right = middle - 1;
               }
           }
           return -1;
       }
       //returns the total elements in array.
       int size()
       {
           return length;
       }
       //returns if array is empty or not.
       bool isEmpty()
       {
           return length == 0?true:false;
       }
       //clears the values in array and sets the length to 0.
       void clear()
       {
           for(int i = 0;i<length;i++)
           {
               array[i] = 0;
           }
           length = 0;
       }};
#endif

//--------------------------- main.cpp ----------------------------

//since you haven't mentioned more aboout list
//i have created list class.
//see the list.h for the methods that are implemented.
//every method that performs on list object are present in list.h
//dont' confuse.

#include "list.h"
#include<iostream>

using namespace std;

//since i have used list class defined can't use const in function declaration.
list intersection(list &L1, list &L2)
{
   //get the sizes of two lists passed.
   int size1 = L1.size();
   int size2 = L2.size();
  
   //we have to compare the list with smaller elements
   //to the other.
   //other wise it will take time
   if(size1<size2)
   {
       //if list 1 has lesser lemenets
       //create res list of size1.
       list res(size1);
       //iterate through list one elements
       for(int i =0;i<size1;i++)
       {
           //first check if i_th value of L1 is not in result list
           //if not present then
           // also check for presence of i_th value in L2 .
           if(res.indexOf(L1[i]) == -1 && L2.indexOf(L1[i])!= -1)
           {
               //if both conditions satisfy insert L1[i] to the result array
               res.push(L1[i]);
           }
       }
       //finally return the result.
       return res;
   }
   else
   {
       //result list
       list res(size2);
       //iterate through list 2(smaller one)
       for(int i =0;i<size2;i++)
       {
           //if check for list2 value in result is not already present.
           //and list2 value in list1
           //then add to the result list.
           if(res.indexOf(L2[i]) == -1 && L1.indexOf(L2[i])!= -1)
           {
               res.push(L2[i]);
           }
       }
       //return it.
       return res;
   }

}
int main()
{
   int len = 10;
  
   list one(len);
   list two(len);
   //Test - 1
   //list one is larger with 10 elements 1 - 10
   //list two smaller with 5 elements 0 - 4
   for(int i = 1;i<=len;i++)
   {
       one.push(i);
   }
   for(int i= 0;i<len/2;i++)
   {
       two.push(i);
   }
   cout<<"\n---------------- Test 1 ----------------------\n";
   cout<<"\n---- List 1 --------\n";
   one.print();
   cout<<"\n---- List 2 --------\n";
   two.print();
   //get the intersection of them it should be 1 - 4.
   list common = intersection(one,two);
   cout<<"\n---------Intersection------\n";
   common.print();
  
   //clear both the list values.
   one.clear();
   two.clear();
  
  
   cout<<"\n---------------- Test 2 ----------------------\n";
   for(int i = len/2;i<=len;i++)
   {
       one.push(i);
   }
   for(int i= 0;i<len;i++)
   {
       two.push(i);
   }
  
   cout<<"\n---- List 1 --------\n";
   one.print();
   cout<<"\n---- List 2 --------\n";
   two.print();
   //get the intersection of them it should be 5,6,7,8,9.
   common = intersection(one,two);
   cout<<"\n---------Intersection------\n";
   common.print();
  
   //clear both the list values.
   one.clear();
   two.clear();

   cout<<"\n---------------- Test 3 ----------------------\n";
   for(int i = len/2;i<len-1;i++)
   {
       one.push(i);
       one.push(i);
   }
   //to check sorted insertion.
   one.push(1);
   for(int i= 0;i<len;i++)
   {
       two.push(i);
   }
  
   cout<<"\n---- List 1 --------\n";
   one.print();
   cout<<"\n---- List 2 --------\n";
   two.print();
   //get the intersection of them it should be 1,5,6,7,8.
   common = intersection(one,two);
   cout<<"\n---------Intersection------\n";
   common.print();
  
   //clear both the list values.
   one.clear();
   two.clear();

   return 0;
}

//-------------- OUTPUT --------------

//PLEASEEEEEEEEEEEEEE LIKE THE ANSWER......