chapter 12: Map

12.1 hashtable

HashMap Data Type HashMap() Create a new, empty map. It returns an empty map collection. put(key, val) Add a new key-value pair to the map. If the key is already in the map then replace

the old value with the new value.

get(key) Given a key, return the value stored in the map or None otherwise. del_(key) or del map[key] Delete the key-value pair from the map using a statement of the form del map[key]. len() Return the number of key-value pairs stored in the map. in Return True for a statement of the form key in map, if the given key is in the map, False otherwise.

_empty = object()
_deleted = object()

def __init__(self, size=11):
    self.size = size
    self._len = 0
    self._keys = [self._empty] * size  # keys
    self._values = [self._empty] * size  # values

def put(self, key, value):
    initial_hash = hash_ = self.hash(key)

    while True:
        if self._keys[hash_] is self._empty or self._keys[hash_] is self._deleted:
            # can assign to hash_ index
            self._keys[hash_] = key
            self._values[hash_] = value
            self._len += 1
            return
        elif self._keys[hash_] == key:
            # key already exists here, assign over
            self._keys[hash_] = key
            self._values[hash_] = value
            return

        hash_ = self._rehash(hash_)

        if initial_hash == hash_:
            # table is full
            raise ValueError("Table is full")

def get(self, key):
    initial_hash = hash_ = self.hash(key)
    while True:
        if self._keys[hash_] is self._empty:
            # That key was never assigned
            return None
        elif self._keys[hash_] == key:
            # key found
            return self._values[hash_]

        hash_ = self._rehash(hash_)
        if initial_hash == hash_:
            # table is full and wrapped around
            return None

def del_(self, key):
    initial_hash = hash_ = self.hash(key)
    while True:
        if self._keys[hash_] is self._empty:
            # That key was never assigned
            return None
        elif self._keys[hash_] == key:
            # key found, assign with deleted sentinel
            self._keys[hash_] = self._deleted
            self._values[hash_] = self._deleted
            self._len -= 1
            return

        hash_ = self._rehash(hash_)
        if initial_hash == hash_:
            # table is full and wrapped around
            return None

def hash(self, key):
    return key % self.size

def _rehash(self, old_hash):
    """
    linear probing
    """
    return (old_hash + 1) % self.size

def __getitem__(self, key):
    return self.get(key)

def __delitem__(self, key):
    return self.del_(key)

def __setitem__(self, key, value):
    self.put(key, value)

def __len__(self):
    return self._len


class ResizableHashTable(HashTable):
    MIN_SIZE = 8

    def __init__(self):
        super().__init__(self.MIN_SIZE)

    def put(self, key, value):
        rv = super().put(key, value)
        # increase size of dict * 2 if filled >= 2/3 size (like python dict)
        if len(self) >= (self.size * 2) / 3:
            self.__resize()

    def __resize(self):
        keys, values = self._keys, self._values
        self.size *= 2  # this will be the new size
        self._len = 0
        self._keys = [self._empty] * self.size
        self._values = [self._empty] * self.size
        for key, value in zip(keys, values):
            if key is not self._empty and key is not self._deleted:
                self.put(key, value)

12.2 is anagram

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1: Input: s = "anagram", t = "nagaram" Output: true

Example 2: Input: s = "rat", t = "car" Output: false

Note: You may assume the string contains only lowercase alphabets.

Reference: https://leetcode.com/problems/valid-anagram/description/

def is_anagram(s, t):
    """
    :type s: str
    :type t: str
    :rtype: bool
    """
    maps = {}
    mapt = {}
    for i in s:
        maps[i] = maps.get(i, 0) + 1
    for i in t:
        mapt[i] = mapt.get(i, 0) + 1
    return maps == mapt

12.3 is isomorphic

Given two strings s and t, determine if they are isomorphic. Two strings are isomorphic if the characters in s can be replaced to get t. All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Example 1: Input: s = "egg", t = "add" Output: true

Example 2: Input: s = "foo", t = "bar" Output: false

Example 3: Input: s = "paper", t = "title" Output: true Reference: https://leetcode.com/problems/isomorphic-strings/description/

def is_isomorphic(s, t):
    """
    :type s: str
    :type t: str
    :rtype: bool
    """
    if len(s) != len(t):
        return False
    dict = {}
    set_value = set()
    for i in range(len(s)):
        if s[i] not in dict:
            if t[i] in set_value:
                return False
            dict[s[i]] = t[i]
            set_value.add(t[i])
        else:
            if dict[s[i]] != t[i]:
                return False
    return True

12.4 logest common subsequence

Given string a and b, with b containing all distinct characters, find the longest common sub sequence's length.

Expected complexity O(n logn).

