A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Chapter 8

These are the solutions to the exercises found in the section, ​Exercises​. The solutions provided here are in JavaScript, but you can find the solutions in Python and Ruby in the code download.^[8]

1. The following implementation first stores the values of the first array in a hash table and then checks each value of the second array against that hash table:

   function getIntersection(array1, array2) {
     let intersection = [];
     let hashTable = {};
   
     for(let i = 0; i < array1.length; i++) {
       hashTable[array1[i]] = true;
     }
   
     for(let j = 0; j < array2.length; j++) {
       if(hashTable[array2[j]]) {
         intersection.push(array2[j]);
       }
     }
   
     return intersection;
   }

   This algorithm has an efficiency of O(N).

2. The following ...