# Hashmap and set in Python

## Intro

**Hashmap** is indexed data structures. A hash map makes use of a hash function to compute an index with a key into an array of buckets or slots. Its value is mapped to the bucket with the corresponding index. The key is unique and immutable. Hash function is the core of implementing a hash map. It takes in the key and translates it to the index of a bucket in the bucket list. Ideal hashing should produce a different index for each key. However, collisions can occur. When hashing gives an existing index, we can simply use a bucket for multiple values by appending a list or by rehashing.

A **Set** in Python is an unordered collection data type that is iterable, mutable and has no duplicate elements. Set are represented by {} (values enclosed in curly braces). The major advantage of using a set, as opposed to a list, is that it has a highly optimized method for checking whether a specific element is contained in the set. This is based on a data structure known as a hash table. Since sets are unordered, we cannot access items using indexes as we do in lists.

## [Leetcode 49] Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

1 | Input: strs = ["eat","tea","tan","ate","nat","bat"] |

Example 2:

1 | Input: strs = [""] |

Example 3:

1 | Input: strs = ["a"] |

Constraints:

- 1 <= strs.length <= 10^4
- 0 <= strs[i].length <= 100
- strs[i] consists of lowercase English letters.

Solution:

1 | class Solution: |

## [Leetcode 128] Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

1 | Input: nums = [100,4,200,1,3,2] |

Example 2:

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

Constraints:

- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9

Solution:

1 | class Solution: |

## [Leetcode 138] Copy List with Random Pointer

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random –> Y, then for the corresponding two nodes x and y in the copied list, x.random –> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

- val: an integer representing Node.val
- random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

1 | Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] |

Example 2:

1 | Input: head = [[1,1],[2,1]] |

Example 3:

1 | Input: head = [[3,null],[3,0],[3,null]] |

Constraints:

- 0 <= n <= 1000
- -10^4 <= Node.val <= 10^4
- Node.random is null or is pointing to some node in the linked list.

Solution:

1 | """ |

## [Leetcode 290] Word Pattern

Given a pattern and a string s, find if s follows the same pattern. Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

Example 1:

1 | Input: pattern = "abba", s = "dog cat cat dog" |

Example 2:

1 | Input: pattern = "abba", s = "dog cat cat fish" |

Example 3:

1 | Input: pattern = "aaaa", s = "dog cat cat dog" |

Constraints:

- 1 <= pattern.length <= 300
- pattern contains only lower-case English letters.
- 1 <= s.length <= 3000
- s contains only lowercase English letters and spaces ‘ ‘.
- s does not contain any leading or trailing spaces.
- All the words in s are separated by a single space.

Solution:

1 | class Solution: |

## [Leetcode 380] Insert Delete GetRandom O(1)

Implement the RandomizedSet class:

- RandomizedSet() Initializes the RandomizedSet object.
- bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
- bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
- int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Example 1:

1 | Input: |

Constraints:

- -231 <= val <= 231 - 1
- At most 2 * 105 calls will be made to insert, remove, and getRandom.
- There will be at least one element in the data structure when getRandom is called.

1 | import random |

## [Leetcode 1657] Determine if Two Strings Are Close

Two strings are considered close if you can attain one from the other using the following operations:

- Operation 1: Swap any two existing characters.

For example, abcde -> aecdb - Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.

For example, aacabb -> bbcbaa (all a’s turn into b’s, and all b’s turn into a’s)

You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

Example 1:

1 | Input: word1 = "abc", word2 = "bca" |

Example 2:

1 | Input: word1 = "a", word2 = "aa" |

Example 3:

1 | Input: word1 = "cabbba", word2 = "abbccc" |

Constraints:

- 1 <= word1.length, word2.length <= 105
- word1 and word2 contain only lowercase English letters.

Solution:

1 | class Solution: |