A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1

Chapter 8

These are the solutions to the exercises found in the section ​Exercises​.

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:

   def get_intersection(array1, array2):
       intersection = []
       hash_table = {}
   
       for value in array1:
           hash_table[value] = True
   
       for value in array2:
           if hash_table.get(value):
               intersection.append(value)
   
       return intersection

   This algorithm has an efficiency of O(N).

2. The following implementation checks each string in the array. If the string isn’t yet in the hash table, the string gets added. If the string is in the hash table, that means it’s been added before, which means it’s ...