1. Intro to hashMaps #

Created Tuesday 18 February 2020

Q1) Given a sentence, return the maximum occurring character: Ans: Simple hack, make a 256 sized array. Traverse the array and keep the characters at its ASCII value. While doing this, keep a max variable and a max character, keep updating it if you find a bigger array. Done in single scan. Catch: The data in the array was subset of some finite set, and also that the data had a one-one relation with the indexes. Terminology: Key: the thing which is used to **call/query **our map.

Q2) Find the maxium occurring word(may not be meaningful) in a sentence. Ans: Here the universal set is infinite. As we do not have a limit on the length and the permutation. Here we will need to make a map, i.e the key(here a word) with a value(no of times it has occurred). This is called a map, key-value pair or dictionary.

The map interface:

  1. insert(key, value)
  2. getValue(key)
  3. delete(key)

Ways of implementing this:

  1. Linked list - every node has a pair<key, value>
    1. insert() - O(n), we have to find the node, update it if found. Or add a note if key is not present.
    2. getValue() - We need to do linear search. O(n)
    3. delete(key) - check if node is present. Delete if found. O(n)

Very bad approach. Our ideal is the array - O(1) access.

  1. BST, we are using some balanced BST.

We should have some ordering. In words we can do lexicographical.

  1. insert() - O(logn), we have to find the node, update it if found. Or add a note if key is not present.
  2. getValue(logn) - search. O(logn)
  3. delete(key) - check if node is present. Delete if found. O(logn)

Very good approach. Our ideal is the array - O(1) access. Implement this.

  1. We use hash table. For some wise thing, we will first see STL offering. We will see all the theory etc afterwards.