def max_common_sub_string(s1, s2):
    # Assuming s2 has all unique chars
    s2dic = {s2[i]: i for i in range(len(s2))}
    maxr = 0
    subs = ''
    i = 0
    while i < len(s1):
        if s1[i] in s2dic:
            j = s2dic[s1[i]]
            k = i
            while j < len(s2) and k < len(s1) and s1[k] == s2[j]:
                k += 1
                j += 1
            if k - i > maxr:
                maxr = k-i
                subs = s1[i:k]
            i = k
        else:
            i += 1
    return subs

12.5 randomized set

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present. remove(val): Removes an item val from the set if present. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

import random


class RandomizedSet:
    def __init__(self):
        self.nums = []
        self.idxs = {}

    def insert(self, val):
        if val not in self.idxs:
            self.nums.append(val)
            self.idxs[val] = len(self.nums)-1
            return True
        return False

    def remove(self, val):
        if val in self.idxs:
            idx, last = self.idxs[val], self.nums[-1]
            self.nums[idx], self.idxs[last] = last, idx
            self.nums.pop()
            self.idxs.pop(val, 0)
            return True
        return False

    def get_random(self):
        idx = random.randint(0, len(self.nums)-1)
        return self.nums[idx]


if __name__ == "__main__":
    rs = RandomizedSet()
    print("insert 1: ", rs.insert(1))
    print("insert 2: ", rs.insert(2))
    print("insert 3: ", rs.insert(3))
    print("insert 4: ", rs.insert(4))
    print("remove 3: ", rs.remove(3))
    print("remove 3: ", rs.remove(3))
    print("remove 1: ", rs.remove(1))
    print("random: ", rs.get_random())
    print("random: ", rs.get_random())
    print("random: ", rs.get_random())
    print("random: ", rs.get_random())

12.6 separate chaining hashtable

import unittest


class Node(object):
    def __init__(self, key=None, value=None, next=None):
        self.key = key
        self.value = value
        self.next = next


class SeparateChainingHashTable(object):
    """
    HashTable Data Type:
    By having each bucket contain a linked list of elements that are hashed to that bucket.

    Usage:
    >>> table = SeparateChainingHashTable() # Create a new, empty map.
    >>> table.put('hello', 'world') # Add a new key-value pair.
    >>> len(table) # Return the number of key-value pairs stored in the map.
    1
    >>> table.get('hello') # Get value by key.
    'world'
    >>> del table['hello'] # Equivalent to `table.del_('hello')`, deleting key-value pair.
    >>> table.get('hello') is None # Return `None` if a key doesn't exist.
    True
    """
    _empty = None

    def __init__(self, size=11):
        self.size = size
        self._len = 0
        self._table = [self._empty] * size

    def put(self, key, value):
        hash_ = self.hash(key)
        node_ = self._table[hash_]
        if node_ is self._empty:
            self._table[hash_] = Node(key, value)
        else:
            while node_.next is not None:
                if node_.key == key:
                    node_.value = value
                    return
                node_ = node_.next
            node_.next = Node(key, value)
        self._len += 1

    def get(self, key):
        hash_ = self.hash(key)
        node_ = self._table[hash_]
        while node_ is not self._empty:
            if node_.key == key:
                return node_.value
            node_ = node_.next
        return None

    def del_(self, key):
        hash_ = self.hash(key)
        node_ = self._table[hash_]
        pre_node = None
        while node_ is not None:
            if node_.key == key:
                if pre_node is None:
                    self._table[hash_] = node_.next
                else:
                    pre_node.next = node_.next
                self._len -= 1
            pre_node = node_
            node_ = node_.next

    def hash(self, key):
        return hash(key) % self.size

    def __len__(self):
        return self._len

    def __getitem__(self, key):
        return self.get(key)

    def __delitem__(self, key):
        return self.del_(key)

    def __setitem__(self, key, value):
        self.put(key, value)

12.7 valid sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

def is_valid_sudoku(self, board):
    seen = []
    for i, row in enumerate(board):
        for j, c in enumerate(row):
            if c != '.':
                seen += [(c,j),(i,c),(i/3,j/3,c)]
    return len(seen) == len(set(seen))

12.8 word pattern

Given a pattern and a string str, find if str 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 str.

Example 1: Input: pattern = "abba", str = "dog cat cat dog" Output: true

Example 2: Input:pattern = "abba", str = "dog cat cat fish" Output: false

Example 3: Input: pattern = "aaaa", str = "dog cat cat dog" Output: false

Example 4: Input: pattern = "abba", str = "dog dog dog dog" Output: false Notes: You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space. Reference: https://leetcode.com/problems/word-pattern/description/

def word_pattern(pattern, str):
    dict = {}
    set_value = set()
    list_str = str.split()
    if len(list_str) != len(pattern):
        return False
    for i in range(len(pattern)):
        if pattern[i] not in dict:
            if list_str[i] in set_value:
                return False
            dict[pattern[i]] = list_str[i]
            set_value.add(list_str[i])
        else:
            if dict[pattern[i]] != list_str[i]:
                return False
    return True