while learning hashing in python I generally get confused about different terminology and somehow I think O(n^2) is not that bad but now after solving questions I am getting a feeling of hashmap so before jumping to questions we should know about dictionaries built-in functions

Dictionaries --->

1. len(dictionary): Returns the number of key-value pairs in the dictionary.

2. dictionary.keys(): Returns a list of all the keys in the dictionary.

3. dictionary.values(): Returns a list of all the values in the dictionary.

4. dictionary.items(): Returns a list of all the key-value pairs in the dictionary.

5. dictionary.get(key, default): Returns the value for the specified key if it exists in the dictionary. If the key does not exist, it returns the specified default value.

6. dictionary.pop(key, default): Removes and returns the value for the specified key if it exists in the dictionary. If the key does not exist, it returns the specified default value.

7. dictionary.update(other_dictionary): Updates the dictionary with the key-value pairs from the other_dictionary.

8. dictionary.clear(): Removes all the key-value pairs from the dictionary.

9. key in dictionary: Returns True if the specified key exists in the dictionary, otherwise returns False.

10. dictionary.copy(): Returns a shallow copy of the dictionary

questions -->

1. Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

expectation:

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

in this example the majority element is 3 and it appears more than n/2 times

so in this question first we need to create a dictionary after that check if the iteration value is present in dict or not if persent increase its value

now important iteration in which we retrieved the key and value at the same time and then check the value if it is greater then n/2

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count_map = {}
        for num in nums:
            if num in count_map:
                count_map[num] +=1
            else:
                count_map[num] = 1
        majority_count = len(nums)//2
        for nums , count in count_map.items():
            if count > majority_count:
                return nums

2 Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

• MyHashMap() initializes the object with an empty map.

• void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.

• int get(int key) returns the value to which the specified key is mapped, or 1 if this map contains no mapping for the key.

• void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

in this first, we learn about the implementation of python

class MyHashMap:

    def __init__(self):
        self.map = []


    def put(self, key: int, value: int) -> None:
        # k= key , v = value
        for i ,(k , v) in enumerate(self.map):
            if k == key:
                self.map[i] = (key,value)
                return 
        self.map.append((key , value))

    def get(self, key: int) -> int:
        for k,v in self.map:
            if k == key:
                return v
        return -1


    def remove(self, key: int) -> None:
        for i , (k , v) in enumerate(self.map):
            if k == key:
                del self.map[i]
                return

• put(key, value): inserts a key-value pair into the hash map. If the key already exists in the hash map, the corresponding value is updated to the new value.

• get(key): returns the value associated with the given key in the hash map, or -1 if the key does not exist in the hash map.

• remove(key): removes the key-value pair associated with the given key from the hash map, if it exists.

• Here's how the implementation works:

  • The __init__ method initializes an empty list to serve as the underlying data structure for the hash map.

  • The put method loops through the existing key-value pairs in the hash map, and updates the value associated with the key if the key already exists in the hash map. If the key is not found, a new key-value pair is appended to the end of the list.

  • The get method loops through the key-value pairs in the hash map and returns the value associated with the given key if it is found. If the key is not found, the method returns -1.

  • The remove method loops through the key-value pairs in the hash map and removes the key-value pair associated with the given key if it is found.

  • When looping through a sequence, the position index and corresponding value can be retrieved at the same time using the enumerate() function.

This implementation has a time complexity of O(n) for each operation, where n is the number of key-value pairs in the hash map. This is because the implementation uses a list to store the key-value pairs, and searching for a key or removing a key-value pair requires looping through the list until the desired key is found. This is not the most efficient way to implement a hash map, but it is a simple and straightforward approach.

Sets

Python also includes a data type for sets. A set is an unordered collection with no duplicate elements. Basic uses include membership testing and eliminating duplicate entries. Set objects also support mathematical operations like union, intersection, difference, and symmetric difference.

• Creation

s1 = {10, 20, 30}

print(s1)

s2 = set([20, 30, 40])

print(s2)

s3 = {}

print('expected type set',type(s3))

s4 = set()

print(type(s4))

print(s4)

• Insertion

s = {10, 20}

s.add(30)

print(s)

s.add(30)  # adding duplicate items
print(s)

s.update([40, 50])

print(s)

s.update([60, 70], [80, 90])  # inserting multiple list

print(s)

• Removal

s = {10, 30, 20, 40}

s.discard(30)

print(s)

s.remove(20)

print(s)

s.clear()

print(s)

s.add(50)

del s

• Operation on two set 1

s1 = {2, 4, 6, 8}

s2 = {3, 6, 9}

print('union ', s1 | s2)
print(s1.union(s2))

print('intersecton', s1 & s2)
print(s1.intersection(s2))

print('present in s1, but not present in s2', s1 - s2)
print(s1.difference(s2))

print('symmetric differences, not present in both', s1 ^ s2)

• Operation on two set 2

s1 = {2, 4, 6, 8}
s2 = {4, 8}

print('disjoint sets:', s1.isdisjoint(s2))

print('isSubset:', s1 <= s2)
print(s1.issubset(s2))

print('proper set:', s1 < s2)

print('s1 is superset of s2:', s1 >= s2)
print(s1.issuperset(s2))

print('s1 is proper superset of s2:', s1 > s2)

Question on set

Unique Number of Occurrences

Given an array of integers arr, return true if the number of occurrences of each value in the array is unique or false otherwise.

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

    def uniqueOccurrences(self, arr: List[int]) -> bool:
        counts = {}
        for num in arr:
            if num not in counts:
                counts[num] = 1
            else:
                counts[num] += 1

        unique_counts = set(counts.values())
        return len(counts) == len(unique_counts)

with the help of counts, we can keep track of occurrence and unique_counts make a set that is unique if the length of count and the length of unique_counts is the same that means number that occurs in this array is unique if not then the length of count is more than unique_counts

imp = len function in the dictionary calculate the length of value for ex - len(count) = 3

len(unique_counts) = 3 which is true so the answer would be true