Hashing
Go to ProblemsHashing Implementation Details
C
C has nothing native for hashmap We need to write one ourselves.
C++ :
C++ has unordered_map which is implemented via hashing. We will discuss treemaps in C++ as well later, which in practice seem to behave faster in C++.
Declaration
unordered_map<int, int> A; // declares an empty map. O(1)
Adding an key, value pair :
A.insert({key, value}); // O(1) time on average
Find the value for key = K:
if (A.find(K) == A.end()) return null; // means that K does not exist in A.
else return A[K]; // O(1) average case. Rare worst case O(n).
Size ( number of elements ) of the vector :
A.size() // O(1)
Erase from the map :
if (A.find(K) != A.end()) A.erase(A.find(K));
OR A.erase(K);
JAVA :
Now we come to one of the most popular data structures in Java, HashMap.
Declaration :
HashMap<Integer, Integer> A = new HashMap<Integer, Integer>(); // declares an empty map.
Adding an key, value pair :
A.put(key, value); // O(1) time on average
Find the value for key = K:
A.get(K) // null if the key K is not present
A.containsKey(K) tells if the key K is present.
// Both operations O(1) average time. O(n) rare worst case
Size ( number of elements ) of the vector :
A.size() // O(1)
Erase from the map :
A.remove(K);
PYTHON
Python has dictionaries which serve the same purpose.
Declaration :
A = {}
Adding an key, value pair :
A[key] = value // O(1) average time. O(n) worst case
Find the value for key = K:
A[K] // O(1) average, O(n) worst
Size ( number of elements ) of the vector :
len(A) // O(1)
Erase from the map :
del A[K] // O(1) average, O(n) worst
Hashing Problems
Hash search
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Colorful Number | 150 |
|
44:55 | |
| Largest Continuous Sequence Zero Sum | 200 |
|
68:45 | |
| Longest Subarray Length | 200 |
|
57:25 | |
| First Repeating element | 200 |
|
21:50 | |
| 2 Sum | 300 |
|
49:18 | |
| 4 Sum | 325 |
|
72:27 | |
| Valid Sudoku | 325 |
|
50:42 | |
| Diffk II | 375 |
|
29:06 |
Key formation
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Pairs With Given Xor | 200 |
|
27:20 | |
| Anagrams | 350 |
|
46:36 | |
| Equal | 350 |
|
71:23 | |
| Copy List | 450 |
|
56:18 |
Maths and hashing
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Check Palindrome! | 200 |
|
18:55 | |
| Fraction | 450 |
|
81:53 | |
| Points on the Straight Line | 450 |
|
78:52 |
Incremental hash
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| An Increment Problem | 200 |
|
50:48 | |
| Subarray with given XOR | 200 |
|
56:12 | |
| Two out of Three | 200 |
|
33:54 | |
| Substring Concatenation | 1000 |
|
71:27 |
Hashing two pointer
| Problem | Score | Companies | Time | Status |
|---|---|---|---|---|
| Subarray with B odd numbers | 200 |
|
52:45 | |
| Window String | 350 |
|
82:16 | |
| Longest Substring Without Repeat | 350 |
|
51:12 |
