<jupyter_start><jupyter_text>MAP ADT**Overall Structures**$$\text{MutableMapping (collections module)}\\\overbrace{\text{MapBase}}^{\Uparrow}\\\overbrace{\text{UnsortedListMap}\quad \text{HashMapBase} \quad\text{SortedListMap} \quad\text{TreeMap}}^{\Uparrow}\\\overbrace{\text{ChainHashMap}\quad\text{ProbeHashMap}}^{\Uparrow}$$<jupyter_code>from collections import MutableMapping
class MapBase(MutableMapping):
    class _Item:
        __slots__ = '_key', '_value'
        def __init__(self, key, value):
            self._key = key
            self._value = value
        def __eq__(self, other):
            return self._key == other._key
        def __ne__(self, other):
            return self._key != other._key
        def __lt__(self, other):
            return self._key < other._key<jupyter_output><empty_output><jupyter_text>UnsortedListMapWorst-cases scenarios|operation|complexity||:-|:-||`find`|$\mathcal{O}(n)$||`insert`|$\mathcal{O}(n)$||`update`|$\mathcal{O}(n)$||`delete`|$\mathcal{O}(n)$|<jupyter_code>class UnsortedListMap(MapBase):
    # five basic behaviors that we need to define
    def __init__(self):
        self._list = [] # use built-in list as a container
    def __getitem__(self, key):
        for item in self._list:
            if key == item._key:
                return item._value
        raise KeyError('Key Error:{}'.format(repr(key)))
        
    def __setitem__(self, key, value):
#         print("===")
#         print('About to set Key: {} Value: {}'.format(key, value))
        for item in self._list:
#             print('Search Key {}: Value: {}'.format(item._key, item._value))
            if key == item._key:
                item._value = value
                return
#         print("This is a new key-value. We append it to list.")
        self._list.append(self._Item(key,value))
        
    def __delitem__(self, key):
        for index in range(len(self._list)):
            if key == self._list[index]._key:
                temp = self._list.pop(index)
                return temp
        raise KeyError('Key Error:{}'.format(repr(key)))
    
    def __len__(self):
        return len(self._list)
    
    def __iter__(self):
        for item in self._list:
            yield item._key
if __name__ == '__main__':
    # working exmaple
    Movies = UnsortedListMap()
    Cherbobly = UnsortedListMap()
    UDI = UnsortedListMap()
    Movies['chernobly'] = Cherbobly
    Movies['udi'] = UDI
    Cherbobly['Episods'] = 5
    Cherbobly['Producer'] = 'HBO'
    UDI['Episods'] = 10
    UDI['Producer'] = 'JaH'
    for movie_key in Movies:
        print(Movies[movie_key]['Producer'])<jupyter_output>HBO
