Chapter 8

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

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 a duplicate! This algorithm has a time complexity of O(N):

   ​	​def​ ​find_duplicate​(array):
   ​	hash_table = {}
   ​
   ​	​for​ value ​in​ array:
   ​	​if​ hash_table.get(value):
   ​	​return​ value
   ​	​else​:
   ​	hash_table[value] = True
   ​
   ​	​return​ None

3. The following implementation begins by creating a hash table out of all the characters we encounter in the string. Next, we iterate over each character of the alphabet and check to see whether the character is contained within our hash table. If it isn’t, it means the character is missing from the string, so we return it:

   ​	​def​ ​find_missing_letter​(string):
   ​	hash_table = {}
   ​
   ​	​for​ char ​in​ string:
   ​	hash_table[char] = True
   ​
   ​	alphabet = ​"abcdefghijklmnopqrstuvwxyz"​
   ​
   ​	​for​ char ​in​ alphabet:
   ​	​if​ ​not​ hash_table.get(char):
   ​	​return​ char
   ​
   ​	​return​ None

4. The following implementation begins by iterating over each character in the string. If the character doesn’t yet exist in the hash table, the character is added to the hash table as a key with the value of 1, indicating the character has been found once so far. If the character is already in the hash table, we simply increment the value by 1. So if the character "e" has the value of 3, it means the "e" exists three times within the string.

   Then we iterate over the characters again and return the first character that only exists once within the string. This algorithm is O(N):

   ​	​def​ ​first_non_duplicate​(string):
   ​	hash_table = {}
   ​
   ​	​for​ char ​in​ string:
   ​	​if​ hash_table.get(char):
   ​	hash_table[char] += 1
   ​	​else​:
   ​	hash_table[char] = 1
   ​
   ​	​for​ char ​in​ string:
   ​	​if​ hash_table.get(char) == 1:
   ​	​return​ char
   ​
   ​	​return​ None