Ch15_FB.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Remove Invalid Parentheses\n",
    "Hard\n",
    "\n",
    "Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.\n",
    "\n",
    "Note: The input string may contain letters other than the parentheses ( and ).\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: \"()())()\"\n",
    "Output: [\"()()()\", \"(())()\"]\n",
    "Example 2:\n",
    "\n",
    "Input: \"(a)())()\"\n",
    "Output: [\"(a)()()\", \"(a())()\"]\n",
    "Example 3:\n",
    "\n",
    "Input: \")(\"\n",
    "Output: [\"\"]\n",
    "\n",
    "Accepted\n",
    "122.7K\n",
    "Submissions\n",
    "313.1K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Integer to English Words\n",
    "Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.\n",
    "\n",
    "```\n",
    "Example 1:\n",
    "\n",
    "Input: 123\n",
    "Output: \"One Hundred Twenty Three\"\n",
    "Example 2:\n",
    "\n",
    "Input: 12345\n",
    "Output: \"Twelve Thousand Three Hundred Forty Five\"\n",
    "Example 3:\n",
    "\n",
    "Input: 1234567\n",
    "Output: \"One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven\"\n",
    "Example 4:\n",
    "\n",
    "Input: 1234567891\n",
    "Output: \"One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One\"\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def numberToWords(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: strx\n",
    "        \"\"\"\n",
    "\n",
    "        n2w = {1e9: \"Billion\", 1e6: \"Million\", 1e3: \"Thousand\", 1e2: \"Hundred\",\n",
    "               90:  \"Ninety\", 80:  \"Eighty\", 70:  \"Seventy\",\n",
    "               60:  \"Sixty\", 50:  \"Fifty\", 40:  \"Forty\",\n",
    "               30:  \"Thirty\", 20:  \"Twenty\", 19: \"Nineteen\",\n",
    "               18:  \"Eighteen\", 17: \"Seventeen\", 16: \"Sixteen\",\n",
    "               15:  \"Fifteen\", 14: \"Fourteen\", 13: \"Thirteen\",\n",
    "               12:  \"Twelve\", 11:  \"Eleven\", 10:  \"Ten\",\n",
    "               9:   \"Nine\", 8:   \"Eight\", 7:   \"Seven\",\n",
    "               6:   \"Six\", 5:   \"Five\", 4: \"Four\", 3: \"Three\",\n",
    "               2: \"Two\", 1: \"One\", 0: \"Zero\"}\n",
    "\n",
    "        keys = [1000000000, 1000000, 1000, 100, 90, 80, 70,\n",
    "               60, 50, 40, 30, 20, 19, 18, 17, 16, 15, 14, 13, 12,\n",
    "               11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\n",
    "\n",
    "        def dp(n):\n",
    "            if n <= 20: return n2w[n]\n",
    "            for div in keys:\n",
    "                d, r = divmod(n, div)\n",
    "                if not d: continue\n",
    "                s1 = dp(d) + \" \" if div >= 100 else \"\"\n",
    "                s2 = \" \" + dp(r) if r else \"\"\n",
    "                return s1 + n2w[div] + s2\n",
    "\n",
    "        return dp(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def removeInvalidParentheses(self, s: str):\n",
    "        if len(s) == 0:\n",
    "            return [\"\"]\n",
    "        ans = []\n",
    "        \n",
    "        def dfs(tmp, last_i, last_j, par):\n",
    "            count = 0 \n",
    "            for i in range(last_i, len(tmp)):\n",
    "                if tmp[i] == par[0]: count += 1\n",
    "                if tmp[i] == par[1]: count -= 1\n",
    "                if count >= 0:\n",
    "                    continue\n",
    "                for j in range(last_j, i+1):\n",
    "                    if(tmp[j] == par[1]) and (j == last_j or tmp[j-1] != par[1]):\n",
    "                        # count < 0, means ()) like str was constructed, \n",
    "                        #need to remove one, then which one?\n",
    "                        # any one from last_j is fine\n",
    "                        dfs(tmp[:j] + tmp[j+1:], i, j, par)\n",
    "                return\n",
    "            \n",
    "            reverse = tmp[::-1]\n",
    "            \n",
    "            if par[0] == '(':\n",
    "                dfs(reverse, 0, 0, [')', '('])\n",
    "            else:\n",
    "                ans.append(reverse)\n",
    "        \n",
    "        dfs(s, 0, 0, ['(', ')'])\n",
    "        \n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Add Binary\n",
    "Easy\n",
    "Given two binary strings, return their sum (also a binary string).\n",
    "\n",
    "The input strings are both non-empty and contains only characters 1 or 0.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: a = \"11\", b = \"1\"\n",
    "Output: \"100\"\n",
    "Example 2:\n",
    "\n",
    "Input: a = \"1010\", b = \"1011\"\n",
    "Output: \"10101\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def addBinary(self, a, b):\n",
    "        return bin(int(a,2) + int(b,2))[2:]\n",
    "    \n",
    "    def addBinary2(self, a, b):\n",
    "        return bin(eval('0b' + a) + eval('0b' + b))[2:]\n",
    "    \n",
    "    def addBinary3(self, a, b):\n",
    "        res = ''\n",
    "        index = 0 \n",
    "        carry = '0'\n",
    "        \n",
    "        while index < max(len(a), len(b)) or carry == '1':\n",
    "            num_a = a[-1-index] if index < len(a) else '0'\n",
    "            num_b = b[-1-index] if index < len(b) else '0'\n",
    "            val = int(num_a) + int(num_b) + int(carry)\n",
    "            res = str(val%2) + res\n",
    "            carry = '1' if val > 1 else '0'\n",
    "            index += 1 \n",
    "        \n",
    "        return res \n",
    "            "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### First Bad Version\n",
    "You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.\n",
    "\n",
    "Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.\n",
    "\n",
    "You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.\n",
    "\n",
    "Example:\n",
    "\n",
    "Given n = 5, and version = 4 is the first bad version.\n",
    "\n",
    "call isBadVersion(3) -> false\n",
    "call isBadVersion(5) -> true\n",
    "call isBadVersion(4) -> true\n",
    "\n",
    "Then 4 is the first bad version. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The isBadVersion API is already defined for you.\n",
    "# @param version, an integer\n",
    "# @return a bool\n",
    "# def isBadVersion(version):\n",
    "\n",
    "class Solution(object):\n",
    "    def firstBadVersion(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        r = n-1\n",
    "        l = 0\n",
    "        while(l<=r):\n",
    "            mid = l + (r-l) // 2\n",
    "            if isBadVersion(mid)==False:\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid-1\n",
    "        return l\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Valid Palindrome II\n",
    "\n",
    "Share\n",
    "Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.\n",
    "```\n",
    "Example 1:\n",
    "Input: \"aba\"\n",
    "Output: True\n",
    "Example 2:\n",
    "Input: \"abca\"\n",
    "Output: True\n",
    "Explanation: You could delete the character 'c'.\n",
    "Note:\n",
    "The string will only contain lowercase characters a-z. The maximum length of the string is 50000.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def validPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # Time: O(n)\n",
    "        # Space: O(n)\n",
    "        left, right = 0, len(s) - 1\n",
    "        while left < right:\n",
    "            if s[left] != s[right]:\n",
    "                one, two = s[left:right], s[left + 1:right + 1]\n",
    "                return one == one[::-1] or two == two[::-1]\n",
    "            left, right = left + 1, right - 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "    def isPalindrome(self, s, start, end, delCount):\n",
    "        if delCount > 1:\n",
    "            return False\n",
    "        while start < end:\n",
    "            if s[start] != s[end]:\n",
    "                break\n",
    "            start += 1\n",
    "            end -= 1\n",
    "        if (start == end) or (start == end+1):\n",
    "            return True\n",
    "        return any([self.isPalindrome(s, start+1, end, delCount+1), self.isPalindrome(s, start, end-1, delCount+1)])\n",
    "\n",
    "    def validPalindrome(self, s):\n",
    "        return self.isPalindrome(s, 0, len(s)-1, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Two Sum II - Input array is sorted\n",
    "Easy\n",
    "\n",
    "874\n",
    "\n",
    "369\n",
    "\n",
    "Favorite\n",
    "\n",
    "Share\n",
    "Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.\n",
    "\n",
    "The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.\n",
    "\n",
    "Note:\n",
    "\n",
    "Your returned answers (both index1 and index2) are not zero-based.\n",
    "You may assume that each input would have exactly one solution and you may not use the same element twice.\n",
    "Example:\n",
    "\n",
    "Input: numbers = [2,7,11,15], target = 9\n",
    "Output: [1,2]\n",
    "Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def twoSum(self, numbers, target):\n",
    "        \"\"\"\n",
    "        :type numbers: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        j = len(numbers)-1\n",
    "        while i<j:\n",
    "            if numbers[i] + numbers[j] == target:\n",
    "                return [i+1,j+1]\n",
    "            elif numbers[i] + numbers[j] > target:\n",
    "                j-= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### findAnagrams"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "def findAnagrams(self, s, p):\n",
    "    \"\"\"\n",
    "    :type s: str\n",
    "    :type p: str\n",
    "    :rtype: List[int]\n",
    "    \"\"\"\n",
    "    res = []\n",
    "    pCounter = Counter(p)\n",
    "    sCounter = Counter(s[:len(p)-1])\n",
    "    for i in range(len(p)-1,len(s)):\n",
    "        sCounter[s[i]] += 1   # include a new char in the window\n",
    "        if sCounter == pCounter:    # This step is O(1), since there are at most 26 English letters \n",
    "            res.append(i-len(p)+1)   # append the starting index\n",
    "        sCounter[s[i-len(p)+1]] -= 1   # decrease the count of oldest char in the window\n",
    "        if sCounter[s[i-len(p)+1]] == 0:\n",
    "            del sCounter[s[i-len(p)+1]]   # remove the count if it is 0\n",
    "    return res\n",
    "\n",
    "## not using counter, much faster than 1\n",
    "def findAnagrams(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        n, m = len(s), len(p)\n",
    "        if n < m: return res\n",
    "        phash, shash = [0]*123, [0]*123\n",
    "        for x in p:\n",
    "            phash[ord(x)] += 1\n",
    "        for x in s[:m-1]:\n",
    "            shash[ord(x)] += 1\n",
    "        for i in range(m-1, n):\n",
    "            shash[ord(s[i])] += 1\n",
    "            if i-m >= 0:\n",
    "                shash[ord(s[i-m])] -= 1\n",
    "            if shash == phash:\n",
    "                res.append(i - m + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Detect cyclic linklist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param head: The first node of the linked list.\n",
    "    @return: True if it has a cycle, or false\n",
    "    \"\"\"\n",
    "    def hasCycle(self, head):\n",
    "        # write your code here\n",
    "        if head is None:    \t\t\n",
    "            return False\t\t\n",
    "        p1 = head\t\t\n",
    "        p2 = head\t\t\n",
    "        while True:\n",
    "            if p1.next is not None:\n",
    "                p1=p1.next.next\n",
    "                p2=p2.next\n",
    "                if p1 is None or p2 is None:\n",
    "                    return False\n",
    "                elif p1 == p2:\n",
    "                    return True\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Peak Index in a Mountain Array\n",
    "\n",
    "Let's call an array A a mountain if the following properties hold:\n",
    "\n",
    "A.length >= 3\n",
    "There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]\n",
    "Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].\n",
    "```\n",
    "Example 1:\n",
    "\n",
    "Input: [0,1,0]\n",
    "Output: 1\n",
    "Example 2:\n",
    "\n",
    "Input: [0,2,1,0]\n",
    "Output: 1\n",
    "Note:\n",
    "\n",
    "3 <= A.length <= 10000\n",
    "0 <= A[i] <= 10^6\n",
    "A is a mountain, as defined above.\n",
    "```\n",
    "Notes：需要注意，先检查start 还是先检查end, 这里无所谓，反正只有两个candidate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def peakIndexInMountainArray(self, A: List[int]) -> int:\n",
    "        start, end = 0, len(A) - 1\n",
    "        while start + 1 < end:\n",
    "            mid = start + (end - start) // 2     \n",
    "            if  A[mid] < A[mid+1]:\n",
    "                start = mid\n",
    "            else:\n",
    "                end = mid\n",
    "        \n",
    "        if A[end-1] < A[end] and A[end] > A[end+1]:\n",
    "            return end\n",
    "        return start"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Meeting Rooms II\n",
    "Medium\n",
    "\n",
    "1299\n",
    "\n",
    "23\n",
    "\n",
    "Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: [[0, 30],[5, 10],[15, 20]]\n",
    "Output: 2\n",
    "Example 2:\n",
    "\n",
    "Input: [[7,10],[2,4]]\n",
    "Output: 1\n",
    "NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.\n",
    "\n",
    "Accepted\n",
    "149.5K\n",
    "Submissions\n",
    "349.2K"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def minMeetingRooms(self, intervals):\n",
    "        points = []\n",
    "        for start, end in intervals:\n",
    "            points.append((start, 1))\n",
    "            points.append((end, -1))\n",
    "        points.sort()\n",
    "        on_going_meeting = max_rooms = 0\n",
    "        for _, delta in points:\n",
    "            on_going_meeting += delta\n",
    "            max_rooms = max(max_rooms, on_going_meeting)\n",
    "\n",
    "        return max_rooms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Vertical Sum in a tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def verticalTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return []\n",
    "        array = []\n",
    "        def dfs(node, x, y, array):\n",
    "            if node is None:\n",
    "                return\n",
    "            array.append((x, y, node.val))\n",
    "            dfs(node.left, x - 1, y - 1, array)\n",
    "            dfs(node.right, x + 1, y - 1, array)\n",
    "        dfs(root, 0, 0, array)\n",
    "        def cmp_(A, B):\n",
    "            if A[0] != B[0]:\n",
    "                return A[0] - B[0]\n",
    "            if A[1] != B[1]:\n",
    "                return B[1] - A[1]\n",
    "            return A[2] - B[2]\n",
    "    \n",
    "        array = sorted(array, cmp = cmp_)\n",
    "        # print(array)\n",
    "        ans = [[array[0][2]]]\n",
    "        for i in range(1, len(array)):\n",
    "            if array[i][0] == array[i-1][0]:\n",
    "                ans[-1].append(array[i][2])\n",
    "            else:\n",
    "                ans.append([array[i][2]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Serialize and Deserialize Binary Tree\n",
    "Hard\n",
    "\n",
    "1454\n",
    "\n",
    "67\n",
    "\n",
    "Favorite\n",
    "\n",
    "Share\n",
    "Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.\n",
    "\n",
    "Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.\n",
    "```\n",
    "Example: \n",
    "\n",
    "You may serialize the following tree:\n",
    "\n",
    "    1\n",
    "   / \\\n",
    "  2   3\n",
    "     / \\\n",
    "    4   5\n",
    "\n",
    "as \"[1,2,3,null,null,4,5]\"\n",
    "Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.\n",
    "\n",
    "Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.TreeNode at 0x175ee6f8d68>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class TreeNode(object):\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "from collections import deque\n",
    "class Codec:\n",
    "\n",
    "    @staticmethod\n",
    "    def serialize(root):\n",
    "        \"\"\"\n",
    "        @param root: An object of TreeNode, denote the root of the binary tree.\n",
    "        This method will be invoked first, you should design your own algorithm\n",
    "        to serialize a binary tree which denote by a root node to a string which\n",
    "        can be easily deserialized by your own \"deserialize\" method later.\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return \"[]\"\n",
    "        que = [root]\n",
    "        i = 0\n",
    "        while len(que) > i:\n",
    "            if que[i]:\n",
    "                que.append(que[i].left)\n",
    "                que.append(que[i].right)\n",
    "                que[i] = str(que[i].val)\n",
    "            else:\n",
    "                que[i] = 'null' \n",
    "            \n",
    "            i += 1\n",
    "            \n",
    "        while que[-1] is 'null':\n",
    "            que.pop()\n",
    "            \n",
    "        ser = \",\".join(que)\n",
    "        return \"[\" + ser + \"]\"\n",
    "    \n",
    "    @staticmethod\n",
    "    def serialize_bfs(self, root):\n",
    "        if root == None:\n",
    "            return '[]'\n",
    "        deck = deque()\n",
    "        deck.append(root)\n",
    "        ser = []\n",
    "        while deck:\n",
    "            node = deck.popleft()\n",
    "            if node:\n",
    "                ser.append(str(node.val))\n",
    "                deck.append(node.left)\n",
    "                deck.append(node.right)\n",
    "            else:\n",
    "                ser.append('null')\n",
    "        while ser[-1] == 'null':\n",
    "            ser.pop(-1)\n",
    "            \n",
    "        ser = ','.join(ser)\n",
    "        return '[' + ser + ']'      \n",
    "    @staticmethod\n",
    "    def deserialize(data):\n",
    "        \"\"\"\n",
    "        @param data: A string serialized by your serialize method.\n",
    "        This method will be invoked second, the argument data is what exactly\n",
    "        you serialized at method \"serialize\", that means the data is not given by\n",
    "        system, it's given by your own serialize method. So the format of data is\n",
    "        designed by yourself, and deserialize it here as you serialize it in\n",
    "        \"serialize\" method.\n",
    "        \"\"\"\n",
    "        if data == \"[]\":\n",
    "            return None\n",
    "        data = data[1:-1].split(',') # remove {\n",
    "        root = TreeNode(int(data[0]))\n",
    "        que = [root]\n",
    "        index = 0\n",
    "        is_left = True\n",
    "        for i in range(1, len(data)):\n",
    "            if data[i] != 'null':\n",
    "                node = TreeNode(int(data[i]))\n",
    "                que.append(node)\n",
    "                if is_left: \n",
    "                    que[index].left = node\n",
    "                else:\n",
    "                    que[index].right = node\n",
    "                \n",
    "            if is_left is False:\n",
    "                index += 1 \n",
    "            is_left = not is_left\n",
    "        return root\n",
    "\n",
    "codec = Codec()\n",
    "codec.deserialize('[1,2,3]')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Verifying an Alien Dictionary\n",
    "Easy\n",
    "\n",
    "In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.\n",
    "\n",
    "Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: words = [\"hello\",\"leetcode\"], order = \"hlabcdefgijkmnopqrstuvwxyz\"\n",
    "Output: true\n",
    "Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.\n",
    "Example 2:\n",
    "\n",
    "Input: words = [\"word\",\"world\",\"row\"], order = \"worldabcefghijkmnpqstuvxyz\"\n",
    "Output: false\n",
    "Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.\n",
    "Example 3:\n",
    "\n",
    "Input: words = [\"apple\",\"app\"], order = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "Output: false\n",
    "Explanation: The first three characters \"app\" match, and the second string is shorter (in size.) According to lexicographical rules \"apple\" > \"app\", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).\n",
    " \n",
    "\n",
    "Note:\n",
    "```\n",
    "1 <= words.length <= 100\n",
    "1 <= words[i].length <= 20\n",
    "order.length == 26\n",
    "All characters in words[i] and order are english lowercase letters.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        base_int = ord('a')\n",
    "        new_order = sorted(words, key=lambda word: [order.index(c) for c in word])\n",
    "        return new_order == words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Subarray Sum Equals K\n",
    "Medium\n",
    "Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.\n",
    "\n",
    "Example 1:\n",
    "Input:nums = [1,1,1], k = 2\n",
    "Output: 2\n",
    "Note:\n",
    "The length of the array is in range [1, 20,000].\n",
    "The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def subarraySum(self, A, K):\n",
    "        count = collections.defaultdict()\n",
    "        count[0] = 1 # count sum 0 is 1\n",
    "        ans = su = 0\n",
    "        for x in A:\n",
    "            su += x\n",
    "            ans += count[su-K]\n",
    "            count[su] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Two sum\n",
    "def twoSum(nums, target):\n",
    "    nmap = {}\n",
    "    for i, num in enumerate(nums):\n",
    "        if target - num in nmap:\n",
    "            return sorted([i, nmap[target - num]])\n",
    "        else:\n",
    "            nmap[num] = i\n",
    "    \n",
    "    return [-1, -1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Subarray Product less than K"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def numSubarrayProductLessThanK(self, nums, k):\n",
    "    if not nums:\n",
    "        return 0\n",
    "    j = 0\n",
    "    res = 1\n",
    "    count = 0\n",
    "    for i in range(len(nums)):\n",
    "        res *= nums[i]\n",
    "        if res >= k:\n",
    "            while j <= i and res >= k:\n",
    "                res /= nums[j]\n",
    "                j += 1\n",
    "        count += i - j + 1\n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task Scheduler\n",
    "Medium\n",
    "Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.\n",
    "\n",
    "However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.\n",
    "\n",
    "You need to return the least number of intervals the CPU will take to finish all the given tasks.\n",
    "\n",
    " \n",
    "\n",
    "Example:\n",
    "\n",
    "Input: tasks = [\"A\",\"A\",\"A\",\"B\",\"B\",\"B\"], n = 2\n",
    "Output: 8\n",
    "Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.\n",
    "    \n",
    "Note:\n",
    "Let's say the most frequent tasks occur M times, and there are Mct of them.\n",
    "\n",
    "When N > Mct, let's make our scheduling constraint strictly stronger by choosing N = Mct. So from now on, let's suppose Mct <= N, and the most frequent tasks are denoted #A, #B, #C, ... #K.\n",
    "\n",
    "Then we could schedule say, ABC...K__...ABC...K_...ABC...K_....., where A...K occurs Mct times, _ denotes idle time, and there is N space between A's. This partial schedule would have length L = (M-1) * (N+1) + Mct. Clearly, we need at least L intervals of time in our schedule to fit our given tasks. Let's show this is enough.\n",
    "\n",
    "\n",
    "Start inserting the remaining similar tasks in the following 'writing' order:\n",
    "\n",
    "The first space to the right of the first K\n",
    "The first space to the right of the second K\n",
    "...\n",
    "The first space to the right of the last K\n",
    "The second space to the right of the first K\n",
    "...\n",
    "The second space to the right of the last K\n",
    "The third space to the right of the first K\n",
    "....\n",
    "For example, say we have A B C 1 4 7 10 A B C 2 5 8 11 A B C 3 6 9 12 A B C D.\n",
    "The numbers denote idle time in the order we will insert.\n",
    "If we have EEEFFGGHHJJK left, we would insert:\n",
    "A B C E F G J A B C E F H J A B C E G H K A B C D\n",
    "\n",
    "Say two tasks of the same type collide if they are scheduled within N time of each other. After we have inserted all tasks of frequency M - 1 (which clearly will not collide), other tasks of frequency lower than M - 1 will never have any task written collide with it's left-neighbor (because of the writing order), and the last task written does not collide with the first task written as they are at least 2N - 1 apart.\n",
    "\n",
    "If len(tasks) <= L, this proves that an L-length schedule satisfies.\n",
    "\n",
    "When len(tasks) > L, clearly we need at least len(tasks) intervals of time to schedule all tasks - one interval for each task. Let's insert remaining tasks as before, possibly having one task incomplete. For example, we might have A B C E F G J A B C E F H J A B C E G H K A B C D, with KLLMMNNOO left to insert - and K is incomplete. Our strategy will now be to insert these tasks into our compact schedule.\n",
    "\n",
    "Our incomplete task (K in our example) can be completed by inserting tasks K in the writing order spots that preceded it. For example, if we wrote J 10th, J 11th, and K 12th, then the positions 11 and 10 are suitable to add K without collision (and numerous enough to permit adding them all). Now with our remaining tasks, say LL, we will insert in the 1st, N+1th, (and 2N+1th, 3N+1th, etc. if necessary) positions in schedule order.\n",
    "\n",
    "So we've shown that the answer is max(len(tasks), L).\n",
    "\n",
    "\n",
    "\n",
    "Method2:\n",
    "\n",
    "This is an extremely tricky problem.\n",
    "The main idea is to schedule the most frequent tasks as frequently as possible. Begin with scheduling the most frequent task. Then cool-off for n, and in that cool-off period schedule tasks in order of frequency, or if no tasks are available, then be idle.\n",
    "Exampe: Say we have the following tasks: [A,A,A,B,C,D,E] with n =2\n",
    "Now if we schedule using the idea of scheduling all unique tasks once and then calculating if a cool-off is required or not, then we have: A,B,C,D,E,A,idle,dile,A i.e. 2 idle slots.\n",
    "But if we schedule using most frequent first, then we have:\n",
    "2.1: A,idle,idle,A,idle,idle,A\n",
    "2.2: A,B,C,A,D,E,A i.e. no idle slots. This is the general intuition of this problem.\n",
    "3.The idea in two can be implemented using a heap and temp list. This is illustrated in the code below.\n",
    "4.Time complexity is O(N * n) where N is the number of tasks and n is the cool-off period.\n",
    "5.Space complexity is O(1) - will not be more than O(26)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def leastInterval(self, tasks: List[str], N: int) -> int:\n",
    "    count = Counter(tasks)\n",
    "    M = max(count.values())\n",
    "    Mct = list(count.values()).count(M)\n",
    "    #AAABBCDE,2\n",
    "    #A__, A__, A__ 3 most frequent interval \n",
    "    #ABC, ABD, AE_ (3-1)*(2+1) + 1 = 7, which is less than tasks\n",
    "    return max(len(tasks), (M-1)*(N+1) + Mct)\n",
    "        \n",
    "\n",
    "from heapq import heappush, heappop\n",
    "from collections import Counter\n",
    "\n",
    "def leastInterval(self, tasks, n):\n",
    "    curr_time, h = 0, []\n",
    "    for k,v in Counter(tasks).items():\n",
    "        heappush(h, (-1*v, k))\n",
    "    while h:\n",
    "        i, temp = 0, []\n",
    "        while i <= n:\n",
    "            curr_time += 1\n",
    "            if h:\n",
    "                x,y = heappop(h)\n",
    "                if x != -1:\n",
    "                    temp.append((x+1,y))\n",
    "            if not h and not temp:\n",
    "                break\n",
    "            else:\n",
    "                i += 1\n",
    "        for item in temp:\n",
    "            heappush(h, item)\n",
    "    return curr_time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Convert Binary Search Tree to Sorted Doubly Linked List\n",
    "Medium\n",
    "Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.\n",
    "\n",
    "Let's take the following BST as an example, it may help you understand the problem better:\n",
    "\n",
    "![](https://assets.leetcode.com/uploads/2018/10/12/bstdlloriginalbst.png)\n",
    "\n",
    "\n",
    " \n",
    "We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.\n",
    "\n",
    "The figure below shows the circular doubly linked list for the BST above. The \"head\" symbol means the node it points to is the smallest element of the linked list.\n",
    "\n",
    " ![](https://assets.leetcode.com/uploads/2018/10/12/bstdllreturndll.png)\n",
    "\n",
    "\n",
    " \n",
    "Specifically, we want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. We should return the pointer to the first element of the linked list.\n",
    "\n",
    "The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.\n",
    "\n",
    " \n",
    "![](https://assets.leetcode.com/uploads/2018/10/12/bstdllreturnbst.png)\n",
    "\n",
    "Accepted\n",
    "27.7K\n",
    "Submissions\n",
    "53.4K"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def treeToDoublyList(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        h, t = self.helper(root)\n",
    "        h.left = t\n",
    "        t.right = h\n",
    "        return h        \n",
    "    \n",
    "    def helper(self, node):\n",
    "        # will flat the node and return head and tail of the link list \n",
    "        if not node.left and not node.right:\n",
    "            return node, node \n",
    "        \n",
    "        if node.left:\n",
    "            lh, lt = self.helper(node.left)\n",
    "            lt.right = node\n",
    "            node.left = lt\n",
    "        else:\n",
    "            lh, lt = node, node \n",
    "        \n",
    "        if node.right:\n",
    "            rh, rt = self.helper(node.right)\n",
    "            rh.left = node \n",
    "            node.right = rh\n",
    "        else:\n",
    "            rh, rt = node, node\n",
    "        \n",
    "        return lh, rt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Product of Array Except Self\n",
    "Medium\n",
    "Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].\n",
    "\n",
    "Example:\n",
    "\n",
    "Input:  [1,2,3,4]\n",
    "Output: [24,12,8,6]\n",
    "Note: Please solve it without division and in O(n).\n",
    "\n",
    "Follow up:\n",
    "Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)\n",
    "\n",
    "Accepted\n",
    "254.1K\n",
    "Submissions\n",
    "462.9K"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def productExceptSelf(self, nums) -> list:\n",
    "    p = 1\n",
    "    output = []\n",
    "    n = len(nums)\n",
    "    for i in range(n):\n",
    "        output.append(p)\n",
    "        p *= nums[i]\n",
    "\n",
    "    p = 1 \n",
    "    # output = [1,1,2,6], miss the last\n",
    "\n",
    "    for i in range(n-1, -1, -1):\n",
    "        output[i] = p * output[i]\n",
    "        p *= nums[i]\n",
    "    # p come after 1 digit\n",
    "    return output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### K Closest Points to Origin\n",
    "Medium\n",
    "\n",
    "We have a list of points on the plane.  Find the K closest points to the origin (0, 0).\n",
    "\n",
    "(Here, the distance between two points on a plane is the Euclidean distance.)\n",
    "\n",
    "You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)\n",
    "\n",
    " \n",
    "```\n",
    "Example 1:\n",
    "\n",
    "Input: points = [[1,3],[-2,2]], K = 1\n",
    "Output: [[-2,2]]\n",
    "Explanation: \n",
    "The distance between (1, 3) and the origin is sqrt(10).\n",
    "The distance between (-2, 2) and the origin is sqrt(8).\n",
    "Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.\n",
    "We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].\n",
    "Example 2:\n",
    "\n",
    "Input: points = [[3,3],[5,-1],[-2,4]], K = 2\n",
    "Output: [[3,3],[-2,4]]\n",
    "(The answer [[-2,4],[3,3]] would also be accepted.)\n",
    " \n",
    "\n",
    "Note:\n",
    "\n",
    "1 <= K <= points.length <= 10000\n",
    "-10000 < points[i][0] < 10000\n",
    "-10000 < points[i][1] < 10000\n",
    "```\n",
    "简单排序，或者大小堆"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:\n",
    "        return sorted(points, key=lambda x: x[0]**2 + x[1]**2)[:K]\n",
    "\n",
    "    def kClosets(self, points, K):\n",
    "        return heapq.nsmallest(K, points, lambda x: x[0]**2 + x[1]**2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from heapq import heappush, heappop\n",
    "\n",
    "class Point(object):\n",
    "    def __init__(self, x, y):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "    \n",
    "    def __lt__(self, other):# pay attention here, heap is min-heap, reverse lt relation.\n",
    "        return (self.x**2 + self.y**2) > (other.x**2 + other.y**2)\n",
    "    \n",
    "    def __eq__(self, other):\n",
    "        return (self.x**2 + self.y**2) == (other.x**2 + other.y**2)\n",
    "    \n",
    "    def __gt__(self, other):\n",
    "        return (self.x**2 + self.y**2) < (other.x**2 + other.y**2)\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:\n",
    "        heap = []\n",
    "        \n",
    "        for x, y in points:\n",
    "            p = Point(x,y)\n",
    "            heappush(heap, p)\n",
    "            if len(heap) > K:\n",
    "                heappop(heap)\n",
    "        \n",
    "        \n",
    "        ans = [[p.x, p.y] for p in heap]\n",
    "        \n",
    "        return sorted(ans, key = lambda x: x[0]**2 + x[1]**2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Why dist is made negative? \n",
    "\n",
    "short ans, we want to pop out the largest one every time. \n",
    "\n",
    "Python's heapq is implemented as min heap.\n",
    "\n",
    "However, what we actually want is a max heap where when we 'pop' an element from the max heap, we get the largest element currently in the heap.\n",
    "\n",
    "Let's take example of points = [[1,3],[-2,2]], K = 1.\n",
    "If we were to push both [1,3] and [2,2] to heap by their Euclidean distance, then our heap would have [(10, 1, 3), (8, -2, 2)].\n",
    "When we \"pop\" an element, we want to pop (10, 1, 3), which is how max heap works.\n",
    "\n",
    "Since Python's heapq is implemeneted as min heap, we would actually get (8,-2,2) which is not what we want.\n",
    "To use Python's heapq as Max heap, I just reversed sign of Euclidean distance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:\n",
    "        \n",
    "        heap = []\n",
    "        \n",
    "        for (x, y) in points:\n",
    "            dist = -(x*x + y*y)\n",
    "            if len(heap) == K:\n",
    "                heapq.heappushpop(heap, (dist, x, y))\n",
    "            else:\n",
    "                heapq.heappush(heap, (dist, x, y))\n",
    "        \n",
    "        return [(x,y) for (dist,x, y) in heap]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Binary Search Tree Iterator\n",
    "Medium\n",
    "Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.\n",
    "\n",
    "Calling next() will return the next smallest number in the BST.\n",
    "\n",
    " \n",
    "```\n",
    "Example:\n",
    "\n",
    "\n",
    "\n",
    "BSTIterator iterator = new BSTIterator(root);\n",
    "iterator.next();    // return 3\n",
    "iterator.next();    // return 7\n",
    "iterator.hasNext(); // return true\n",
    "iterator.next();    // return 9\n",
    "iterator.hasNext(); // return true\n",
    "iterator.next();    // return 15\n",
    "iterator.hasNext(); // return true\n",
    "iterator.next();    // return 20\n",
    "iterator.hasNext(); // return false\n",
    " \n",
    "\n",
    "Note:\n",
    "\n",
    "next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.\n",
    "You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BSTIterator:\n",
    "# @param root, a binary search tree's root node\n",
    "    def __init__(self, root):\n",
    "        self.stack = []\n",
    "        self.allLeftIntoStack(root)\n",
    "\n",
    "    # @return a boolean, whether we have a next smallest number\n",
    "    def hasNext(self):\n",
    "        return True if self.stack else False\n",
    "\n",
    "    # @return an integer, the next smallest number\n",
    "    def next(self):\n",
    "        cur = self.stack.pop()\n",
    "        self.allLeftIntoStack(cur.right)\n",
    "        return cur.val\n",
    "        \n",
    "    def allLeftIntoStack(self, node):\n",
    "        while node:\n",
    "            self.stack.append(node)\n",
    "            node = node.left"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Binary Tree Vertical Order Traversal\n",
    "Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).\n",
    "\n",
    "If two nodes are in the same row and column, the order should be from left to right.\n",
    "\n",
    "```\n",
    "Examples 1:\n",
    "\n",
    "Input: [3,9,20,null,null,15,7]\n",
    "\n",
    "   3\n",
    "  /\\\n",
    " /  \\\n",
    " 9  20\n",
    "    /\\\n",
    "   /  \\\n",
    "  15   7 \n",
    "\n",
    "Output:\n",
    "\n",
    "[\n",
    "  [9],\n",
    "  [3,15],\n",
    "  [20],\n",
    "  [7]\n",
    "]\n",
    "Examples 2:\n",
    "\n",
    "Input: [3,9,8,4,0,1,7]\n",
    "\n",
    "     3\n",
    "    /\\\n",
    "   /  \\\n",
    "   9   8\n",
    "  /\\  /\\\n",
    " /  \\/  \\\n",
    " 4  01   7 \n",
    "\n",
    "Output:\n",
    "\n",
    "[\n",
    "  [4],\n",
    "  [9],\n",
    "  [3,0,1],\n",
    "  [8],\n",
    "  [7]\n",
    "]\n",
    "Examples 3:\n",
    "\n",
    "Input: [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5)\n",
    "\n",
    "     3\n",
    "    /\\\n",
    "   /  \\\n",
    "   9   8\n",
    "  /\\  /\\\n",
    " /  \\/  \\\n",
    " 4  01   7\n",
    "    /\\\n",
    "   /  \\\n",
    "   5   2\n",
    "\n",
    "Output:\n",
    "\n",
    "[\n",
    "  [4],\n",
    "  [9,5],\n",
    "  [3,0,1],\n",
    "  [8,2],\n",
    "  [7]\n",
    "]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def verticalOrder(self, root):\n",
    "    cols = collections.defaultdict(list)\n",
    "    queue = [(root, 0)]\n",
    "    for node, i in queue:\n",
    "        if node:\n",
    "            cols[i].append(node.val)\n",
    "            queue += (node.left, i - 1), (node.right, i + 1)\n",
    "    return [cols[i] for i in sorted(cols)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Binary Tree Path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# dfs + stack\n",
    "def binaryTreePaths1(self, root):\n",
    "    if not root:\n",
    "        return []\n",
    "    res, stack = [], [(root, \"\")]\n",
    "    while stack:\n",
    "        node, ls = stack.pop()\n",
    "        if not node.left and not node.right:\n",
    "            res.append(ls+str(node.val))\n",
    "        if node.right:\n",
    "            stack.append((node.right, ls+str(node.val)+\"->\"))\n",
    "        if node.left:\n",
    "            stack.append((node.left, ls+str(node.val)+\"->\"))\n",
    "    return res\n",
    "    \n",
    "# bfs + queue\n",
    "def binaryTreePaths2(self, root):\n",
    "    if not root:\n",
    "        return []\n",
    "    res, queue = [], collections.deque([(root, \"\")])\n",
    "    while queue:\n",
    "        node, ls = queue.popleft()\n",
    "        if not node.left and not node.right:\n",
    "            res.append(ls+str(node.val))\n",
    "        if node.left:\n",
    "            queue.append((node.left, ls+str(node.val)+\"->\"))\n",
    "        if node.right:\n",
    "            queue.append((node.right, ls+str(node.val)+\"->\"))\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Is Graph Bipartite?\n",
    "Medium\n",
    "Given an undirected graph, return true if and only if it is bipartite.\n",
    "\n",
    "Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.\n",
    "\n",
    "The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists.  Each node is an integer between 0 and graph.length - 1.  There are no self edges or parallel edges: graph[i] does not contain i, and it doesn't contain any element twice.\n",
    "```\n",
    "Example 1:\n",
    "Input: [[1,3], [0,2], [1,3], [0,2]]\n",
    "Output: true\n",
    "Explanation: \n",
    "The graph looks like this:\n",
    "0----1\n",
    "|    |\n",
    "|    |\n",
    "3----2\n",
    "We can divide the vertices into two groups: {0, 2} and {1, 3}.\n",
    "Example 2:\n",
    "Input: [[1,2,3], [0,2], [0,1,3], [0,2]]\n",
    "Output: false\n",
    "Explanation: \n",
    "The graph looks like this:\n",
    "0----1\n",
    "| \\  |\n",
    "|  \\ |\n",
    "3----2\n",
    "We cannot find a way to divide the set of nodes into two independent subsets.\n",
    " ```\n",
    "\n",
    "Note:\n",
    "\n",
    "graph will have length in range [1, 100].\n",
    "graph[i] will contain integers in range [0, graph.length - 1].\n",
    "graph[i] will not contain i or duplicate values.\n",
    "The graph is undirected: if any element j is in graph[i], then i will be in graph[j]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "class Solution:\n",
    "    def isBipartite(self, graph) -> bool:\n",
    "        if not graph:\n",
    "            return True\n",
    "        n = len(graph)\n",
    "        color = [-1] * n # uncolocred n nodes         \n",
    "        for i in range(n):\n",
    "            if color[i] == -1: # not colored yet, color it to while 0\n",
    "                deck = deque([i])\n",
    "                color[i] = 0\n",
    "                while deck:\n",
    "                    node = deck.popleft()\n",
    "                    for adjnode in graph[node]:\n",
    "                        if color[adjnode] == -1:\n",
    "                            color[adjnode] = 1 - color[node]\n",
    "                            deck.append(adjnode)\n",
    "                        elif color[node] == color[adjnode]:\n",
    "                            return False\n",
    "                        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Interval List Intersections\n",
    "Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.\n",
    "\n",
    "Return the intersection of these two interval lists.\n",
    "\n",
    "(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.  The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval.  For example, the intersection of [1, 3] and [2, 4] is [2, 3].)\n",
    "![](https://assets.leetcode.com/uploads/2019/01/30/interval1.png)\n",
    "```\n",
    "\n",
    "Example 1:\n",
    "\n",
    "\n",
    "\n",
    "Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]\n",
    "Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]\n",
    "Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.\n",
    " \n",
    "\n",
    "Note:\n",
    "\n",
    "0 <= A.length < 1000\n",
    "0 <= B.length < 1000\n",
    "0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9\n",
    "NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def intervalIntersection(self, A, B):\n",
    "        \"\"\"\n",
    "        思路：\n",
    "        S表示start， E表示end\n",
    "        1. 建立一个栈s\n",
    "        2. 遇到S，将s入栈，遇到E，s最上层pop出来\n",
    "        3. 那么s栈内存在三种情况：空，一个S，两个S，不会出现三个（因为接下来必会遇到E）\n",
    "        4. 如果s栈内有两个S，那么[S,E]是交集，如果只一个S，那么不是交集，直接扔掉\n",
    "        \"\"\"\n",
    "        if not A or not B:\n",
    "            return []\n",
    "        a = []\n",
    "        b = []\n",
    "        s = []\n",
    "        ret = []\n",
    "        # 为了使用栈结构，反向\n",
    "        A.reverse()\n",
    "        B.reverse()\n",
    "        while (A or a) and (B or b):\n",
    "            if not a:\n",
    "                a = A.pop()\n",
    "                # 为了使用栈结构，先start 后end\n",
    "                a = [a.end, a.start]\n",
    "            if not b:\n",
    "                b = B.pop()\n",
    "                # 为了使用栈结构，先start 后end\n",
    "                b = [b.end, b.start]\n",
    "            c = a \n",
    "            if a[-1] < b[-1]:\n",
    "                c = a\n",
    "            elif a[-1] > b[-1]:\n",
    "                c = b\n",
    "            else:\n",
    "                # 如果值相等的话，优先使用start，也就是len()==2\n",
    "                c = a if len(a)==2 else b\n",
    "            if len(c)==2:\n",
    "                s.append(c.pop())\n",
    "            else:\n",
    "                num = s.pop()\n",
    "                num_end = c.pop()\n",
    "                if len(s):\n",
    "                    ret.append([num, num_end])\n",
    "                else:\n",
    "                    # 非交集，扔掉\n",
    "                    pass\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Clone Graph\n",
    "Medium\n",
    "Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.\n",
    "\n",
    " \n",
    "```\n",
    "Example:\n",
    "```\n",
    "![](https://assets.leetcode.com/uploads/2019/02/19/113_sample.png)\n",
    "```\n",
    "Input:\n",
    "{\"$id\":\"1\",\"neighbors\":[{\"$id\":\"2\",\"neighbors\":[{\"$ref\":\"1\"},{\"$id\":\"3\",\"neighbors\":[{\"$ref\":\"2\"},{\"$id\":\"4\",\"neighbors\":[{\"$ref\":\"3\"},{\"$ref\":\"1\"}],\"val\":4}],\"val\":3}],\"val\":2},{\"$ref\":\"4\"}],\"val\":1}\n",
    "\n",
    "Explanation:\n",
    "Node 1's value is 1, and it has two neighbors: Node 2 and 4.\n",
    "Node 2's value is 2, and it has two neighbors: Node 1 and 3.\n",
    "Node 3's value is 3, and it has two neighbors: Node 2 and 4.\n",
    "Node 4's value is 4, and it has two neighbors: Node 1 and 3.\n",
    " \n",
    "\n",
    "Note:\n",
    "\n",
    "The number of nodes will be between 1 and 100.\n",
    "The undirected graph is a simple graph, which means no repeated edges and no self-loops in the graph.\n",
    "Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.\n",
    "You must return the copy of the given node as a reference to the cloned graph.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# BFS, less space\n",
    "def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "    if not node:\n",
    "        return \n",
    "    nodeCopy = Node(node.val, [])\n",
    "    dic = {node: nodeCopy}\n",
    "    queue = collections.deque([node])\n",
    "    while queue:\n",
    "        node = queue.popleft()\n",
    "        for neighbor in node.neighbors:\n",
    "            if neighbor not in dic: # neighbor is not visited\n",
    "                neighborCopy = Node(neighbor.val, [])\n",
    "                dic[neighbor] = neighborCopy\n",
    "                dic[node].neighbors.append(neighborCopy)\n",
    "                queue.append(neighbor)\n",
    "            else:\n",
    "                dic[node].neighbors.append(dic[neighbor])\n",
    "    return nodeCopy    \n",
    "    \n",
    "# DFS iteratively\n",
    "def cloneGraph2(self, node):# fast \n",
    "    if not node:\n",
    "        return \n",
    "    nodeCopy = UndirectedGraphNode(node.label)\n",
    "    dic = {node: nodeCopy}\n",
    "    stack = [node]\n",
    "    while stack:\n",
    "        node = stack.pop()\n",
    "        for neighbor in node.neighbors:\n",
    "            if neighbor not in dic:\n",
    "                neighborCopy = UndirectedGraphNode(neighbor.label)\n",
    "                dic[neighbor] = neighborCopy\n",
    "                dic[node].neighbors.append(neighborCopy)\n",
    "                stack.append(neighbor)\n",
    "            else:\n",
    "                dic[node].neighbors.append(dic[neighbor])\n",
    "    return nodeCopy\n",
    "    \n",
    "# DFS recursively, roughly the same as before.\n",
    "def cloneGraph(self, node):\n",
    "    if not node:\n",
    "        return \n",
    "    nodeCopy = UndirectedGraphNode(node.label)\n",
    "    dic = {node: nodeCopy}\n",
    "    self.dfs(node, dic)\n",
    "    return nodeCopy\n",
    "    \n",
    "def dfs(self, node, dic):\n",
    "    for neighbor in node.neighbors:\n",
    "        if neighbor not in dic:\n",
    "            neighborCopy = UndirectedGraphNode(neighbor.label)\n",
    "            dic[neighbor] = neighborCopy\n",
    "            dic[node].neighbors.append(neighborCopy)\n",
    "            self.dfs(neighbor, dic)\n",
    "        else:\n",
    "            dic[node].neighbors.append(dic[neighbor])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Validate Binary Search Tree\n",
    "Medium\n",
    "\n",
    "1896\n",
    "\n",
    "283\n",
    "\n",
    "Favorite\n",
    "\n",
    "Share\n",
    "Given a binary tree, determine if it is a valid binary search tree (BST).\n",
    "\n",
    "Assume a BST is defined as follows:\n",
    "\n",
    "The left subtree of a node contains only nodes with keys less than the node's key.\n",
    "The right subtree of a node contains only nodes with keys greater than the node's key.\n",
    "Both the left and right subtrees must also be binary search trees.\n",
    " \n",
    "```\n",
    "Example 1:\n",
    "\n",
    "    2\n",
    "   / \\\n",
    "  1   3\n",
    "\n",
    "Input: [2,1,3]\n",
    "Output: true\n",
    "Example 2:\n",
    "\n",
    "    5\n",
    "   / \\\n",
    "  1   4\n",
    "     / \\\n",
    "    3   6\n",
    "\n",
    "Input: [5,1,4,null,null,3,6]\n",
    "Output: false\n",
    "Explanation: The root node's value is 5 but its right child's value is 4.\n",
    "```\n",
    "Solution: just need to use in-order traverse and see if it is sorted number, that's it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param root: The root of binary tree.\n",
    "    @return: True if the binary tree is BST, or false\n",
    "    \"\"\"  \n",
    "    def isValidBST(self, root):\n",
    "        self.lastVal = - 2**32 \n",
    "        self.isBST = True\n",
    "        self.valid(root)\n",
    "        return self.isBST\n",
    "    \n",
    "    def valid(self, node): # in-order traversal\n",
    "        if node is None:\n",
    "            return\n",
    "        \n",
    "        self.valid(node.left)\n",
    "        if self.lastVal >= node.val:\n",
    "            self.isBST = None\n",
    "            return\n",
    "        self.lastVal = node.val\n",
    "        self.valid(node.right)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Accounts Merge\n",
    "\n",
    "Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.\n",
    "\n",
    "Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.\n",
    "\n",
    "After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.\n",
    "\n",
    "```\n",
    "Example 1:\n",
    "Input: \n",
    "accounts = [[\"John\", \"johnsmith@mail.com\", \"john00@mail.com\"], [\"John\", \"johnnybravo@mail.com\"], [\"John\", \"johnsmith@mail.com\", \"john_newyork@mail.com\"], [\"Mary\", \"mary@mail.com\"]]\n",
    "Output: [[\"John\", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  [\"John\", \"johnnybravo@mail.com\"], [\"Mary\", \"mary@mail.com\"]]\n",
    "Explanation: \n",
    "The first and third John's are the same person as they have the common email \"johnsmith@mail.com\".\n",
    "The second John and Mary are different people as none of their email addresses are used by other accounts.\n",
    "We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'], ['John', 'johnnybravo@mail.com'], \n",
    "['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be accepted.\n",
    "Note:\n",
    "\n",
    "The length of accounts will be in the range [1, 1000].\n",
    "The length of accounts[i] will be in the range [1, 10].\n",
    "The length of accounts[i][j] will be in the range [1, 30].\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We give each account an ID, based on the index of it within the list of accounts.\n",
    "```\n",
    "[\n",
    "[\"John\", \"johnsmith@mail.com\", \"john00@mail.com\"], # Account 0\n",
    "[\"John\", \"johnnybravo@mail.com\"], # Account 1\n",
    "[\"John\", \"johnsmith@mail.com\", \"john_newyork@mail.com\"],  # Account 2\n",
    "[\"Mary\", \"mary@mail.com\"] # Account 3\n",
    "]\n",
    "Next, build an emails_accounts_map that maps an email to a list of accounts, which can be used to track which email is linked to which account. This is essentially our graph.\n",
    "\n",
    "# emails_accounts_map of email to account ID\n",
    "{\n",
    "  \"johnsmith@mail.com\": [0, 2],\n",
    "  \"john00@mail.com\": [0],\n",
    "  \"johnnybravo@mail.com\": [1],\n",
    "  \"john_newyork@mail.com\": [2],\n",
    "  \"mary@mail.com\": [3]\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def accountsMerge(self, accounts):\n",
    "        d = {}  # key:val = email:index\n",
    "        from collections import defaultdict\n",
    "        graph = defaultdict(list)   # graph connecting the indices of the same account\n",
    "        for i, a in enumerate(accounts):\n",
    "            for email in a[1:]:\n",
    "                if email in d:\n",
    "                    graph[i].append(d[email])\n",
    "                    graph[d[email]].append(i)\n",
    "                else:\n",
    "                    d[email] = i\n",
    "        \n",
    "        # dfs, return indices belong to the same account\n",
    "        def dfs(i):\n",
    "            tmp = {i}\n",
    "            for j in graph[i]:\n",
    "                if j not in seen:\n",
    "                    seen.add(j)\n",
    "                    tmp |= dfs(j)\n",
    "            return tmp\n",
    "                    \n",
    "        seen = set()\n",
    "        res = [] \n",
    "        for i in range(len(accounts)):\n",
    "            if i in seen:\n",
    "                continue\n",
    "            res.append([accounts[i][0]] + sorted(set(email for j in dfs(i) for email in accounts[j][1:])))\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "##Union Find:\n",
    "\n",
    "class Solution(object):\n",
    "    def accountsMerge(self, accounts):        \n",
    "        n = len(accounts)\n",
    "        father = [_ for _ in range(n)]\n",
    "\n",
    "        def find(i):\n",
    "            while father[i] != i:\n",
    "                father[i] = father[father[i]]\n",
    "                i = father[i]\n",
    "            return i \n",
    "        \n",
    "        # union & find\n",
    "        d = {} \n",
    "        for i in range(n):\n",
    "            for email in accounts[i][1:]:\n",
    "                if email in d:\n",
    "                    fa, fb = find(i), find(d[email])\n",
    "                    father[fb] = fa\n",
    "                else:\n",
    "                    d[email] = i\n",
    "        \n",
    "        res0 = collections.defaultdict(set)\n",
    "        \n",
    "        for i in range(n):\n",
    "            res0[find(i)] |= set(accounts[i][1:])\n",
    "        \n",
    "        res = []\n",
    "        for k, v in res0.items():\n",
    "            res.append([accounts[k][0]] + sorted(v))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### One Edit Distance\n",
    "Given two strings s and t, determine if they are both one edit distance apart.\n",
    "\n",
    "Note: \n",
    "\n",
    "There are 3 possiblities to satisify one edit distance apart:\n",
    "\n",
    "Insert a character into s to get t\n",
    "Delete a character from s to get t\n",
    "Replace a character of s to get t\n",
    "Example 1:\n",
    "\n",
    "Input: s = \"ab\", t = \"acb\"\n",
    "Output: true\n",
    "Explanation: We can insert 'c' into s to get t.\n",
    "Example 2:\n",
    "\n",
    "Input: s = \"cab\", t = \"ad\"\n",
    "Output: false\n",
    "Explanation: We cannot get t from s by only one step.\n",
    "Example 3:\n",
    "\n",
    "Input: s = \"1203\", t = \"1213\"\n",
    "Output: true\n",
    "Explanation: We can replace '0' with '1' to get t."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isOneEditDistance(self, s, t):\n",
    "    if s == t:\n",
    "        return False\n",
    "    l1, l2 = len(s), len(t)\n",
    "    if l1 > l2: # force s no longer than t\n",
    "        return self.isOneEditDistance(t, s)\n",
    "    if l2 - l1 > 1:\n",
    "        return False\n",
    "    for i in range(len(s)):\n",
    "        if s[i] != t[i]:\n",
    "            if l1 == l2:\n",
    "                s = s[:i]+t[i]+s[i+1:]  # replacement\n",
    "            else:\n",
    "                s = s[:i]+t[i]+s[i:]  # insertion\n",
    "            break\n",
    "    return s == t or s == t[:-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  Reorder List\n",
    "Medium\n",
    "\n",
    "858\n",
    "\n",
    "66\n",
    "\n",
    "Favorite\n",
    "\n",
    "Share\n",
    "Given a singly linked list L: L0→L1→…→Ln-1→Ln,\n",
    "reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…\n",
    "\n",
    "You may not modify the values in the list's nodes, only nodes itself may be changed.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Given 1->2->3->4, reorder it to 1->4->2->3.\n",
    "Example 2:\n",
    "\n",
    "Given 1->2->3->4->5, reorder it to 1->5->2->4->3.\n",
    "\n",
    "\n",
    "Notes: Does't matter if the length of the list is odd or even, find mid, split, reverse the second list and insert. Pretty straightfowward.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def reorderList(self, head):\n",
    "        if not head or not head.next or not head.next.next: \n",
    "            return\n",
    "        slow, fast = head, head\n",
    "        while fast.next and fast.next.next: \n",
    "            slow, fast = slow.next, fast.next.next\n",
    "\n",
    "        head1, head2 = head, slow.next\n",
    "\n",
    "        slow.next, cur, pre = None, head2, None\n",
    "\n",
    "        # reverse the second list\n",
    "        while cur:\n",
    "            curnext = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = curnext\n",
    "\n",
    "        cur1, cur2 = head1, pre\n",
    "        # insert \n",
    "        while cur2:\n",
    "            next1, next2 = cur1.next, cur2.next\n",
    "            cur1.next = cur2\n",
    "            cur2.next = next1\n",
    "            cur1, cur2 = next1, next2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Next Permutation\n",
    "Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.\n",
    "\n",
    "If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).\n",
    "\n",
    "The replacement must be in-place and use only constant extra memory.\n",
    "\n",
    "Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.\n",
    "\n",
    "1,2,3 → 1,3,2\n",
    "3,2,1 → 1,2,3\n",
    "1,1,5 → 1,5,1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 1, 3]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param nums: A list of integers\n",
    "    @return: A list of integers\n",
    "    \"\"\"\n",
    "    def nextPermutation(self, nums):\n",
    "        if nums is None or len(nums) == 0:\n",
    "            return nums\n",
    "        n = len(nums)        \n",
    "        for i in range(n-2, -1, -1):\n",
    "            if nums[i] < nums[i+1]:\n",
    "                break\n",
    "        else:\n",
    "            nums.reverse()\n",
    "            return nums\n",
    "        \n",
    "        # find the first element larger than i\n",
    "        for j in range(n-1, i, -1):\n",
    "            if nums[j] > nums[i]:\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "                break\n",
    "        \n",
    "        self.reverse(nums, i+1, n-1)\n",
    "        \n",
    "        return nums\n",
    "    \n",
    "    def reverse(self, nums, start, end):\n",
    "        while start < end:\n",
    "            nums[start], nums[end] = nums[end], nums[start]\n",
    "            start += 1\n",
    "            end -= 1 \n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    print(s.nextPermutation([1,3,2]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Permutaion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def permute(self, nums):\n",
    "        ans = []\n",
    "        def dfs(path, res):\n",
    "\n",
    "            if len(path) == len(nums):\n",
    "                ans.append(path)\n",
    "                return\n",
    "\n",
    "            for i in range(len(res)):\n",
    "                ch = res[i]\n",
    "                new_res = res[:i] + res[i+1:]\n",
    "                dfs(path + [ch], new_res)\n",
    "\n",
    "        dfs([], nums)\n",
    "        return ans\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    print(s.permute([1,2,3]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1]]\n",
      "[[1, 1]]\n",
      "[[2, 1, 1]]\n",
      "[[2, 1, 1], [1, 2, 1]]\n",
      "[[2, 1, 1], [1, 2, 1], [1, 1, 2]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[[2, 1, 1], [1, 2, 1], [1, 1, 2]]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def permuteUnique(nums):\n",
    "    ans = [[]]\n",
    "    for n in nums:\n",
    "        new_ans = []\n",
    "        for l in ans:\n",
    "            for i in range(len(l)+1):\n",
    "                new_ans.append(l[:i]+[n]+l[i:])\n",
    "                print(new_ans)\n",
    "                if i<len(l) and l[i]==n: break              #handles duplication\n",
    "        ans = new_ans\n",
    "    return ans\n",
    "\n",
    "permuteUnique([1,1,2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 1, 2], [1, 2, 1], [2, 1, 1]]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def Permutation2(S):\n",
    "    if S is None:\n",
    "        return []\n",
    "    if S is []:\n",
    "        return [[]]\n",
    "\n",
    "    def dfs(tmp, s):\n",
    "        if s == []:\n",
    "            res.append(tmp)\n",
    "            return\n",
    "        for i in range(len(s)):\n",
    "            if 0 < i < len(s) and s[i] == s[i-1]:\n",
    "                continue\n",
    "            dfs(tmp + [s[i]], s[:i] + s[i+1:])\n",
    "            #dfs(s[i] + tmp, s[:i] + s[i+1:])\n",
    "    res = []\n",
    "    dfs([], S)\n",
    "    return res\n",
    "\n",
    "Permutation2([1,1,2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Interval List Intersections\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def intervalIntersection(self, A: 'List[Interval]', B: 'List[Interval]') -> 'List[Interval]':\n",
    "        res = []\n",
    "        i = j = 0\n",
    "        while i < len(A) and j < len(B):\n",
    "            if A[i].start <= B[j].end and B[j].start <= A[i].end:\n",
    "                res.append([max(A[i].start, B[j].start), min(A[i].end, B[j].end)])\n",
    "            if A[i].end < B[j].end:\n",
    "                i+=1\n",
    "            else:    \n",
    "                j+=1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Continuous Subarray Sum\n",
    "\n",
    "Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.\n",
    "\n",
    " \n",
    "```\n",
    "Example 1:\n",
    "\n",
    "Input: [23, 2, 4, 6, 7],  k=6\n",
    "Output: True\n",
    "Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.\n",
    "Example 2:\n",
    "\n",
    "Input: [23, 2, 6, 4, 7],  k=6\n",
    "Output: True\n",
    "Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def checkSubarraySum(nums, k):\n",
    "    rmap = {0:-1} # pass case[0,0], 0\n",
    "    rum = 0\n",
    "    for i, num in enumerate(nums):\n",
    "        rum += num\n",
    "        if k != 0:\n",
    "            rum %= k \n",
    "        if rum in rmap:\n",
    "            if i - rmap[rum] > 1:\n",
    "                return True\n",
    "        else:\n",
    "            rmap[rum] = i\n",
    "    return False\n",
    "checkSubarraySum([0,0,0], 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Kth largest number in an array\n",
    "Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: [3,2,1,5,6,4] and k = 2\n",
    "Output: 5\n",
    "Example 2:\n",
    "\n",
    "Input: [3,2,3,1,2,4,5,5,6] and k = 4\n",
    "Output: 4\n",
    "Note: \n",
    "You may assume k is always valid, 1 ≤ k ≤ array's length."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# O(nlgn) time\n",
    "def findKthLargest1(self, nums, k):\n",
    "    return sorted(nums, reverse=True)[k-1]\n",
    "    \n",
    "# O(nk) time, bubble sort idea, TLE\n",
    "def findKthLargest2(self, nums, k):\n",
    "    for i in xrange(k):\n",
    "        for j in xrange(len(nums)-i-1):\n",
    "            if nums[j] > nums[j+1]:\n",
    "                # exchange elements, time consuming\n",
    "                nums[j], nums[j+1] = nums[j+1], nums[j]\n",
    "    return nums[len(nums)-k]\n",
    "    \n",
    "# O(nk) time, selection sort idea\n",
    "def findKthLargest3(self, nums, k):\n",
    "    for i in xrange(len(nums), len(nums)-k, -1):\n",
    "        tmp = 0\n",
    "        for j in xrange(i):\n",
    "            if nums[j] > nums[tmp]:\n",
    "                tmp = j\n",
    "        nums[tmp], nums[i-1] = nums[i-1], nums[tmp]\n",
    "    return nums[len(nums)-k]\n",
    "    \n",
    "# O(k+(n-k)lgk) time, min-heap\n",
    "def findKthLargest4(self, nums, k):\n",
    "    heap = []\n",
    "    for num in nums:\n",
    "        heapq.heappush(heap, num)\n",
    "    for _ in xrange(len(nums)-k):\n",
    "        heapq.heappop(heap)\n",
    "    return heapq.heappop(heap)\n",
    "\n",
    "# O(k+(n-k)lgk) time, min-heap        \n",
    "def findKthLargest5(self, nums, k):\n",
    "    return heapq.nlargest(k, nums)[k-1]\n",
    "    \n",
    "# O(n) time, quick selection\n",
    "def findKthLargest(self, nums, k):\n",
    "    # convert the kth largest to smallest\n",
    "    return self.findKthSmallest(nums, len(nums)+1-k)\n",
    "    \n",
    "def findKthSmallest(self, nums, k):\n",
    "    if nums:\n",
    "        pos = self.partition(nums, 0, len(nums)-1)\n",
    "        if k > pos+1:\n",
    "            return self.findKthSmallest(nums[pos+1:], k-pos-1)\n",
    "        elif k < pos+1:\n",
    "            return self.findKthSmallest(nums[:pos], k)\n",
    "        else:\n",
    "            return nums[pos]\n",
    "\n",
    "#choese the right most as pivort\n",
    "def partition(self, nums, l, r):\n",
    "    low = l\n",
    "    while l < r:\n",
    "        if nums[l] < nums[r]:\n",
    "            nums[l], nums[low] = nums[low], nums[l]\n",
    "            low += 1\n",
    "        l += 1\n",
    "    nums[low], nums[r] = nums[r], nums[low]\n",
    "    return low"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Alien Dictionary\n",
    "Hard\n",
    "There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.\n",
    "```\n",
    "Example 1:\n",
    "\n",
    "Input:\n",
    "[\n",
    "  \"wrt\",\n",
    "  \"wrf\",\n",
    "  \"er\",\n",
    "  \"ett\",\n",
    "  \"rftt\"\n",
    "]\n",
    "\n",
    "Output: \"wertf\"\n",
    "Example 2:\n",
    "\n",
    "Input:\n",
    "[\n",
    "  \"z\",\n",
    "  \"x\"\n",
    "]\n",
    "\n",
    "Output: \"zx\"\n",
    "Example 3:\n",
    "\n",
    "Input:\n",
    "[\n",
    "  \"z\",\n",
    "  \"x\",\n",
    "  \"z\"\n",
    "] \n",
    "\n",
    "Output: \"\" \n",
    "\n",
    "Explanation: The order is invalid, so return \"\".\n",
    "Note:\n",
    "\n",
    "You may assume all letters are in lowercase.\n",
    "You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.\n",
    "If the order is invalid, return an empty string.\n",
    "There may be multiple valid order of letters, return any one of them is fine.\n",
    "```\n",
    "使用 heapq 作为 topological sorting 时所用的 queue。即可找到满足条件的最小序列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from heapq import heappush, heappop, heapify\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param words: a list of words\n",
    "    @return: a string which is correct order\n",
    "    \"\"\"\n",
    "    def alienOrder(self, words):\n",
    "        graph = self.build_graph(words)\n",
    "        return self.topological_sort(graph)\n",
    "        \n",
    "    def build_graph(self, words):\n",
    "        # key is node, value is neighbors\n",
    "        graph = {}\n",
    "\n",
    "        # initialize graph\n",
    "        for word in words:\n",
    "            for c in word:\n",
    "                if c not in graph:\n",
    "                    graph[c] = set() \n",
    "\n",
    "        # add edges        \n",
    "        n = len(words)\n",
    "        for i in range(n - 1):\n",
    "            for j in range(min(len(words[i]), len(words[i + 1]))):\n",
    "                if words[i][j] != words[i + 1][j]:\n",
    "                    graph[words[i][j]].add(words[i + 1][j])\n",
    "                    break\n",
    "                \n",
    "        return graph\n",
    "\n",
    "    def topological_sort(self, graph):\n",
    "        # before looking into this part of code\n",
    "        # you should know how to use bfs algorithm to do topological sorting\n",
    "        \n",
    "        # initialize indegree \n",
    "        indegree = {\n",
    "            node: 0\n",
    "            for node in graph\n",
    "        }\n",
    "        \n",
    "        # calculate indegree\n",
    "        for node in graph:\n",
    "            for neighbor in graph[node]:\n",
    "                indegree[neighbor] = indegree[neighbor] + 1\n",
    "        \n",
    "        # use heapq instead of regular queue so that we can get the \n",
    "        # smallest lexicographical order\n",
    "        '''\n",
    "        queue = [node for node in graph if indegree[node] == 0]\n",
    "        heapify(queue)\n",
    "        \n",
    "        # regular bfs algorithm to do topological sorting\n",
    "        topo_order = \"\"\n",
    "        while queue:\n",
    "            node = heappop(queue)\n",
    "            topo_order += node\n",
    "            for neighbor in graph[node]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if indegree[neighbor] == 0:\n",
    "                    heappush(queue, neighbor)\n",
    "            \n",
    "        # if all nodes popped\n",
    "        return topo_order if len(topo_order) == len(graph) else \"\"\n",
    "        '''\n",
    "        # regular bfs\n",
    "        que = [node for node in graph if indegree[node] == 0]\n",
    "        res = [] \n",
    "        while len(que) > 0:\n",
    "            curt = que.pop()\n",
    "            res.append(curt)\n",
    "            for nb in curt.neighbors:\n",
    "                indegree[nb] -= 1\n",
    "                if indegree[nb] == 0:\n",
    "                    que.append(nb)\n",
    "        return ''.join(res) if len(res) == len(graph) else \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Expression Add Operators\n",
    "Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.\n",
    "```\n",
    "Example 1:\n",
    "\n",
    "Input: num = \"123\", target = 6\n",
    "Output: [\"1+2+3\", \"1*2*3\"] \n",
    "Example 2:\n",
    "\n",
    "Input: num = \"232\", target = 8\n",
    "Output: [\"2*3+2\", \"2+3*2\"]\n",
    "Example 3:\n",
    "\n",
    "Input: num = \"105\", target = 5\n",
    "Output: [\"1*0+5\",\"10-5\"]\n",
    "Example 4:\n",
    "\n",
    "Input: num = \"00\", target = 0\n",
    "Output: [\"0+0\", \"0-0\", \"0*0\"]\n",
    "Example 5:\n",
    "\n",
    "Input: num = \"3456237490\", target = 9191\n",
    "Output: []\n",
    "```\n",
    "每一层递归都进行加减乘除的尝试，回溯。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        \n",
    "        res = []\n",
    "        n = len(num)\n",
    "        \n",
    "        def dfs(idx, path, tot, last):\n",
    "            if idx == n:\n",
    "                res.append(path) if tot == target else None\n",
    "                return\n",
    "            \n",
    "            for i in range(idx, n):\n",
    "                tmp = num[idx: i+1]\n",
    "                x = int(tmp)\n",
    "                if idx == 0:\n",
    "                    dfs(i+1, tmp, x, x)\n",
    "                else:\n",
    "                    dfs(i+1, path+'+'+tmp, tot+x, x)\n",
    "                    dfs(i+1, path+'-'+tmp, tot-x, -x)\n",
    "                    dfs(i+1, path+'*'+tmp, tot-last+last*x, last*x)\n",
    "                if x == 0:\n",
    "                    break\n",
    "        \n",
    "        dfs(0, '', 0, 0)        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Binary Tree Postorder Traversal\n",
    "Hard\n",
    "Given a binary tree, return the postorder traversal of its nodes' values.\n",
    "```\n",
    "Example:\n",
    "\n",
    "Input: [1,null,2,3]\n",
    "   1\n",
    "    \\\n",
    "     2\n",
    "    /\n",
    "   3\n",
    "\n",
    "Output: [3,2,1]\n",
    "Folow up: Recursive solution is trivial, could you do it iteratively?\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param root: The root of binary tree.\n",
    "    @return: Postorder in ArrayList which contains node values.\n",
    "    \"\"\"\n",
    "    result = []\n",
    "    \n",
    "    def traverse(self, root):\n",
    "        if root is None:\n",
    "            return\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "        self.results.append(root.val) \n",
    "\n",
    "\n",
    "\n",
    "    def postorderTraversal(self, root):\n",
    "        self.results = []\n",
    "        self.traverse(root)\n",
    "        return self.results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Word Ladder II\n",
    "Hard\n",
    "\n",
    "Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:\n",
    "\n",
    "Only one letter can be changed at a time\n",
    "Each transformed word must exist in the word list. Note that beginWord is not a transformed word.\n",
    "Note:\n",
    "\n",
    "Return an empty list if there is no such transformation sequence.\n",
    "All words have the same length.\n",
    "All words contain only lowercase alphabetic characters.\n",
    "You may assume no duplicates in the word list.\n",
    "You may assume beginWord and endWord are non-empty and are not the same.\n",
    "```\n",
    "Example 1:\n",
    "\n",
    "Input:\n",
    "beginWord = \"hit\",\n",
    "endWord = \"cog\",\n",
    "wordList = [\"hot\",\"dot\",\"dog\",\"lot\",\"log\",\"cog\"]\n",
    "\n",
    "Output:\n",
    "[\n",
    "  [\"hit\",\"hot\",\"dot\",\"dog\",\"cog\"],\n",
    "  [\"hit\",\"hot\",\"lot\",\"log\",\"cog\"]\n",
    "]\n",
    "Example 2:\n",
    "\n",
    "Input:\n",
    "beginWord = \"hit\"\n",
    "endWord = \"cog\"\n",
    "wordList = [\"hot\",\"dot\",\"dog\",\"lot\",\"log\"]\n",
    "\n",
    "Output: []\n",
    "\n",
    "Explanation: The endWord \"cog\" is not in wordList, therefore no possible transformation.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def findLadders(self, beginWord, endWord, wordList):\n",
    "\n",
    "        wordList = set(wordList)\n",
    "        res = []\n",
    "        layer = {}\n",
    "        layer[beginWord] = [[beginWord]]\n",
    "\n",
    "        while layer:\n",
    "            newlayer = collections.defaultdict(list)\n",
    "            for w in layer:\n",
    "                if w == endWord: \n",
    "                    res.extend(k for k in layer[w])\n",
    "                else:\n",
    "                    for i in range(len(w)):\n",
    "                        for c in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                            neww = w[:i]+c+w[i+1:]\n",
    "                            if neww in wordList:\n",
    "                                newlayer[neww]+=[j+[neww] for j in layer[w]]\n",
    "\n",
    "            wordList -= set(newlayer.keys())\n",
    "            layer = newlayer\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Shortest Distance from All Buildings\n",
    "Hard\n",
    "\n",
    "418\n",
    "\n",
    "21\n",
    "\n",
    "Favorite\n",
    "\n",
    "Share\n",
    "You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:\n",
    "\n",
    "Each 0 marks an empty land which you can pass by freely.\n",
    "Each 1 marks a building which you cannot pass through.\n",
    "Each 2 marks an obstacle which you cannot pass through.\n",
    "Example:\n",
    "\n",
    "Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]\n",
    "\n",
    "1 - 0 - 2 - 0 - 1\n",
    "|   |   |   |   |\n",
    "0 - 0 - 0 - 0 - 0\n",
    "|   |   |   |   |\n",
    "0 - 0 - 1 - 0 - 0\n",
    "\n",
    "Output: 7 \n",
    "\n",
    "Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2),\n",
    "             the point (1,2) is an ideal empty land to build a house, as the total \n",
    "             travel distance of 3+3+1=7 is minimal. So return 7.\n",
    "Note:\n",
    "There will be at least one building. If it is not possible to build such house according to the above rules, return -1.\n",
    "\n",
    "\n",
    "Use hit to record how many times a 0 grid has been reached and use distSum to record the sum of distance from all 1 grids to this 0 grid. A powerful pruning is that during the BFS we use count1 to count how many 1 grids we reached. If count1 < buildings then we know not all 1 grids are connected are we can return -1 immediately, which greatly improved speed (beat 100% submissions)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def shortestDistance(self, grid):\n",
    "    if not grid or not grid[0]: return -1\n",
    "    M, N, buildings = len(grid), len(grid[0]), sum(val for line in grid for val in line if val == 1)\n",
    "    hit, distSum = [[0] * N for i in range(M)], [[0] * N for i in range(M)]\n",
    "    \n",
    "    def BFS(start_x, start_y):\n",
    "        visited = [[False] * N for k in range(M)]\n",
    "        visited[start_x][start_y], count1, queue = True, 1, collections.deque([(start_x, start_y, 0)])\n",
    "        while queue:\n",
    "            x, y, dist = queue.popleft()\n",
    "            for i, j in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):\n",
    "                if 0 <= i < M and 0 <= j < N and not visited[i][j]:\n",
    "                    visited[i][j] = True\n",
    "                    if not grid[i][j]:\n",
    "                        queue.append((i, j, dist + 1))\n",
    "                        hit[i][j] += 1\n",
    "                        distSum[i][j] += dist + 1\n",
    "                    elif grid[i][j] == 1:\n",
    "                        count1 += 1\n",
    "        return count1 == buildings  \n",
    "    \n",
    "    for x in range(M):\n",
    "        for y in range(N):\n",
    "            if grid[x][y] == 1:\n",
    "                if not BFS(x, y): return -1\n",
    "    return min([distSum[i][j] for i in range(M) for j in range(N) if not grid[i][j] and hit[i][j] == buildings] or [-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Read N Characters Given Read4 II - Call multiple times\n",
    "\n",
    "Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be called multiple times.\n",
    "\n",
    " \n",
    "\n",
    "Method read4:\n",
    "\n",
    "The API read4 reads 4 consecutive characters from the file, then writes those characters into the buffer array buf.\n",
    "\n",
    "The return value is the number of actual characters read.\n",
    "\n",
    "Note that read4() has its own file pointer, much like FILE *fp in C.\n",
    "\n",
    "Definition of read4:\n",
    "\n",
    "    Parameter:  char[] buf\n",
    "    Returns:    int\n",
    "\n",
    "Note: buf[] is destination not source, the results from read4 will be copied to buf[]\n",
    "Below is a high level example of how read4 works:\n",
    "\n",
    "File file(\"abcdefghijk\"); // File is \"abcdefghijk\", initially file pointer (fp) points to 'a'\n",
    "char[] buf = new char[4]; // Create buffer with enough space to store characters\n",
    "read4(buf); // read4 returns 4. Now buf = \"abcd\", fp points to 'e'\n",
    "read4(buf); // read4 returns 4. Now buf = \"efgh\", fp points to 'i'\n",
    "read4(buf); // read4 returns 3. Now buf = \"ijk\", fp points to end of file\n",
    " \n",
    "\n",
    "Method read:\n",
    "\n",
    "By using the read4 method, implement the method read that reads n characters from the file and store it in the buffer array buf. Consider that you cannot manipulate the file directly.\n",
    "\n",
    "The return value is the number of actual characters read.\n",
    "\n",
    "Definition of read:\n",
    "\n",
    "    Parameters:\tchar[] buf, int n\n",
    "    Returns:\tint\n",
    "\n",
    "Note: buf[] is destination not source, you will need to write the results to buf[]\n",
    "\n",
    "```\n",
    "Example 1:\n",
    "\n",
    "File file(\"abc\");\n",
    "Solution sol;\n",
    "// Assume buf is allocated and guaranteed to have enough space for storing all characters from the file.\n",
    "sol.read(buf, 1); // After calling your read method, buf should contain \"a\". We read a total of 1 character from the file, so return 1.\n",
    "sol.read(buf, 2); // Now buf should contain \"bc\". We read a total of 2 characters from the file, so return 2.\n",
    "sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0.\n",
    "Example 2:\n",
    "\n",
    "File file(\"abc\");\n",
    "Solution sol;\n",
    "sol.read(buf, 4); // After calling your read method, buf should contain \"abc\". We read a total of 3 characters from the file, so return 3.\n",
    "sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0.\n",
    " \n",
    "\n",
    "Note:\n",
    "\n",
    "Consider that you cannot manipulate the file directly, the file is only accesible for read4 but not for read.\n",
    "The read function may be called multiple times.\n",
    "Please remember to RESET your class variables declared in Solution, as static/class variables are persisted across multiple test cases. Please see here for more details.\n",
    "You may assume the destination buffer array, buf, is guaranteed to have enough space for storing n characters.\n",
    "It is guaranteed that in a given test case the same buffer buf is called by read.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "# @param buf, Destination buffer (a list of characters)\n",
    "# @param n,   Maximum number of characters to read (an integer)\n",
    "# @return     The number of characters read (an integer)\n",
    "    def __init__(self):\n",
    "        self.queue = []\n",
    "\n",
    "    def read(self, buf, n):\n",
    "        idx = 0\n",
    "        while True:\n",
    "            buf4 = [\"\"]*4\n",
    "            l = read4(buf4)\n",
    "            self.queue.extend(buf4[:k]) # 这里好像不加k也可以？\n",
    "            curr = min(len(self.queue), n-idx)\n",
    "            for i in range(curr):\n",
    "                buf[idx] = self.queue.pop(0)\n",
    "                idx+=1\n",
    "            if curr == 0:\n",
    "                break \n",
    "        return idx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Longest Substring with At Most K Distinct Characters\n",
    "Hard\n",
    "Given a string, find the length of the longest substring T that contains at most k distinct characters.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: s = \"eceba\", k = 2\n",
    "Output: 3\n",
    "Explanation: T is \"ece\" which its length is 3.\n",
    "Example 2:\n",
    "\n",
    "Input: s = \"aa\", k = 1\n",
    "Output: 2\n",
    "Explanation: T is \"aa\" which its length is 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    \n",
    "    \"\"\"\n",
    "    The general idea is to iterate over string s.\n",
    "    Always put the character c and its location i in the dictionary d.\n",
    "    1) If the sliding window contains less than or equal to k distinct characters, simply record the return value, and move on.\n",
    "    2) Otherwise, we need to remove a character from the sliding window.\n",
    "       Here's how to find the character to be removed:\n",
    "       Because the values in d represents the rightmost location of each character in the sliding window, in order to find the longest substring T, we need to locate the smallest location, and remove it from the dictionary, and then record the return value.\n",
    "    \"\"\"\n",
    "    def lengthOfLongestSubstringKDistinct(self, s, k):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # Use dictionary d to keep track of (character, location) pair,\n",
    "        # where location is the rightmost location that the character appears at\n",
    "        d = {}\n",
    "        low, ret = 0, 0\n",
    "        for i, c in enumerate(s):\n",
    "            d[c] = i\n",
    "            if len(d) > k:\n",
    "                low = min(d.values())\n",
    "                del d[s[low]]\n",
    "                low += 1\n",
    "            ret = max(i - low + 1, ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Merge k Sorted Lists\n",
    "Hard\n",
    "Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.\n",
    "\n",
    "Example:\n",
    "\n",
    "Input:\n",
    "[\n",
    "  1->4->5,\n",
    "  1->3->4,\n",
    "  2->6\n",
    "]\n",
    "\n",
    "Output: 1->1->2->3->4->4->5->6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq\n",
    "# overwrite the compare function \n",
    "# so that we can directly put ListNode into heapq\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode(object):\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "ListNode.__lt__ = lambda x, y: (x.val < y.val)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param lists: a list of ListNode\n",
    "    @return: The head of one sorted list.\n",
    "    \"\"\"\n",
    "    def mergeKLists(self, lists):\n",
    "        if not lists:\n",
    "            return None\n",
    "        \n",
    "        dummy = ListNode(0)\n",
    "        tail = dummy\n",
    "        heap = []\n",
    "        for head in lists:\n",
    "            if head:\n",
    "                heapq.heappush(heap, head)\n",
    "                \n",
    "        while heap:\n",
    "            head = heapq.heappop(heap)\n",
    "            tail.next = head\n",
    "            tail = head\n",
    "            if hexad.next:\n",
    "                heapq.heappush(heap, head.next)\n",
    "                    \n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Valid Number\n",
    "Validate if a given string can be interpreted as a decimal number.\n",
    "```\n",
    "Some examples:\n",
    "\"0\" => true\n",
    "\" 0.1 \" => true\n",
    "\"abc\" => false\n",
    "\"1 a\" => false\n",
    "\"2e10\" => true\n",
    "\" -90e3   \" => true\n",
    "\" 1e\" => false\n",
    "\"e3\" => false\n",
    "\" 6e-1\" => true\n",
    "\" 99e2.5 \" => false\n",
    "\"53.5e93\" => true\n",
    "\" --6 \" => false\n",
    "\"-+3\" => false\n",
    "\"95a54e53\" => false\n",
    "\n",
    "Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one. However, here is a list of characters that can be in a valid decimal number:\n",
    "\n",
    "Numbers 0-9\n",
    "Exponent - \"e\"\n",
    "Positive/negative sign - \"+\"/\"-\"\n",
    "Decimal point - \".\"\n",
    "Of course, the context of these characters also matters in the input.\n",
    "\n",
    "Update (2015-02-10):\n",
    "The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isNumber(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        #define a DFA\n",
    "        state = [{}, \n",
    "              {'blank': 1, 'sign': 2, 'digit':3, '.':4}, \n",
    "              {'digit':3, '.':4},\n",
    "              {'digit':3, '.':5, 'e':6, 'blank':9},\n",
    "              {'digit':5},\n",
    "              {'digit':5, 'e':6, 'blank':9},\n",
    "              {'sign':7, 'digit':8},\n",
    "              {'digit':8},\n",
    "              {'digit':8, 'blank':9},\n",
    "              {'blank':9}]\n",
    "        currentState = 1\n",
    "        for c in s:\n",
    "            if c >= '0' and c <= '9':\n",
    "                c = 'digit'\n",
    "            if c == ' ':\n",
    "                c = 'blank'\n",
    "            if c in ['+', '-']:\n",
    "                c = 'sign'\n",
    "            if c not in state[currentState].keys():\n",
    "                return False\n",
    "            currentState = state[currentState][c]\n",
    "        if currentState not in [3,5,8,9]:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Find the Closest Palindrome\n",
    "Hard\n",
    "\n",
    "143\n",
    "\n",
    "574\n",
    "\n",
    "Favorite\n",
    "\n",
    "Share\n",
    "Given an integer n, find the closest integer (not including itself), which is a palindrome.\n",
    "\n",
    "The 'closest' is defined as absolute difference minimized between two integers.\n",
    "\n",
    "Example 1:\n",
    "Input: \"123\"\n",
    "Output: \"121\"\n",
    "Note:\n",
    "The input n is a positive integer represented by string, whose length will not exceed 18.\n",
    "If there is a tie, return the smaller one as answer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def nearestPalindromic(self, n) -> str:\n",
    "        len_n = (len(n))\n",
    "        isOdd = len_n % 2#判断数字是奇数位还是偶数位\n",
    "        int_n = int(n[:len_n // 2 + isOdd])\n",
    "        '''\n",
    "        回文数是有范围的，比如说n为三位数，那么其最近回文数的范围在[99, 1001]之间\n",
    "        '''\n",
    "        max_Palindromic = str (10**len_n + 1)\n",
    "        min_Palindromic = str(10**(len_n-1)-1)\n",
    "        if abs(int(min_Palindromic)-int(n))>abs(int(max_Palindromic)-int(n)):\n",
    "            nearestPalindromic=max_Palindromic\n",
    "        else:\n",
    "            nearestPalindromic=min_Palindromic\n",
    "        '''\n",
    "        是回文数需要改变中间的那个数字，要么增加1，要么减小1，比如121，可以变成111和131。\n",
    "        另一种情况是原数不是回文数，我们只需要改变右半边就行了，比如123，变成121。\n",
    "        那么其实这三种情况可以总结起来，分别相当于对中间的2进行了-1, +1, +0\n",
    "        '''\n",
    "        for i in [-1,0, 1]:\n",
    "            nearestPalindromic_i=list(str(int_n+i))\n",
    "            tmp=list(str(int_n+i))\n",
    "            tmp.reverse()\n",
    "            if isOdd==1:\n",
    "                 del tmp[0]\n",
    "            nearestPalindromic_i.extend(tmp)\n",
    "            if ''.join(nearestPalindromic_i)==n:#除去自身\n",
    "                continue\n",
    "            if abs(int(nearestPalindromic)-int(n))>abs(int(''.join(nearestPalindromic_i))-int(n)):\n",
    "                nearestPalindromic=''.join(nearestPalindromic_i)\n",
    "        return nearestPalindromic\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Text Justification\n",
    "Hard\n",
    "Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.\n",
    "\n",
    "You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.\n",
    "\n",
    "Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.\n",
    "\n",
    "For the last line of text, it should be left justified and no extra space is inserted between words.\n",
    "\n",
    "```\n",
    "Note:\n",
    "\n",
    "A word is defined as a character sequence consisting of non-space characters only.\n",
    "Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.\n",
    "The input array words contains at least one word.\n",
    "Example 1:\n",
    "\n",
    "Input:\n",
    "words = [\"This\", \"is\", \"an\", \"example\", \"of\", \"text\", \"justification.\"]\n",
    "maxWidth = 16\n",
    "Output:\n",
    "[\n",
    "   \"This    is    an\",\n",
    "   \"example  of text\",\n",
    "   \"justification.  \"\n",
    "]\n",
    "Example 2:\n",
    "\n",
    "Input:\n",
    "words = [\"What\",\"must\",\"be\",\"acknowledgment\",\"shall\",\"be\"]\n",
    "maxWidth = 16\n",
    "Output:\n",
    "[\n",
    "  \"What   must   be\",\n",
    "  \"acknowledgment  \",\n",
    "  \"shall be        \"\n",
    "]\n",
    "Explanation: Note that the last line is \"shall be    \" instead of \"shall     be\",\n",
    "             because the last line must be left-justified instead of fully-justified.\n",
    "             Note that the second line is also left-justified becase it contains only one word.\n",
    "Example 3:\n",
    "\n",
    "Input:\n",
    "words = [\"Science\",\"is\",\"what\",\"we\",\"understand\",\"well\",\"enough\",\"to\",\"explain\",\n",
    "         \"to\",\"a\",\"computer.\",\"Art\",\"is\",\"everything\",\"else\",\"we\",\"do\"]\n",
    "maxWidth = 20\n",
    "Output:\n",
    "[\n",
    "  \"Science  is  what we\",\n",
    "  \"understand      well\",\n",
    "  \"enough to explain to\",\n",
    "  \"a  computer.  Art is\",\n",
    "  \"everything  else  we\",\n",
    "  \"do                  \"\n",
    "]\n",
    "```\n",
    "How does it work? Well in the question statement, the sentence \"Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right\" was just a really long and awkward way to say round robin. The following line implements the round robin logic:\n",
    "\n",
    "```\n",
    "for i in range(maxWidth - num_of_letters):\n",
    "                cur[i%(len(cur)-1 or 1)] += ' '\n",
    "```\n",
    "What does this line do? Once you determine that there are only k words that can fit on a given line, you know what the total length of those words is num_of_letters. Then the rest are spaces, and there are (maxWidth - num_of_letters) of spaces. The \"or 1\" part is for dealing with the edge case len(cur) == 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fullJustify(self, words, maxWidth):\n",
    "    res, cur, num_of_letters = [], [], 0\n",
    "    for w in words:\n",
    "        if num_of_letters + len(w) + len(cur) > maxWidth:\n",
    "            for i in range(maxWidth - num_of_letters):\n",
    "                cur[i%(len(cur)-1 or 1)] += ' '\n",
    "            res.append(''.join(cur))\n",
    "            cur, num_of_letters = [], 0\n",
    "        cur += [w]\n",
    "        num_of_letters += len(w)\n",
    "    return res + [' '.join(cur).ljust(maxWidth)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Regular Expression Matching\n",
    "\n",
    "```\n",
    "Given an input string (s) and a pattern (p), \n",
    "implement regular expression matching with support for '.' and '*'.\n",
    "\n",
    "'.' Matches any single character.\n",
    "'*' Matches zero or more of the preceding element.\n",
    "The matching should cover the entire input string (not partial).\n",
    "\n",
    "Note:\n",
    "\n",
    "s could be empty and contains only lowercase letters a-z.\n",
    "p could be empty and contains only lowercase letters a-z, and characters like . or *.\n",
    "Example 1:\n",
    "\n",
    "Input:\n",
    "s = \"aa\"\n",
    "p = \"a\"\n",
    "Output: false\n",
    "Explanation: \"a\" does not match the entire string \"aa\".\n",
    "Example 2:\n",
    "\n",
    "Input:\n",
    "s = \"aa\"\n",
    "p = \"a*\"\n",
    "Output: true\n",
    "Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes \"aa\".\n",
    "Example 3:\n",
    "\n",
    "Input:\n",
    "s = \"ab\"\n",
    "p = \".*\"\n",
    "Output: true\n",
    "Explanation: \".*\" means \"zero or more (*) of any character (.)\".\n",
    "Example 4:\n",
    "\n",
    "Input:\n",
    "s = \"aab\"\n",
    "p = \"c*a*b\"\n",
    "Output: true\n",
    "Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches \"aab\".\n",
    "Example 5:\n",
    "\n",
    "Input:\n",
    "s = \"mississippi\"\n",
    "p = \"mis*is*p*.\"\n",
    "Output: false\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isMatch1(self, s, p):\n",
    "        if not p:\n",
    "            return not s\n",
    "\n",
    "        first_match = bool(s) and p[0] in {s[0], '.'}\n",
    "\n",
    "        if len(p) >= 2 and p[1] == '*':\n",
    "            return self.isMatch(s, p[2:]) or first_match and self.isMatch(s[1:], p)\n",
    "        else:\n",
    "            return first_match and self.isMatch(s[1:], p[1:])\n",
    "\n",
    "    def isMatch(self, s, p):\n",
    "        # f: s[i:] and p[j:] match?\n",
    "        f = [[False for j in range(len(p)+1)]\n",
    "                    for i in range(len(s)+1)]\n",
    "\n",
    "        f[-1][-1] = True\n",
    "        for i in range(len(s), -1, -1):\n",
    "            for j in range(len(p)-1, -1, -1):\n",
    "                first_match = i < len(s) and p[j] in {s[i], '.'}\n",
    "                if j + 1 < len(p) and p[j+1] == '*':\n",
    "                    f[i][j] = f[i][j+2] or first_match and f[i+1][j]\n",
    "                else:\n",
    "                    f[i][j] = first_match and f[i+1][j+1]\n",
    "\n",
    "        return f[0][0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Word Break II \n",
    "\n",
    "```\n",
    "Example\n",
    "Given a String CatMat\n",
    "Given a dictionary [\"Cat\", \"Mat\", \"Ca\", \"tM\", \"at\", \"C\", \"Dog\", \"og\", \"Do\"]\n",
    "return 3\n",
    "\n",
    "we can form 3 sentences, as follows:\n",
    "CatMat = Cat Mat\n",
    "CatMat = Ca tM at\n",
    "CatMat = C at Mat\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param: : A string\n",
    "    @param: : A set of word\n",
    "    @return: the number of possible sentences.\n",
    "    \"\"\"\n",
    "\n",
    "    def wordBreak3_dfs(self, S, word_dict):\n",
    "        \n",
    "        self.count = 0\n",
    "        S = S.lower()\n",
    "        word_dict = set([word.lower() for word in word_dict])\n",
    "\n",
    "        def dfs(start_index, tmp):\n",
    "            if start_index == len(S):\n",
    "                self.count += 1\n",
    "\n",
    "            for i in range(start_index, len(S)):\n",
    "                if S[start_index:i+1] in word_dict:\n",
    "                    dfs(i+1, tmp +[S[start_index:i+1]])\n",
    "        \n",
    "        dfs(0, [])\n",
    "        return self.count\n",
    "    \n",
    "    def wordBreak3_dp(self, S, word_dict):\n",
    "        if len(S) == 0 or len(word_dict) == 0:\n",
    "            return 0\n",
    "        \n",
    "        dict_lower = set()\n",
    "        for word in word_dict:\n",
    "            dict_lower.add(word.lower())\n",
    "        \n",
    "        n = len(S)\n",
    "        maxLength = max([len(w) for w in word_dict])\n",
    "        \n",
    "        # define f[i]: number of sentences that S[:i] can be breaked into\n",
    "        f = [0 for _ in range(n + 1)]\n",
    "        \n",
    "        # init\n",
    "        f[0] = 1\n",
    "        \n",
    "        # function\n",
    "        for i in range(1, n + 1):\n",
    "            start_index = max(0, i - maxLength)\n",
    "            for j in range(start_index, i):\n",
    "                if f[j] and S[j:i].lower() in dict_lower:\n",
    "                    f[i] += f[j] # 这里也可以用f[i-j] 不过相应就变成S[i-j:i]\n",
    "        \n",
    "        # ans\n",
    "        return f[n]\n",
    "    \n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    print(s.wordBreak3_dp(S = \"Catmat\", \n",
    "                          word_dict = [\"Cat\",\"mat\",\"ca\",\"tm\",\"at\",\"C\",\"Dog\",\"og\",\"Do\"]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Maxium of 3 non-overlapping array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def maxSumOfThreeSubarrays(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "\n",
    "        # Best single, double, and triple sequence found so far\n",
    "        bestSeq = 0\n",
    "        bestTwoSeq = [0, k]\n",
    "        bestThreeSeq = [0, k, k*2]\n",
    "\n",
    "        # Sums of each window\n",
    "        seqSum = sum(nums[0:k])\n",
    "        seqTwoSum = sum(nums[k:k*2])\n",
    "        seqThreeSum = sum(nums[k*2:k*3])\n",
    "\n",
    "        # Sums of combined best windows\n",
    "        bestSeqSum = seqSum\n",
    "        bestTwoSum = seqSum + seqTwoSum\n",
    "        bestThreeSum = seqSum + seqTwoSum + seqThreeSum\n",
    "\n",
    "        # Current window positions\n",
    "        seqIndex = 1\n",
    "        twoSeqIndex = k + 1\n",
    "        threeSeqIndex = k*2 + 1\n",
    "        while threeSeqIndex <= len(nums) - k:\n",
    "            # Update the three sliding windows\n",
    "            seqSum = seqSum - nums[seqIndex - 1] + nums[seqIndex + k - 1]\n",
    "            seqTwoSum = seqTwoSum - nums[twoSeqIndex - 1] + nums[twoSeqIndex + k - 1]\n",
    "            seqThreeSum = seqThreeSum - nums[threeSeqIndex - 1] + nums[threeSeqIndex + k - 1]\n",
    "            \n",
    "            # Update best single window\n",
    "            if seqSum > bestSeqSum:\n",
    "                bestSeq = seqIndex\n",
    "                bestSeqSum = seqSum\n",
    "\n",
    "            # Update best two windows\n",
    "            if seqTwoSum + bestSeqSum > bestTwoSum:\n",
    "                bestTwoSeq = [bestSeq, twoSeqIndex]\n",
    "                bestTwoSum = seqTwoSum + bestSeqSum\n",
    "\n",
    "            # Update best three windows\n",
    "            if seqThreeSum + bestTwoSum > bestThreeSum:\n",
    "                bestThreeSeq = bestTwoSeq + [threeSeqIndex]\n",
    "                bestThreeSum = seqThreeSum + bestTwoSum\n",
    "\n",
    "            # Update the current positions\n",
    "            seqIndex += 1\n",
    "            twoSeqIndex += 1\n",
    "            threeSeqIndex += 1\n",
    "\n",
    "        return bestThreeSeq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Find Median from Data Stream"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from heapq import *\n",
    "\n",
    "class MedianFinder:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.heaps = None, [], []\n",
    "        self.i = 1\n",
    "\n",
    "    def addNum(self, num):\n",
    "        heappush(self.heaps[-self.i], -heappushpop(self.heaps[self.i], num * self.i))\n",
    "        self.i *= -1\n",
    "\n",
    "    def findMedian(self):\n",
    "        return (self.heaps[self.i][0] * self.i - self.heaps[-1][0]) / 2.0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sliding Window Maxium"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxSlidingWindow(self, nums, k):\n",
    "    d = collections.deque()\n",
    "    out = []\n",
    "    for i, n in enumerate(nums):\n",
    "        while d and nums[d[-1]] < n:\n",
    "            d.pop()\n",
    "        d += i,\n",
    "        if d[0] == i - k:\n",
    "            d.popleft()\n",
    "        if i >= k - 1:\n",
    "            out += nums[d[0]],\n",
    "    return out"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sliding Window Median\n",
    "\n",
    "使用九章算法强化班中讲到的 HashHeap。即一个 Hash + Heap。\n",
    "Hash 的 key 是 Heap 里的每个元素，值是这个元素在 Heap 中的下标。\n",
    "\n",
    "要做这个题首先需要先做一下 Data Stream Median。这个题是只在一个集合中增加数，不删除数，然后不断的求中点。\n",
    "Sliding Window Median，就是不断的增加数，删除数，然后求中点。比 Data Stream Median 难的地方就在于如何支持删除数。\n",
    "\n",
    "因为 Data Stream Median 的方法是用 两个 Heap，一个 max heap，一个min heap。所以删除的话，就需要让 heap 也支持删除操作。\n",
    "由于 Python 的 heapq 并不支持 logn 时间内的删除操作，因此只能自己实现一个 hash + heap 的方法。\n",
    "\n",
    "总体时间复杂度 O(nlogk)O(nlogk)，n是元素个数，k 是 window 的大小。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def medianSlidingWindow1(self, nums, k):\n",
    "    window = sorted(nums[:k])\n",
    "    medians = []\n",
    "    for a, b in zip(nums, nums[k:] + [0]):\n",
    "        medians.append((window[k//2] + window[~(k//2)]) / 2.)\n",
    "        window.remove(a)\n",
    "        bisect.insort(window, b)\n",
    "    return medians\n",
    "\n",
    "def medianSlidingWindow(self, nums, k):\n",
    "    small, large, ans = [], [], []\n",
    "    for i, n in enumerate(nums[:k]): \n",
    "        heapq.heappush(small, (-n,i))\n",
    "    for _ in range(k-(k>>1)): \n",
    "        self.move(small, large)\n",
    "    ans = [large[0][0] * 1. if k & 1 else (large[0][0]-small[0][0]) / 2.]\n",
    "    for i, n in enumerate(nums[k:]):\n",
    "        if n >= large[0][0]:\n",
    "            heapq.heappush(large, (n, i+k))\n",
    "            if nums[i] <= large[0][0]: self.move(large, small)\n",
    "        else:\n",
    "            heapq.heappush(small, (-n, i+k))\n",
    "            if nums[i] >= large[0][0]: self.move(small, large)\n",
    "        while small and small[0][1] <= i: heapq.heappop(small)\n",
    "        while large and large[0][1] <= i: heapq.heappop(large)\n",
    "        ans.append(large[0][0] * 1. if k & 1 else (large[0][0]-small[0][0]) / 2.)\n",
    "    return ans\n",
    "\n",
    "def move(self, h1, h2):\n",
    "    x, i = heapq.heappop(h1)\n",
    "    heapq.heappush(h2, (-x, i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Edit Distance\n",
    "\n",
    "\n",
    "Thought process:\n",
    "Given two strings, we're tasked with finding the minimum number of transformations we need to make to arrive with equivalent strings. From the get-go, there doesn't seem to be any way around trying all possibilities, and in this, possibilities refers to inserting, deleting, or replacing a character. Recursion is usually a good choice for trying all possilbilities.\n",
    "\n",
    "Whenever we write recursive functions, we'll need some way to terminate, or else we'll end up overflowing the stack via infinite recursion. With strings, the natural state to keep track of is the index. We'll need two indexes, one for word1 and one for word2. Now we just need to handle our base cases, and recursive cases.\n",
    "What happens when we're done with either word? Some thought will tell you that the minimum number of transformations is simply to insert the rest of the other word. This is our base case. What about when we're not done with either string? We'll either match the currently indexed characters in both strings, or mismatch. In the first case, we don't incur any penalty, and we can continue to compare the rest of the strings by recursing on the rest of both strings. In the case of a mismatch, we either insert, delete, or replace. To recap:\n",
    "\n",
    "base case: word1 = \"\" or word2 = \"\" => return length of other string\n",
    "recursive case: word1[0] == word2[0] => recurse on word1[1:] and word2[1:]\n",
    "recursive case: word1[0] != word2[0] => recurse by inserting, deleting, or replacing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# dfs\n",
    "def minDistance(self, word1, word2):\n",
    "        \"\"\"Naive recursive solution\"\"\"\n",
    "        if not word1 and not word2:\n",
    "            return 0\n",
    "        if not word1:\n",
    "            return len(word2)\n",
    "        if not word2:\n",
    "            return len(word1)\n",
    "        if word1[0] == word2[0]:\n",
    "            return self.minDistance(word1[1:], word2[1:])\n",
    "        insert = 1 + self.minDistance(word1, word2[1:])\n",
    "        delete = 1 + self.minDistance(word1[1:], word2)\n",
    "        replace = 1 + self.minDistance(word1[1:], word2[1:])\n",
    "        return min(insert, replace, delete)\n",
    "\n",
    "# O(m*n) space\n",
    "def minDistance1(self, word1, word2):\n",
    "    l1, l2 = len(word1)+1, len(word2)+1\n",
    "    dp = [[0 for _ in xrange(l2)] for _ in xrange(l1)]\n",
    "    for i in xrange(l1):\n",
    "        dp[i][0] = i\n",
    "    for j in xrange(l2):\n",
    "        dp[0][j] = j\n",
    "    for i in xrange(1, l1):\n",
    "        for j in xrange(1, l2):\n",
    "            dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+(word1[i-1]!=word2[j-1]))\n",
    "    return dp[-1][-1]\n",
    "\n",
    "# O(n) space with rolling array            \n",
    "def minDistance(self, word1, word2):\n",
    "    l1, l2 = len(word1)+1, len(word2)+1\n",
    "    pre = [0 for _ in xrange(l2)]\n",
    "    for j in xrange(l2):\n",
    "        pre[j] = j\n",
    "    for i in xrange(1, l1):\n",
    "        cur = [i]*l2\n",
    "        for j in xrange(1, l2):\n",
    "            cur[j] = min(cur[j-1]+1, pre[j]+1, pre[j-1]+(word1[i-1]!=word2[j-1]))\n",
    "        pre = cur[:]\n",
    "    return pre[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sudoku Solver\n",
    "\n",
    "Write a program to solve a Sudoku puzzle by filling the empty cells.\n",
    "\n",
    "A sudoku solution must satisfy all of the following rules:\n",
    "\n",
    "Each of the digits 1-9 must occur exactly once in each row.\n",
    "Each of the digits 1-9 must occur exactly once in each column.\n",
    "Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.\n",
    "Empty cells are indicated by the character '.'.\n",
    "\n",
    "![](https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png)\n",
    "\n",
    "A sudoku puzzle...\n",
    "\n",
    "![](https://upload.wikimedia.org/wikipedia/commons/thumb/3/31/Sudoku-by-L2G-20050714_solution.svg/250px-Sudoku-by-L2G-20050714_solution.svg.png)\n",
    "...and its solution numbers marked in red.\n",
    "\n",
    "Note:\n",
    "\n",
    "The given board contain only digits 1-9 and the character '.'.\n",
    "You may assume that the given Sudoku puzzle will have a single unique solution.\n",
    "The given board size is always 9x9.\n",
    "\n",
    "Solution:\n",
    "\n",
    "It's similar to how human solve Sudoku. \n",
    "\n",
    "create a hash table (dictionary) val to store possible values in every location.\n",
    "Each time, start from the location with fewest possible values, choose one value from it and then update the board and possible values at other locations. If this update is valid, keep solving (DFS). If this update is invalid (leaving zero possible values at some locations) or this value doesn't lead to the solution, undo the updates and then choose the next value. \n",
    "Since we calculated val at the beginning and start filling the board from the location with fewest possible values, the amount of calculation and thus the runtime can be significantly reduced: \n",
    "\n",
    "\n",
    "The run time is 48-68 ms on LeetCode OJ, which seems to be among the fastest python solutions here.\n",
    "\n",
    "\n",
    "The PossibleVals function may be further simplified/optimized, but it works just fine for now. (it would look less lengthy if we are allowed to use numpy array for the board lol). \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solveSudoku(self, board):\n",
    "    self.board = board\n",
    "    self.val = self.PossibleVals()\n",
    "    self.Solver()\n",
    "\n",
    "def PossibleVals(self):\n",
    "    a = \"123456789\"\n",
    "    d, val = {}, {}\n",
    "    for i in xrange(9):\n",
    "        for j in xrange(9):\n",
    "            ele = self.board[i][j]\n",
    "            if ele != \".\":\n",
    "                d[(\"r\", i)] = d.get((\"r\", i), []) + [ele]\n",
    "                d[(\"c\", j)] = d.get((\"c\", j), []) + [ele]\n",
    "                d[(i//3, j//3)] = d.get((i//3, j//3), []) + [ele]\n",
    "            else:\n",
    "                val[(i,j)] = []\n",
    "    for (i,j) in val.keys():\n",
    "        inval = d.get((\"r\",i),[])+d.get((\"c\",j),[])+d.get((i/3,j/3),[])\n",
    "        val[(i,j)] = [n for n in a if n not in inval ]\n",
    "    return val\n",
    "\n",
    "def Solver(self):\n",
    "    if len(self.val)==0:\n",
    "        return True\n",
    "    kee = min(self.val.keys(), key=lambda x: len(self.val[x]))\n",
    "    nums = self.val[kee]\n",
    "    for n in nums:\n",
    "        update = {kee:self.val[kee]}\n",
    "        if self.ValidOne(n, kee, update): # valid choice\n",
    "            if self.Solver(): # keep solving\n",
    "                return True\n",
    "        self.undo(kee, update) # invalid choice or didn't solve it => undo\n",
    "    return False\n",
    "    \n",
    "def ValidOne(self, n, kee, update):\n",
    "    self.board[kee[0]][kee[1]] = n\n",
    "    del self.val[kee]\n",
    "    i, j = kee\n",
    "    for ind in self.val.keys():\n",
    "        if n in self.val[ind]:\n",
    "            if ind[0]==i or ind[1]==j or (ind[0]/3,ind[1]/3)==(i/3,j/3):\n",
    "                update[ind] = n\n",
    "                self.val[ind].remove(n)\n",
    "                if len(self.val[ind])==0:\n",
    "                    return False\n",
    "    return True\n",
    "\n",
    "def undo(self, kee, update):\n",
    "    self.board[kee[0]][kee[1]]=\".\"\n",
    "    for k in update:            \n",
    "        if k not in self.val:\n",
    "            self.val[k]= update[k]\n",
    "        else:\n",
    "            self.val[k].append(update[k])\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Decode Ways II\n",
    "\n",
    "A message containing letters from A-Z is being encoded to numbers using the following mapping way:\n",
    "```\n",
    "'A' -> 1\n",
    "'B' -> 2\n",
    "...\n",
    "'Z' -> 26\n",
    "Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.\n",
    "\n",
    "Given the encoded message containing digits and the character '*', return the total number of ways to decode it.\n",
    "\n",
    "Also, since the answer may be very large, you should return the output mod 109 + 7.\n",
    "\n",
    "Example 1:\n",
    "Input: \"*\"\n",
    "Output: 9\n",
    "Explanation: The encoded message can be decoded to the string: \"A\", \"B\", \"C\", \"D\", \"E\", \"F\", \"G\", \"H\", \"I\".\n",
    "Example 2:\n",
    "Input: \"1*\"\n",
    "Output: 9 + 9 = 18\n",
    "Note:\n",
    "The length of the input string will fit in range [1, 105].\n",
    "The input string will only contain the character '*' and digits '0' - '9'.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def numDecodings(self, S):\n",
    "        MOD = 10**9 + 7\n",
    "        e0, e1, e2 = 1, 0, 0\n",
    "        for c in S:\n",
    "            if c == '*':\n",
    "                f0 = 9*e0 + 9*e1 + 6*e2\n",
    "                f1 = e0\n",
    "                f2 = e0\n",
    "            else:\n",
    "                f0 = (c > '0') * e0 + e1 + (c < = '6') * e2\n",
    "                f1 = (c == '1') * e0\n",
    "                f2 = (c == '2') * e0\n",
    "            e0, e1, e2 = f0 % MOD, f1, f2\n",
    "        return e0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Range Sum Query 2D - Mutable\n",
    "```\n",
    "Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).\n",
    "```\n",
    "![](https://leetcode.com/static/images/courses/range_sum_query_2d.png)\n",
    "```\n",
    "Range Sum Query 2D\n",
    "The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.\n",
    "\n",
    "Example:\n",
    "Given matrix = [\n",
    "  [3, 0, 1, 4, 2],\n",
    "  [5, 6, 3, 2, 1],\n",
    "  [1, 2, 0, 1, 5],\n",
    "  [4, 1, 0, 1, 7],\n",
    "  [1, 0, 3, 0, 5]\n",
    "]\n",
    "\n",
    "sumRegion(2, 1, 4, 3) -> 8\n",
    "update(3, 2, 2)\n",
    "sumRegion(2, 1, 4, 3) -> 10\n",
    "Note:\n",
    "The matrix is only modifiable by the update function.\n",
    "You may assume the number of calls to update and sumRegion function is distributed evenly.\n",
    "You may assume that row1 ≤ row2 and col1 ≤ col2.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class NumMatrix(object):\n",
    "    def __init__(self, matrix):\n",
    "        \"\"\"\n",
    "        initialize your data structure here.\n",
    "        :type matrix: List[List[int]]\n",
    "        \"\"\"\n",
    "        for row in matrix:\n",
    "            for col in xrange(1, len(row)):\n",
    "                row[col] += row[col-1]\n",
    "        self.matrix = matrix\n",
    "        \n",
    "\n",
    "    def update(self, row, col, val):\n",
    "        \"\"\"\n",
    "        update the element at matrix[row,col] to val.\n",
    "        :type row: int\n",
    "        :type col: int\n",
    "        :type val: int\n",
    "        :rtype: void\n",
    "        \"\"\"\n",
    "        original = self.matrix[row][col]\n",
    "        if col != 0:\n",
    "            original -= self.matrix[row][col-1]\n",
    "            \n",
    "        diff = original - val\n",
    "        \n",
    "        for y in xrange(col, len(self.matrix[0])):\n",
    "            self.matrix[row][y] -= diff\n",
    "\n",
    "    def sumRegion(self, row1, col1, row2, col2):\n",
    "        \"\"\"\n",
    "        sum of elements matrix[(row1,col1)..(row2,col2)], inclusive.\n",
    "        :type row1: int\n",
    "        :type col1: int\n",
    "        :type row2: int\n",
    "        :type col2: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        sum = 0\n",
    "        for x in xrange(row1, row2+1):\n",
    "            sum += self.matrix[x][col2]\n",
    "            if col1 != 0:\n",
    "                sum -= self.matrix[x][col1-1]\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class NumMatrix(object):\n",
    "    def __init__(self, matrix):\n",
    "        if not matrix:\n",
    "            return\n",
    "        self.m, self.n = len(matrix), len(matrix[0])\n",
    "        self.matrix, self.bit = [[0]*(self.n) for _ in range(self.m)], [[0]*(self.n+1) for _ in range(self.m+1)]\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                self.update(i, j, matrix[i][j])\n",
    "\n",
    "    def update(self, row, col, val):\n",
    "        diff, self.matrix[row][col], i = val-self.matrix[row][col], val, row+1\n",
    "        while i <= self.m:\n",
    "            j = col+1\n",
    "            while j <= self.n:\n",
    "                self.bit[i][j] += diff\n",
    "                j += (j & -j)\n",
    "            i += (i & -i)\n",
    "\n",
    "    def sumRegion(self, row1, col1, row2, col2):\n",
    "        return self.sumCorner(row2, col2) + self.sumCorner(row1-1, col1-1) - self.sumCorner(row1-1, col2) - self.sumCorner(row2, col1-1)\n",
    "\n",
    "    def sumCorner(self, row, col):\n",
    "        res, i = 0, row+1\n",
    "        while i:\n",
    "            j = col+1\n",
    "            while j:\n",
    "                res += self.bit[i][j]\n",
    "                j -= (j & -j)\n",
    "            i -= (i & -i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Insert Delete GetRandom O(1) - Duplicates allowed\n",
    "\n",
    "Design a data structure that supports all following operations in average O(1) time.\n",
    "\n",
    "Note: Duplicate elements are allowed.\n",
    "insert(val): Inserts an item val to the collection.\n",
    "remove(val): Removes an item val from the collection if present.\n",
    "getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.\n",
    "```\n",
    "Example:\n",
    "\n",
    "// Init an empty collection.\n",
    "RandomizedCollection collection = new RandomizedCollection();\n",
    "\n",
    "// Inserts 1 to the collection. Returns true as the collection did not contain 1.\n",
    "collection.insert(1);\n",
    "\n",
    "// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].\n",
    "collection.insert(1);\n",
    "\n",
    "// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].\n",
    "collection.insert(2);\n",
    "\n",
    "// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.\n",
    "collection.getRandom();\n",
    "\n",
    "// Removes 1 from the collection, returns true. Collection now contains [1,2].\n",
    "collection.remove(1);\n",
    "\n",
    "// getRandom should return 1 and 2 both equally likely.\n",
    "collection.getRandom();\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "class RandomizedCollection(object):\n",
    "\n",
    "    def __init__(self):\n",
    "        self.vals, self.idxs = [], collections.defaultdict(set)\n",
    "        \n",
    "\n",
    "    def insert(self, val):\n",
    "        self.vals.append(val)\n",
    "        self.idxs[val].add(len(self.vals) - 1)\n",
    "        return len(self.idxs[val]) == 1\n",
    "        \n",
    "\n",
    "    def remove(self, val):\n",
    "        if self.idxs[val]:\n",
    "            out, ins = self.idxs[val].pop(), self.vals[-1]\n",
    "            self.vals[out] = ins\n",
    "            if self.idxs[ins]:\n",
    "                self.idxs[ins].add(out)\n",
    "                self.idxs[ins].discard(len(self.vals) - 1)\n",
    "            self.vals.pop()\n",
    "            return True\n",
    "        return False \n",
    "\n",
    "    def getRandom(self):\n",
    "        return random.choice(self.vals)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class RandomizedCollection(object):\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.dic = {}\n",
    "        self.dic_2 = {}\n",
    "        self.n = 0\n",
    "\n",
    "    def insert(self, val):\n",
    "        \"\"\"\n",
    "        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.\n",
    "        :type val: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        flag = not val in self.dic\n",
    "        if flag:self.dic[val] = set()\n",
    "        self.dic[val].add(self.n)\n",
    "        self.dic_2[self.n] = val\n",
    "        self.n += 1\n",
    "        return flag\n",
    "\n",
    "    def remove(self, val):\n",
    "        \"\"\"\n",
    "        Removes a value from the collection. Returns true if the collection contained the specified element.\n",
    "        :type val: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not val in self.dic:return False\n",
    "        val_index = self.dic[val].pop()\n",
    "        if not self.dic[val]:self.dic.pop(val)\n",
    "        last_val = self.dic_2.pop(self.n-1)\n",
    "        if val_index != self.n-1:\n",
    "            self.dic[last_val].remove(self.n-1)\n",
    "            self.dic[last_val].add(val_index)\n",
    "            self.dic_2[val_index] = last_val\n",
    "        self.n -= 1\n",
    "        return True\n",
    "\n",
    "    def getRandom(self):\n",
    "        \"\"\"\n",
    "        Get a random element from the collection.\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return self.dic_2[random.randint(0,self.n-1)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Basic Calculator\n",
    "\n",
    "Implement a basic calculator to evaluate a simple expression string.\n",
    "\n",
    "The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .\n",
    "```\n",
    "Example 1:\n",
    "\n",
    "Input: \"1 + 1\"\n",
    "Output: 2\n",
    "Example 2:\n",
    "\n",
    "Input: \" 2-1 + 2 \"\n",
    "Output: 3\n",
    "Example 3:\n",
    "\n",
    "Input: \"(1+(4+5+2)-3)+(6+8)\"\n",
    "Output: 23\n",
    "Note:\n",
    "You may assume that the given expression is always valid.\n",
    "Do not use the eval built-in library function.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate(self, s):\n",
    "    res, num, sign, stack = 0, 0, 1, []\n",
    "    for ss in s:\n",
    "        if ss.isdigit():\n",
    "            num = 10*num + int(ss)\n",
    "        elif ss in [\"-\", \"+\"]:\n",
    "            res += sign*num\n",
    "            num = 0\n",
    "            sign = [-1, 1][ss==\"+\"]\n",
    "        elif ss == \"(\":\n",
    "            stack.append(res)\n",
    "            stack.append(sign)\n",
    "            sign, res = 1, 0\n",
    "        elif ss == \")\":\n",
    "            res += sign*num\n",
    "            res *= stack.pop()\n",
    "            res += stack.pop()\n",
    "            num = 0\n",
    "    return res + num*sign"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "51. N-Queens\n",
    "\n",
    "The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.\n",
    "\n",
    "![](https://assets.leetcode.com/uploads/2018/10/12/8-queens.png)\n",
    "\n",
    "Given an integer n, return all distinct solutions to the n-queens puzzle.\n",
    "\n",
    "Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.\n",
    "```\n",
    "Example:\n",
    "\n",
    "Input: 4\n",
    "Output: [\n",
    " [\".Q..\",  // Solution 1\n",
    "  \"...Q\",\n",
    "  \"Q...\",\n",
    "  \"..Q.\"],\n",
    "\n",
    " [\"..Q.\",  // Solution 2\n",
    "  \"Q...\",\n",
    "  \"...Q\",\n",
    "  \".Q..\"]\n",
    "]\n",
    "Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solveNQueens(self, n):\n",
    "    res = []\n",
    "    self.dfs([-1]*n, 0, [], res)\n",
    "    return res\n",
    " \n",
    "# nums is a one-dimension array, like [1, 3, 0, 2] means\n",
    "# first queen is placed in column 1, second queen is placed\n",
    "# in column 3, etc.\n",
    "def dfs(self, nums, index, path, res):\n",
    "    if index == len(nums):\n",
    "        res.append(path)\n",
    "        return  # backtracking\n",
    "    for i in xrange(len(nums)):\n",
    "        nums[index] = i\n",
    "        if self.valid(nums, index):  # pruning\n",
    "            tmp = \".\"*len(nums)\n",
    "            self.dfs(nums, index+1, path+[tmp[:i]+\"Q\"+tmp[i+1:]], res)\n",
    "\n",
    "# check whether nth queen can be placed in that column\n",
    "def valid(self, nums, n):\n",
    "    for i in xrange(n):\n",
    "        if abs(nums[i]-nums[n]) == n -i or nums[i] == nums[n]:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Longest Consecutive Sequence\n",
    "```\n",
    "Given an unsorted array of integers, find the length of the longest consecutive elements sequence.\n",
    "\n",
    "Your algorithm should run in O(n) complexity.\n",
    "\n",
    "Example:\n",
    "\n",
    "Input: [100, 4, 200, 1, 3, 2]\n",
    "Output: 4\n",
    "Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def longestConsecutive(self, nums):\n",
    "    nums = set(nums)\n",
    "    best = 0\n",
    "    for x in nums:\n",
    "        if x - 1 not in nums:\n",
    "            y = x + 1\n",
    "            while y in nums:\n",
    "                y += 1\n",
    "            best = max(best, y - x)\n",
    "    return best"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Guess the Word\n",
    "```\n",
    "This problem is an interactive problem new to the LeetCode platform.\n",
    "\n",
    "We are given a word list of unique words, each word is 6 letters long, and one word in this list is chosen as secret.\n",
    "\n",
    "You may call master.guess(word) to guess a word.  The guessed word should have type string and must be from the original list with 6 lowercase letters.\n",
    "\n",
    "This function returns an integer type, representing the number of exact matches (value and position) of your guess to the secret word.  Also, if your guess is not in the given wordlist, it will return -1 instead.\n",
    "\n",
    "For each test case, you have 10 guesses to guess the word. At the end of any number of calls, if you have made 10 or less calls to master.guess and at least one of these guesses was the secret, you pass the testcase.\n",
    "\n",
    "Besides the example test case below, there will be 5 additional test cases, each with 100 words in the word list.  The letters of each word in those testcases were chosen independently at random from 'a' to 'z', such that every word in the given word lists is unique.\n",
    "\n",
    "Example 1:\n",
    "Input: secret = \"acckzz\", wordlist = [\"acckzz\",\"ccbazz\",\"eiowzz\",\"abcczz\"]\n",
    "\n",
    "Explanation:\n",
    "\n",
    "master.guess(\"aaaaaa\") returns -1, because \"aaaaaa\" is not in wordlist.\n",
    "master.guess(\"acckzz\") returns 6, because \"acckzz\" is secret and has all 6 matches.\n",
    "master.guess(\"ccbazz\") returns 3, because \"ccbazz\" has 3 matches.\n",
    "master.guess(\"eiowzz\") returns 2, because \"eiowzz\" has 2 matches.\n",
    "master.guess(\"abcczz\") returns 4, because \"abcczz\" has 4 matches.\n",
    "\n",
    "We made 5 calls to master.guess and one of them was the secret, so we pass the test case.\n",
    "Note:  Any solutions that attempt to circumvent the judge will result in disqualification.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "        \n",
    "    def findSecretWord(self, wordlist, master):\n",
    "        \"\"\"\n",
    "        :type wordlist: List[Str]\n",
    "        :type master: Master\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        \n",
    "        def countMatches(w1, w2):\n",
    "            return sum(1 for c1, c2 in zip(w1, w2) if c1 == c2)\n",
    "        \n",
    "        def wordScore(char_pos_to_count):\n",
    "            return lambda word: sum(char_pos_to_count[(c, i)] for i, c in enumerate(word))\n",
    "                    \n",
    "        if len(wordlist) == 1:\n",
    "            master.guess(wordlist[0])\n",
    "        \n",
    "        possible = list(wordlist) # for some reason there's an error in master.guess() if wordlist is directly modified\n",
    "        \n",
    "        char_pos_to_count = defaultdict(lambda: 0)\n",
    "\n",
    "        for word in possible:\n",
    "            for pos, char in enumerate(word):\n",
    "                char_pos_to_count[(char, pos)] += 1\n",
    "\n",
    "        possible.sort(key=wordScore(char_pos_to_count))\n",
    "        \n",
    "        for _ in range(10):\n",
    "            \n",
    "            if len(possible) == 1:\n",
    "                master.guess(possible[0])\n",
    "                return\n",
    "            \n",
    "            guessed = possible.pop()\n",
    "            verdict = master.guess(guessed)\n",
    "            \n",
    "            if verdict == 6:\n",
    "                return\n",
    "            \n",
    "            possible = [w for w in possible if countMatches(w, guessed) == verdict]\n",
    "        \n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def findSecretWord(self, wordlist, master):\n",
    "\t\t\n",
    "        def pair_matches(a, b):         # count the number of matching characters\n",
    "            return sum(c1 == c2 for c1, c2 in zip(a, b))\n",
    "\n",
    "        def most_overlap_word():\n",
    "            counts = [[0 for _ in range(26)] for _ in range(6)]     # counts[i][j] is nb of words with char j at index i\n",
    "            for word in candidates:\n",
    "                for i, c in enumerate(word):\n",
    "                    counts[i][ord(c) - ord(\"a\")] += 1\n",
    "\n",
    "            best_score = 0\n",
    "            for word in candidates:\n",
    "                score = 0\n",
    "                for i, c in enumerate(word):\n",
    "                    score += counts[i][ord(c) - ord(\"a\")]           # all words with same chars in same positions\n",
    "                if score > best_score:\n",
    "                    best_score = score\n",
    "                    best_word = word\n",
    "\n",
    "            return best_word\n",
    "\n",
    "        candidates = wordlist[:]        # all remaining candidates, initially all words\n",
    "        while candidates:\n",
    "\n",
    "            s = most_overlap_word()     # guess the word that overlaps with most others\n",
    "            matches = master.guess(s)\n",
    "\n",
    "            if matches == 6:\n",
    "                return\n",
    "\n",
    "            candidates = [w for w in candidates if pair_matches(s, w) == matches]   # filter words with same matches"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Smallest Range\n",
    "\n",
    "You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists.\n",
    "\n",
    "We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.\n",
    "```\n",
    "Example 1:\n",
    "Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]\n",
    "Output: [20,24]\n",
    "Explanation: \n",
    "List 1: [4, 10, 15, 24,26], 24 is in range [20,24].\n",
    "List 2: [0, 9, 12, 20], 20 is in range [20,24].\n",
    "List 3: [5, 18, 22, 30], 22 is in range [20,24].\n",
    "Note:\n",
    "The given list may contain duplicates, so ascending order means >= here.\n",
    "1 <= k <= 3500\n",
    "-105 <= value of elements <= 105.\n",
    "For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you'll see this point.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def smallestRange(self, A):\n",
    "    pq = [(row[0], i, 0) for i, row in enumerate(A)]\n",
    "    heapq.heapify(pq)\n",
    "    \n",
    "    ans = -1e9, 1e9\n",
    "    right = max(row[0] for row in A)\n",
    "    while pq:\n",
    "        left, i, j = heapq.heappop(pq)\n",
    "        if right - left < ans[1] - ans[0]:\n",
    "            ans = left, right\n",
    "        if j + 1 == len(A[i]):\n",
    "            return ans\n",
    "        v = A[i][j+1]\n",
    "        right = max(right, v)\n",
    "        heapq.heappush(pq, (v, i, j+1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Robot Room Cleaner\n",
    "\n",
    "Given a robot cleaner in a room modeled as a grid.\n",
    "\n",
    "Each cell in the grid can be empty or blocked.\n",
    "\n",
    "The robot cleaner with 4 given APIs can move forward, turn left or turn right. Each turn it made is 90 degrees.\n",
    "\n",
    "When it tries to move into a blocked cell, its bumper sensor detects the obstacle and it stays on the current cell.\n",
    "\n",
    "Design an algorithm to clean the entire room using only the 4 given APIs shown below.\n",
    "\n",
    "interface Robot {\n",
    "  // returns true if next cell is open and robot moves into the cell.\n",
    "  // returns false if next cell is obstacle and robot stays on the current cell.\n",
    "  boolean move();\n",
    "\n",
    "  // Robot will stay on the same cell after calling turnLeft/turnRight.\n",
    "  // Each turn will be 90 degrees.\n",
    "  void turnLeft();\n",
    "  void turnRight();\n",
    "\n",
    "  // Clean the current cell.\n",
    "  void clean();\n",
    "}\n",
    "\n",
    "```\n",
    "Example:\n",
    "\n",
    "Input:\n",
    "room = [\n",
    "  [1,1,1,1,1,0,1,1],\n",
    "  [1,1,1,1,1,0,1,1],\n",
    "  [1,0,1,1,1,1,1,1],\n",
    "  [0,0,0,1,0,0,0,0],\n",
    "  [1,1,1,1,1,1,1,1]\n",
    "],\n",
    "row = 1,\n",
    "col = 3\n",
    "\n",
    "Explanation:\n",
    "All grids in the room are marked by either 0 or 1.\n",
    "0 means the cell is blocked, while 1 means the cell is accessible.\n",
    "The robot initially starts at the position of row=1, col=3.\n",
    "From the top left corner, its position is one row below and three columns right.\n",
    "Notes:\n",
    "\n",
    "The input is only given to initialize the room and the robot's position internally. You must solve this problem \"blindfolded\". In other words, you must control the robot using only the mentioned 4 APIs, without knowing the room layout and the initial robot's position.\n",
    "The robot's initial position will always be in an accessible cell.\n",
    "The initial direction of the robot will be facing up.\n",
    "All accessible cells are connected, which means the all cells marked as 1 will be accessible by the robot.\n",
    "Assume all four edges of the grid are all surrounded by wall.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def cleanRoom(self, robot):\n",
    "        \"\"\"\n",
    "        :type robot: Robot\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        self.dfs(robot, 0, 0, 0, 1, set())\n",
    "    \n",
    "    def dfs(self, robot, x, y, direction_x, direction_y, visited):\n",
    "        robot.clean()\n",
    "        visited.add((x, y))\n",
    "        \n",
    "        for k in range(4):\n",
    "            neighbor_x = x + direction_x\n",
    "            neighbor_y = y + direction_y\n",
    "            if (neighbor_x, neighbor_y) not in visited and robot.move():\n",
    "                self.dfs(robot, neighbor_x, neighbor_y, direction_x, direction_y, visited)\n",
    "                robot.turnLeft()\n",
    "                robot.turnLeft()\n",
    "                robot.move()\n",
    "                robot.turnLeft()\n",
    "                robot.turnLeft()\n",
    "            robot.turnLeft()\n",
    "            direction_x, direction_y = -direction_y, direction_x   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Desgin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### All O`one Data Structure\n",
    "Hard\n",
    "\n",
    "Implement a data structure supporting the following operations:\n",
    "\n",
    "Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.\n",
    "Dec(Key) - If Key's value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.\n",
    "GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string \"\".\n",
    "GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string \"\".\n",
    "Challenge: Perform all these in O(1) time complexity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    def __init__(self, key, val=1):\n",
    "        self.key = key\n",
    "        self.val = val\n",
    "        self.prev = None\n",
    "        self.next = None\n",
    "    \n",
    "    def backward(self):\n",
    "        #ABCD -> ACBD, self is C\n",
    "        p_, p__, n_ = self.prev, self.prev.prev, self.next\n",
    "        self.prev, self.next, p_.prev, p_.next, p__.next, n_.prev = p__, p_, self, n_, self, p_\n",
    "\n",
    "    def forward(self):\n",
    "        #ACBD -> ABCD, self is B \n",
    "        n_, n__, p_ = self.next, self.next.next, self.prev\n",
    "        self.next, self.prev, n_.next, n_.prev, p_.next, n__.prev = n__, n_, self, p_, n_, self\n",
    "    \n",
    "    \n",
    "class AllOne:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.keys = {} \n",
    "        self.head = Node(key=None, val=None)\n",
    "        self.tail = Node(key=None, val=None)\n",
    "        self.head.next = self.tail\n",
    "        self.tail.prev = self.head       \n",
    "        \n",
    "        \n",
    "    def inc(self, key: str) -> None:\n",
    "        \"\"\"\n",
    "        Inserts a new key <Key> with value 1. Or increments an existing key by 1.\n",
    "        \"\"\"\n",
    "        if key in self.keys:\n",
    "            # 1,1,2,1 -> 1,1,1,2\n",
    "            node = self.keys[key]\n",
    "            node.val += 1\n",
    "            while node.next.key and node.val > node.next.val:\n",
    "                node.forward()\n",
    "        else:\n",
    "            # h-old -> h-new-old\n",
    "            node = Node(key)\n",
    "            self.keys[key] = node\n",
    "            h, n_ =self.head, self.head.next\n",
    "            h.next, n_.prev = node, node\n",
    "            node.prev, node.next = h, n_\n",
    "            \n",
    "            \n",
    "            \n",
    "    def dec(self, key: str) -> None:\n",
    "        \"\"\"\n",
    "        Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.\n",
    "        \"\"\"\n",
    "        if key in self.keys:\n",
    "            node = self.keys[key]\n",
    "            if node.val == 1:\n",
    "                p_, n_ = node.prev, node.next\n",
    "                p_.next = n_\n",
    "                n_.prev = p_\n",
    "                self.keys.pop(key)\n",
    "            else:\n",
    "                node.val -= 1\n",
    "                while node.prev.key and node.prev.val > node.val:\n",
    "                    node.backward()\n",
    "                \n",
    "\n",
    "    def getMaxKey(self) -> str:\n",
    "        \"\"\"\n",
    "        Returns one of the keys with maximal value.\n",
    "        get tail\n",
    "        \"\"\"\n",
    "        return self.tail.prev.key if self.tail.prev.key else ''\n",
    "        \n",
    "\n",
    "    def getMinKey(self) -> str:\n",
    "        \"\"\"\n",
    "        Returns one of the keys with Minimal value.\n",
    "        get head\n",
    "        \"\"\"\n",
    "        return self.head.next.key if self.head.next.key else ''\n",
    "\n",
    "\n",
    "# Your AllOne object will be instantiated and called as such:\n",
    "# obj = AllOne()\n",
    "# obj.inc(key)\n",
    "# obj.dec(key)\n",
    "# param_3 = obj.getMaxKey()\n",
    "# param_4 = obj.getMinKey()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Behavioral Question"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Why do you want to go to FB?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What is the maxium changellenge in your work "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# System Desgin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Database"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Consistant Hashing\n",
    "\n",
    "在 Consistent Hashing I 中我们介绍了一个比较简单的一致性哈希算法，这个简单的版本有两个缺陷：\n",
    "\n",
    "增加一台机器之后，数据全部从其中一台机器过来，这一台机器的读负载过大，对正常的服务会造成影响。\n",
    "当增加到3台机器的时候，每台服务器的负载量不均衡，为1:1:2。\n",
    "为了解决这个问题，引入了 micro-shards 的概念，一个更好的算法是这样：\n",
    "\n",
    "将 360° 的区间分得更细。从 0~359 变为一个 0 ~ n-1 的区间，将这个区间首尾相接，连成一个圆。\n",
    "当加入一台新的机器的时候，随机选择在圆周中撒 k 个点，代表这台机器的 k 个 micro-shards。\n",
    "每个数据在圆周上也对应一个点，这个点通过一个 hash function 来计算。\n",
    "一个数据该属于那台机器负责管理，是按照该数据对应的圆周上的点在圆上顺时针碰到的第一个 micro-shard 点所属的机器来决定。\n",
    "n 和 k在真实的 NoSQL 数据库中一般是 2^64 和 1000。\n",
    "\n",
    "请实现这种引入了 micro-shard 的 consistent hashing 的方法。主要实现如下的三个函数：\n",
    "\n",
    "create(int n, int k)\n",
    "addMachine(int machine_id) // add a new machine, return a list of shard ids.\n",
    "\n",
    "getMachineIdByHashCode(int hashcode) // return machine id\n",
    "\n",
    " Notice\n",
    "当 n 为 2^64 时，在这个区间内随机基本不会出现重复。\n",
    "但是为了方便测试您程序的正确性，n 在数据中可能会比较小，所以你必须保证你生成的 k 个随机数不会出现重复。\n",
    "```\n",
    "Example 1:\n",
    "\n",
    "Input:\n",
    "  create(100, 3)\n",
    "  addMachine(1)\n",
    "  getMachineIdByHashCode(4)\n",
    "  addMachine(2)\n",
    "  getMachineIdByHashCode(61)\n",
    "  getMachineIdByHashCode(91)\n",
    "Output:\n",
    "  [77,83,86]\n",
    "  1\n",
    "  [15,35,93]\n",
    "  1\n",
    "  2\n",
    "Example 2:\n",
    "\n",
    "Input:\n",
    "  create(10, 5)\n",
    "  addMachine(1)\n",
    "  getMachineIdByHashCode(4)\n",
    "  addMachine(2)\n",
    "  getMachineIdByHashCode(0)\n",
    "  getMachineIdByHashCode(1)\n",
    "  getMachineIdByHashCode(2)\n",
    "  getMachineIdByHashCode(3)\n",
    "  getMachineIdByHashCode(4)\n",
    "  getMachineIdByHashCode(5)\n",
    "Output:\n",
    "  [2,3,5,6,7]\n",
    "  1\n",
    "  [0,1,4,8,9]\n",
    "  2\n",
    "  2\n",
    "  1\n",
    "  1\n",
    "  2\n",
    "  1\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "\n",
    "    # @param {int} n a positive integer\n",
    "    # @param {int} k a positive integer\n",
    "    # @return {Solution} a Solution object\n",
    "    @classmethod\n",
    "    def create(cls, n, k):\n",
    "        # Write your code here\n",
    "        solution = cls()\n",
    "        solution.ids = {}\n",
    "        solution.machines = {}\n",
    "        solution.n = n\n",
    "        solution.k = k\n",
    "        return solution\n",
    "\n",
    "    # @param {int} machine_id an integer\n",
    "    # @return {int[]} a list of shard ids\n",
    "    def addMachine(self, machine_id):\n",
    "        # write your code here\n",
    "        ids = []\n",
    "        import random\n",
    "        for i in range(self.k):\n",
    "            index = random.randint(0, self.n - 1)\n",
    "            while index in self.ids:\n",
    "                index = random.randint(0, self.n - 1)\n",
    "\n",
    "            ids.append(index)\n",
    "            self.ids[index] = True\n",
    "\n",
    "        ids.sort()\n",
    "        self.machines[machine_id] = ids\n",
    "        return ids\n",
    "\n",
    "    # @param {int} hashcode an integer\n",
    "    # @return {int} a machine id\n",
    "    def getMachineIdByHashCode(self, hashcode):\n",
    "        # write your code here\n",
    "        machine_id = -1\n",
    "        distance = self.n + 1\n",
    "\n",
    "        for key, value in self.machines.items():\n",
    "            import bisect\n",
    "            index = bisect.bisect_left(value, hashcode) % len(value)\n",
    "            d = value[index] - hashcode\n",
    "            if d < 0:\n",
    "                d += self.n\n",
    "\n",
    "            if d < distance:\n",
    "                distance = d\n",
    "                machine_id = key\n",
    "\n",
    "        return machine_id"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## URL Shortening service"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### BASE 62 基本算法\n",
    "\n",
    "Description\n",
    "\n",
    "Given a long url, make it shorter.\n",
    "\n",
    "You should implement two methods:\n",
    "\n",
    "longToShort(url) Convert a long url to a short url which starts with http://tiny.url/.\n",
    "shortToLong(url) Convert a short url to a long url.\n",
    "You can design any shorten algorithm, the judge only cares about two things:\n",
    "\n",
    "The short key's length should equal to 6 (without domain and slash). And the acceptable characters are [a-zA-Z0-9]. For example: abcD9E\n",
    "No two long urls mapping to the same short url and no two short urls mapping to the same long url.\n",
    "```\n",
    "Example 1:\n",
    "\n",
    "Input: shortToLong(longToShort(\"http://www.lintcode.com/faq/?id=10\"))\n",
    "Output: \"http://www.lintcode.com/faq/?id=10\"\n",
    "Explanation: \n",
    "  When longToShort() called, you can return any short url.\n",
    "  For example, \"http://tiny.url/abcdef\".\n",
    "  And \"http://tiny.url/ABCDEF\" is ok as well.\n",
    "Example 2:\n",
    "\n",
    "Input:\n",
    "  shortToLong(longToShort(\"http://www.lintcode.com/faq/?id=10\"))\n",
    "  shortToLong(longToShort(\"http://www.lintcode.com/faq/?id=10\"))\n",
    "Output:\n",
    "  \"http://www.lintcode.com/faq/?id=10\"\n",
    "  \"http://www.lintcode.com/faq/?id=10\"\n",
    "  ```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TinyUrl:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.dict = {}\n",
    "\n",
    "    def getShortKey(self, url):\n",
    "        return url[-6:]\n",
    "\n",
    "    def idToShortKey(self, id):\n",
    "        ch = \"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789\"\n",
    "        s = \"\"\n",
    "        while id > 0:\n",
    "            s = ch[id % 62] + s\n",
    "            id /= 62\n",
    "        while len(s) < 6:\n",
    "            s = 'a' + s\n",
    "        return s\n",
    "\n",
    "    def shortkeyToid(self, short_key):\n",
    "        id = 0\n",
    "        for c in short_key:\n",
    "            if 'a' <= c and c <= 'z':\n",
    "                id = id * 62 + ord(c) - ord('a')\n",
    "            if 'A' <= c and c <= 'Z':\n",
    "                id = id * 62 + ord(c) - ord('A') + 26\n",
    "            if '0' <= c and c <= '9':\n",
    "                id = id * 62 + ord(c) - ord('0') + 52\n",
    "\n",
    "        return id\n",
    "\n",
    "    # @param {string} url a long url\n",
    "    # @return {string} a short url starts with http://tiny.url/\n",
    "    def longToShort(self, url):\n",
    "        # Write your code here\n",
    "        ans = 0\n",
    "        for a in url:\n",
    "            ans = (ans * 256 + ord(a)) % 56800235584L\n",
    "\n",
    "        while ans in self.dict and self.dict[ans] != url:\n",
    "            ans = (ans + 1) % 56800235584L\n",
    "\n",
    "        self.dict[ans] = url\n",
    "        return \"http://tiny.url/\" + self.idToShortKey(ans)\n",
    "\n",
    "    # @param {string} url a short url starts with http://tiny.url/\n",
    "    # @return {string} a long url\n",
    "    def shortToLong(self, url):\n",
    "        # Write your code here\n",
    "        short_key = self.getShortKey(url)\n",
    "        return self.dict[self.shortkeyToid(short_key)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 定制化短网址\n",
    "As a follow up for Tiny URL, we are going to support custom tiny url, so that user can create their own tiny url. That is to say, you need to implement one more createCustom than 232. Tiny Url.\n",
    "\n",
    "You should implement three methods:\n",
    "\n",
    "longToShort(url) Convert a long url to a short url which starts with http://tiny.url/.\n",
    "shortToLong(url) Convert a short url to a long url.\n",
    "createCustom(url, key) Set the short url of a long url to http://tiny.url/ + key\n",
    "You can design any shorten algorithm, the judge only cares about:\n",
    "\n",
    "The length of short key' generated by longToShort should equal to 6 (without domain and slash). And the acceptable characters are [a-zA-Z0-9]. For example: abcD9E\n",
    "No two long urls mapping to the same short url and no two short urls mapping to the same long url.\n",
    "If createCustom can not meet users' expectment, return \"error\"; otherwise return the short url.\n",
    "\n",
    "```\n",
    "Example 1:\n",
    "\n",
    "Input:\n",
    "  createCustom(\"http://www.lintcode.com/\", \"lccode\")\n",
    "  shortToLong(\"http://tiny.url/lccode\")\n",
    "  createCustom(\"http://www.lintcode.com/\", \"ltcode\")\n",
    "Output:\n",
    "  \"http://tiny.url/lccode\"\n",
    "  \"http://www.lintcode.com/\"\n",
    "  \"error\"\n",
    "Example 2:\n",
    "\n",
    "Input:\n",
    "  longToShort(\"http://www.lintcode.com/\")\n",
    "  createCustom(\"http://www.lintcode.com/\", \"ltcode\")\n",
    "Output:\n",
    "  \"http://tiny.url/abcdef\"    => This answer is not unique.\n",
    "  \"error\"\n",
    "Explanation:\n",
    "  Although it is almost impossible:\n",
    "  if your longToShort() just returns \"http://tiny.url/ltcode\",  \n",
    "  your createCustom() should return \"http://tiny.url/ltcode\".\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TinyUrl2:\n",
    "    def __init__(self):\n",
    "        self.l2s = {}\n",
    "        self.s2l = {}\n",
    "        self.cnt = 0\n",
    "        self.tinyUrl = 'http://tiny.url/'\n",
    "        self.charset = 'qwertyuiopasdfghjklzxcvbnm1234567890QWERTYUIOPASDFGHJKLZXCVBNM'\n",
    "    \n",
    "    def newShortUrl(self):\n",
    "        res = ''\n",
    "        tmp = self.cnt\n",
    "        for i in range(6):\n",
    "            res += self.charset[tmp % 62]\n",
    "            tmp //= 62\n",
    "        self.cnt += 1\n",
    "        return self.tinyUrl + res\n",
    "        \n",
    "    \"\"\"\n",
    "    @param: long_url: a long url\n",
    "    @param: key: a short key\n",
    "    @return: a short url starts with http://tiny.url/\n",
    "    \"\"\"\n",
    "    def createCustom(self, long_url, key):\n",
    "        short_url = self.tinyUrl + key\n",
    "        if long_url in self.l2s:\n",
    "            if self.l2s[long_url] == short_url:\n",
    "                return short_url\n",
    "            else:\n",
    "                return 'error' \n",
    "        if short_url in self.s2l:\n",
    "            return 'error'\n",
    "        self.l2s[long_url] = short_url\n",
    "        self.s2l[short_url] = long_url\n",
    "        return short_url\n",
    "\n",
    "    \"\"\"\n",
    "    @param: long_url: a long url\n",
    "    @return: a short url starts with http://tiny.url/\n",
    "    \"\"\"\n",
    "    def longToShort(self, long_url):\n",
    "        if long_url in self.l2s:\n",
    "            return self.l2s[long_url]\n",
    "        short_url = self.newShortUrl()\n",
    "        self.l2s[long_url] = short_url\n",
    "        self.s2l[short_url] = long_url\n",
    "        return short_url\n",
    "\n",
    "    \"\"\"\n",
    "    @param: short_url: a short url starts with http://tiny.url/\n",
    "    @return: a long url\n",
    "    \"\"\"\n",
    "    def shortToLong(self, short_url):\n",
    "        if short_url in self.s2l:\n",
    "            return self.s2l[short_url]\n",
    "        else:\n",
    "            return 'error'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "py37",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "253.438px"
   },
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}