JaH<jupyter_text>Hash Table  Hash-then-compressionstep 1. Hash function: `hash([immutable object])`step 2. Compression function: $[a\times integer + b \text{ mod }p] \text{ mod } N$, where $N$ is the size of a key-holding-list, $p$ is a prime number that is greater than $N$, and $a \in (0, N-1], b \in [0, N-1]$. This scheme is called MAD compression.The reason using the particular choice of a compression function is to avoid 'cyclic' pattern.  Collision-handling Scheme1. separate chain: the `index list` is implemented as a built-in lust while each `bucket` is implemented as `UnsortedListMap`.    * Suppose we have a key-holding-list of size $N$, and we want to index $n$ items. Then the expected length of a `UnsortedListMap` is $[\frac{n}{N}]$, which is as a result of a really good hash function. Define $\lambda= [\frac{n}{N}]$. Then as long as $\lambda$ is $\mathcal{O}(1)$. Then the complexity for `find`, `insert`, `delete`, `update` all take $\mathcal{O}(1)$ time.2. linear probing: no additional data structure required.    * If we try to insert an item (key, value) into a list `L[j]` that is already occupied, where `j = hash(key)`, then we next try `L[(j+1) mod N]`. If `L[(j+1) mod N]` is also occupied, then we try `L[( j + 2) mod N ]`, and so on, until we find an empty bucket that can accept the new item. Once this bucket is located, we simply insert the item there.    * Easy to form clusters, which is bad.    * Deletion should be taken care of as you can not simply remove it. You need some place holder.    3. Double hashing: use secondary function to generate index if collision happens.|operation|complexity|||:-|:-|:-|||Expected|Worst Case||`find`|$\mathcal{O}(1)$|$\mathcal{O}(n)$||`insert`|$\mathcal{O}(1)$|$\mathcal{O}(n)$||`update`|$\mathcal{O}(1)$|$\mathcal{O}(n)$||`delete`|$\mathcal{O}(1)$|$\mathcal{O}(n)$|<jupyter_code>import random as rnd
class HashMapBase(MapBase):
    """
    Abstract Hash Base Class using MAD compression.
    """
    def __init__(self, capacity, prime=109345121):
        self._list = [None] * capacity
        self._size = 0
        self._prime = prime
        self._a = 1 + rnd.randrange(prime-1)
        self._b = rnd.randrange(prime-1)
    
    def __len__(self):
        return self._size
    
    def _hash_compression(self, key):
        return ((self._a * hash(key) + self._b) % self._prime ) % len(self._list)
    
    def __getitem__(self, key):
        idx = self._hash_compression(key)
        return self._getitem(idx, key) # depends on concrete implementation
    
    def __setitem__(self, key, value):
        idx = self._hash_compression(key)
        self._setitem(idx, key, value)
        if self._size > len(self._list) // 2: # keep load factor <= 0.5
            self._resize(2 * len(self._table) - 1)
    
    def __delitem__(self, key):
        idx = self._hash_compression(key)
        self._size -= 1
        self._delitem(idx, key) # depends on concrete implementation
    
    def _resize(self, capacity):
        old = self.items() # return key-valuer pairs; items method inheret from MutableMapping
        self_list = capacity * [None]
        self._size = 0
        for (key, value) in old:
            self[key] = value
class ChainHashMap(HashMapBase):
    '''
    Concrete implementation of the HashMapBase using separate-chain collision scheme.
    '''
    def _getitem(self, idx, key):
        bucket = self._list[idx] # slot should be an UnsortedListMap; this operation is O(1)
        if bucket is None:
            raise KeyError('Key Error' +  repr(key))
        return bucket[key] # this operation is O(1) while worst case is O(n)
    
    def _setitem(self, idx, key, value):
        print("Bucket index: {}".format(idx))
        if self._list[idx] is None:
            self._list[idx] = UnsortedListMap()
        bucket_size = len(self._list[idx])
        self._list[idx][key] = value # set item; this operation is O(1) while worst case is O(n)
        if len(self._list[idx]) > bucket_size:
            self._size += 1
    
    def _delitem(self, idx, key):
        bucket = self._list[idx] # slot should be an UnsortedListMap; this operation is O(1)
        if bucket is None:
            raise KeyError('Key Error' +  repr(key))
        else:
            del bucket[key]
    def __iter__(self):
        for bucket in self._list:
            if bucket is not None:
                for key in bucket:
                    yield key

if __name__ == "__main__":
    IntFloat = ChainHashMap(20)
    IntFloat[5.0] = 'float'
    IntFloat[5] = 'int'
    IntFloat[6] = 'int'
    print(len(IntFloat)) # since key 5 == key 5.0, then value float is overwritten by int.
    print(IntFloat[5.0])
    print(IntFloat[5])
    del IntFloat[5]
    print(len(IntFloat))
class ProbeHashMap(HashMapBase):
    _AVLOBJ = object() # use as place holder for slot where the item is removed
    
    def _is_availabe(self, idx):
        condition1 = self._list[idx] is None
        condition2 = self._list[idx] is self._AVLOBJ
        return condition1 or condition2
    
    def _find_slot(self, idx, key):
        first_available_position = None
        print("checking Key:[{}] at Position:[{}]".format(key, idx))
        while True:
            if self._is_availabe(idx):
                print("Position:[{}] is avaialable.".format(idx))
                if first_available_position is None:
                    first_available_position = idx
                    print("First avaiable position is [{}]".format(idx))
                print(self._list[idx])
                if self._list[idx] is None:
                    # key is new thus not found at the idx position
                    print("Key: [{}] is new.".format(key))
                    return (False, first_available_position) 
            elif key == self._list[idx]._key:
                print("Key: [{}] has been found at Position [{}]".format(key, idx))
                return (True, idx) # the key is already exist in the position idx
            idx = (idx+1) % len(self._list) # look for the next position
            print("keep searching")
            
    def _getitem(self, idx, key):
        found, position = self._find_slot(idx, key)
        if not found:
            raise KeyError('Key Error: ' + repr(key))
        return self._list[position]._value
    
    def _setitem(self,idx, key, value):
        found, position = self._find_slot(idx, key)
        if not found:
            self._list[position] = self._Item(key, value)
            self._size += 1
        else:
            self._list[position]._value = value
        print("Position: [{}] is inserted Key: [{}] Value: [{}]".format(position, key, value))
    
    def _delitem(self, idx, key):
        print("Try to delete Key: [{}]".format(key))
        found, position = self._find_slot(idx, key)
        if not found:
            raise KeyError('Key Error: ' + repr(key))
        else:
            print("Position at [{}] is set to placeholder".format(position))
            self._list[position] = self._AVLOBJ
            self._size -= 1
        
    def __iter__(self):
        for idx in range(len(self._list)):
            if not self._is_availabe(idx):
                yield self._list[idx]._key
