Question

Write a program to compute intersection of two sorted array of integers and compute the CPU time for different sets of unsigned integers generated by a random number generator. Test this using the same data sets: atleast 3 of size 1000 integers, atleast 3 of size 10000 integers, atleast 3 of size 100000 integers, atleast 3 of one million integers and atleast 3 of size 10 million integers DONT FORGET CPU TIME FOR EACH ONE

NO HASH SET

Answer 1

For the above program, the following are the things we need to have into consideration.

1. We need to run this for 5 different sets of integers and 3 times each.
2. We need to use random generator in order to find the array elements.

Following is the code in java with the output having the time taken.

import java.util.Arrays;
import java.util.Random;

public class Intersection {
   public static int intersection(int a[], int b[])
   {
       int i = 0, j = 0;
       while(i<a.length && j<b.length) {
           if(a[i] == b[j]) {
               return a[i];
           }else if(a[i] > b[j]) {
               j++;
           }else {
               i++;
           }
       }
       return -1;
   }
   public static void main(String args[]) {
       Random rand = new Random();
       int integers = 1000;
       // Runing it for 1000, 10000, 100000, 1000000, 10000000
       for(int i = 0;i<5;i++) {
           // running three times same number
           for(int j = 0;j<3;j++) {
               // start time
               long start_time = System.currentTimeMillis();
           //declaring the integers
               int a[] = new int[integers];
               int b[] = new int[integers];
               // putting the integers in the array
               for(int x = 0;x<integers;x++) {
                   a[x] = rand.nextInt(integers) + 1;
                   b[x] = rand.nextInt(integers) + 1;
               }
               // Sort the array
               Arrays.sort(a);
               Arrays.sort(b);
              
               // Finding the intersection
               intersection(a, b);;
               // end_time
               long end_time = System.currentTimeMillis();
               // Printing the time
               System.out.println("Integers: " + integers + ", Iteration: " + (j+1) + " Time Taken: " + (end_time - start_time));
           }
           integers = integers*10;
       }
      
   }
}

Following is the snippet of the above program and time taken is in milli seconds:

That was a nice question to answer
Friend, If you have any doubts in understanding do let me know in the comment section. I will be happy to help you further.
Please like if you think effort deserves a like.
Thanks