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:
- insert(key, value)
- getValue(key)
- delete(key)
Ways of implementing this:
- Linked list - every node has a pair<key, value>
- insert() - O(n), we have to find the node, update it if found. Or add a note if key is not present.
- getValue() - We need to do linear search. O(n)
- delete(key) - check if node is present. Delete if found. O(n)
Very bad approach. Our ideal is the array - O(1) access.
- BST, we are using some balanced BST.
We should have some ordering. In words we can do lexicographical.
- insert() - O(logn), we have to find the node, update it if found. Or add a note if key is not present.
- getValue(logn) - search. O(logn)
- 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.
- We use hash table. For some wise thing, we will first see STL offering. We will see all the theory etc afterwards.
- Note: access and search are two different things. They are the same in hashmaps.