test = ProbeHashMap(capacity=10)
test[5] = 'this is 5'
print("===")
del test[5]
print("===")
test[5] = 'this is 5 again'<jupyter_output>checking Key:[5] at Position:[6]
Position:[6] is avaialable.
First avaiable position is [6]
None
Key: [5] is new.
Position: [6] is inserted Key: [5] Value: [this is 5]
===
Try to delete Key: [5]
checking Key:[5] at Position:[6]
Key: [5] has been found at Position [6]
Position at [6] is set to placeholder
===
checking Key:[5] at Position:[6]
Position:[6] is avaialable.
First avaiable position is [6]
<object object at 0x10332cde0>
keep searching
Position:[7] is avaialable.
None
Key: [5] is new.
Position: [6] is inserted Key: [5] Value: [this is 5 again]<jupyter_text>LeetCode TwoSumGiven an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element twice.Example:```Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].```<jupyter_code>class Solution:
    def twosum(self, nums, target):
        mydict = {} # use python built-in hash table
        for idx in range(len(nums)):
            leftover = target - nums[idx]
            if leftover in mydict.keys():
                return [mydict[leftover], idx]
            else:
                mydict[nums[idx]] = idx
if __name__ == "__main__":
    nums = [2, 7, 11, 15]
    mine = Solution()
    print(mine.twosum(nums, target=9))
    print(mine.twosum(nums, target=14))<jupyter_output>[0, 1]
None<jupyter_text>Longest sub-String without  repeatingGiven a string, find the length of the longest substring without repeating characters.```Example 1:Input: "abcabcbb"Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2:Input: "bbbbb"Output: 1Explanation: The answer is "b", with the length of 1.Example 3:Input: "pwwkew"Output: 3Explanation: The answer is "wke", with the length of 3.              Note that the answer must be a substring, "pwke" is a subsequence and not a substring.```<jupyter_code>class Solution:
    def lengthOfLongestSubstring(self, s):
        used = {}
        max_length = start = 0
        for i, c in enumerate(s):
            if c in used and start <= used[c]:
                start = used[c] + 1 # skip the duplicate string c betwwen [start, c]
            else:
                max_length = max(max_length, i - start + 1)
            used[c] = i
        return max_length
            
if __name__ == "__main__":
    mine = Solution()
    print(mine.lengthOfLongestSubstring("pwwkew"))
    print(mine.lengthOfLongestSubstring("abcabcbb"))
    print(mine.lengthOfLongestSubstring("bbbb"))
    print(mine.lengthOfLongestSubstring(""))
    print(mine.lengthOfLongestSubstring(' '))
    print(mine.lengthOfLongestSubstring('dvdf'))
    
mydict = {}
' ' in mydict.keys()
longest_new =''
mydict = {}
for char in ' ':
    if char not in mydict.keys():
        mydict[char] = 0
        longest_new+=char
len(longest_new)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12898236931642437, 'fraction_numerical': 0.01090318589545314, 'mean_word_length': 2.699370709382151, 'pattern_counts': {'":': 3, '<': 22, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '291915', 'license': 'MIT', 'n_tokens_mistral': 4148, 'n_tokens_neox': 3998, 'n_words': 1228, 'path': 'Python_DataStructures/.ipynb_checkpoints/Maps, Hash Tables, and Skip Lists-checkpoint.ipynb', 'repo_name': 'Rothdyt/codes-for-courses', 'size': '12932'}