Week 8: Hash Tables

Hash Tables and Hash Sets?

Below are examples of a Table where Values are mapped to a Key. Each Key is unique and they map to “one” Value.

In the above cases we specifically mapped values to specific keys. How would we be able to determine if a specific object is within our Table?

In the first table where the Values have the same value as their Key is easy, but for the second table not as much.

Even if we know which Key it belonged to we will have to traverse the Value to check.

(Key, Value)
  - hashTable.put(key, value)   // returns true
  - hashTable.get(key)          // returns value, or NULL
  - hashTable.containsValue(value)   // returns true or false
  - hashTable.containsKey(key)  // returns true or false
  - hashTable.isEmpty()         // returns true or false
  - hashTable.size()            // returns int

Note: HashMaps are essentially equivalent to Hashtables except HashMaps can have null as a Key or Value.

HashSets also support null for Keys, but do not have a Value

What is a Hash?

Hashtables and HashMaps employ a hashing function to map objects to a Key. In Java this is through the method int hashCode() which is part of the Object class.

The returned hash should have the same value for eqivalent objects, this greatly supports the use of HashTables through the previous use case above.

In some cases hashCode() can return identical hash values for different objects. This is known as a collision, how would you handle collisions in a Hashtable? (It is important to note that Hashtables utilizes an Array internally).

Legacy Note: Uses a hash function to map a key to a specific place in memory (array). That memory is then set to ‘value’.

1) Count number of unique elements in array

Given an integer array, return the number of unique integers in the array.

Input: [1,2,3,2,1,2,2,1]
Output: 3

Input: [1,2,3,4,5]
Output: 5

2) Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

Explanation: Since nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]

3) Check if sentence is pangram

Given a sentence (string), return true if the sentence is a pangram, false otherwise.

A pangram is a sentence that contains at least one occurence of every letter in the english language.

Input: "thequickbrownfoxjumpsoverthelazydog"
Output: true

Input: "The quick brown fox jumps over the lazy dog"
Output: true

Input: "PANDA"
Output: false

Input: "Sphinx of black quartz judge my vow"
Output: true

4) Count number of good pairs in array

Given an array of integers, return the number of good pairs.

A good pair is a pair (i, j) that meets the following criteria:

• nums[i] == nums[j]
• i < j
  • This prevents duplicate pairs. For example (i, j) is valid, but (j, i) isn’t.

Input: nums = [1,2,3,1,1,3]
Output: 4

Explanation: There are 4 good pairs (nums[0], nums[3]), (nums[0], nums[4]), (nums[3], nums[4]), (nums[2], nums[5]).

Input: nums = [1,1,1,1]
Output: 6

Explanation: Each pair in the array are good

Input: nums = [1,2,3]
Output: 0

5) Count numbers smaller than current number

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j’s such that j != i and nums[j] < nums[i].

Return the answer in an array.

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]

Explanation:

• nums[0]=8 has four smaller numbers than it: (1, 2, 2, 3)
• nums[1]=1 has zero smaller numbers than it: (0)
• nums[2]=2 has one smaller number than it: (1)
• nums[3]=2 has one smaller number than it: (1)
• nums[4]=3 has three smaller numbers than it: (1, 2, 2)

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Input: nums = [7,7,7,7]
Output: [0,0,0,0]