Leetcode.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Median of Two Sorted Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are two sorted arrays nums1 and nums2 of size m and n respectively.\n",
    "\n",
    "Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n))."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Apply merge sort takes O(log(m+n)). Then find the median of the combined list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        # part of merge sort\n",
    "        result=[]\n",
    "        k=0\n",
    "        j=0\n",
    "        while(k<len(nums1) and j<len(nums2)):\n",
    "            if(nums1[k]<=nums2[j]):\n",
    "                result.append(nums1[k])\n",
    "                k+=1\n",
    "            else:\n",
    "                result.append(nums2[j])\n",
    "                j+=1\n",
    "        if(k==len(nums1)):\n",
    "            result+=nums2[j:]\n",
    "        else:\n",
    "            result+=nums1[k:]\n",
    "        \n",
    "        # find median\n",
    "        if(len(result)%2==0):\n",
    "            index2=len(result)/2\n",
    "            index1=index2-1\n",
    "            median=float(result[index1]+result[index2])/2.0\n",
    "        else:\n",
    "            index=len(result)//2\n",
    "            median=result[index]\n",
    "        \n",
    "        return median"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums1 = [1, 3]\n",
    "nums2 = [2]\n",
    "o.findMedianSortedArrays(nums1,nums2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Merge Two Sorted Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Start from the head, if l1.node<l2.node, we move pointer of l1 to the next node and compare the next node from l1 with l2 current node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 928,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "class ListNode(object):\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution(object):\n",
    "    def mergeTwoLists(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        head=None\n",
    "        pointer=None\n",
    "        # compare l1 and l2\n",
    "        while l1!=None and l2!=None:\n",
    "            if l1.val<=l2.val:\n",
    "                if pointer==None:\n",
    "                    head=l1\n",
    "                    pointer=l1\n",
    "                else:\n",
    "                    pointer.next=l1\n",
    "                    pointer=pointer.next\n",
    "                l1=l1.next\n",
    "            else:\n",
    "                if pointer==None:\n",
    "                    head=l2\n",
    "                    pointer=l2\n",
    "                else:\n",
    "                    pointer.next=l2\n",
    "                    pointer=pointer.next\n",
    "                l2=l2.next\n",
    "                \n",
    "        # concatenate the rest of l1\n",
    "        if l1!=None:\n",
    "            if pointer!=None:\n",
    "                pointer.next=l1\n",
    "            else:\n",
    "                head=l1\n",
    "            \n",
    "        # concatenate the rest of l2\n",
    "        if l2!=None:\n",
    "            if pointer!=None:\n",
    "                pointer.next=l2\n",
    "            else:\n",
    "                head=l2\n",
    "            \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 931,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "l1=ListNode(1)\n",
    "l1.next=ListNode(3)\n",
    "l1.next.next=ListNode(5)\n",
    "l1.next.next.next=ListNode(7)\n",
    "l2=ListNode(2)\n",
    "l2.next=ListNode(4)\n",
    "l2.next.next=ListNode(6)\n",
    "l2.next.next.next=ListNode(8)\n",
    "o=Solution()\n",
    "head=o.mergeTwoLists(l1, l2)\n",
    "while head!=None:\n",
    "    print head.val\n",
    "    head=head.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Valid Parentheses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.\n",
    "\n",
    "The brackets must close in the correct order, \"()\" and \"()[]{}\" are all valid but \"(]\" and \"([)]\" are not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 959,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isValid(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        stack=[]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in \"({[\":\n",
    "                stack.append(s[i])\n",
    "            if s[i] in \")}]\":\n",
    "                if(stack!=[] and self.match(stack[len(stack)-1],s[i])):\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    return False\n",
    "        return stack==[]\n",
    "    \n",
    "    def match(self,a,b):\n",
    "        return (a=='(' and b==')') or (a=='[' and b==']') or (a=='{' and b=='}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 960,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 960,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.isValid('{[][]}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=red>Longest Palindromic Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward, such as madam or kayak. Sentence-length palindromes may be written when allowances are made for adjustments to capital letters, punctuation, and word dividers, such as \"A man, a plan, a canal, Panama!\", \"Was it a car or a cat I saw?\" or \"No 'x' in Nixon\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We take steps as follows.\n",
    "\n",
    "1. use regular expression to filter the string such that it only contains lowercase letters.\n",
    "2. We reverse the string to check if there is a match between substrings in the reversed substring and the original string, we also need to deal with the situation \"adcfda\"->\"adfcda\" where there is no palindrome in the string but there are common substrings between the original string and the reversed one. We need to keep track of the original indices of the reversed substring to see if it matches the original substring.\n",
    "3. Then the problem remains is to find the longest common substring between reversed and original string."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=red> The above method is hard for me to program at the moment, but I will come back here later."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here I would like to consider the dynamical programming approach. Define $P(i,j)$ as\n",
    "\n",
    "\\begin{equation}\n",
    "P(i,j)=\\left\\{\n",
    "                \\begin{array}{ll}\n",
    "                  true & if\\ S_i \\ldots S_j\\ is\\ palindrome \\\\\n",
    "                  false & \\ else\\\\\n",
    "                \\end{array}\n",
    "              \\right.\n",
    "\\end{equation}\n",
    "\n",
    "Obviously,\n",
    "\n",
    "\\begin{equation}\n",
    "P(i,j)=(P(i+1,j-1)\\ and\\ S_i==S_j)\n",
    "\\end{equation}\n",
    "\n",
    "The base case is\n",
    "\n",
    "\\begin{eqnarray}\n",
    "P(i,i)=true \\\\\n",
    "P(i,i+1)=(S_i==S_{i+1})\n",
    "\\end{eqnarray}\n",
    "\n",
    "This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 906,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        n=len(s)\n",
    "        # initialize\n",
    "        P=[[False]*n for i in range(n)]\n",
    "        longest_palindrome=s[0]\n",
    "        for i in range(n):\n",
    "            P[i][i]=True\n",
    "            if i+1<n:\n",
    "                P[i][i+1]=(s[i]==s[i+1])\n",
    "                if P[i][i+1]==True:\n",
    "                    longest_palindrome=s[i:i+2]\n",
    "                \n",
    "        # scan different length\n",
    "        for l in range(2,n):\n",
    "            for i in range(n-l):\n",
    "                P[i][i+l]=(P[i+1][i+l-1] and (s[i]==s[i+l]))\n",
    "                if P[i][i+l]==True:\n",
    "                    longest_palindrome=s[i:i+l+1]\n",
    "                    \n",
    "        return longest_palindrome"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 907,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'bb'"
      ]
     },
     "execution_count": 907,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s='bba'\n",
    "o=Solution()\n",
    "o.longestPalindrome(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=red>The above code still exceed time limit.</font> Let me do some improvement:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        n=len(s)\n",
    "        if n==0: return s\n",
    "        # Palindrome identifying list\n",
    "        P=[[False]*n for i in range(n)]\n",
    "        # initialize\n",
    "        for i in range(n):\n",
    "            P[i][i]=True\n",
    "        for i in range(n-1):\n",
    "            P[i][i+1]=(s[i]==s[i+1])\n",
    "            "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let me turn to the third approach: expand around center. For a string of length n, there could be 2n-1 centers either at a particular character or between characters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 926,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        longest=0\n",
    "        longest_palindrome=''\n",
    "        n=len(s)\n",
    "        # expand around center\n",
    "        for i in range(1,2*n):\n",
    "            #center between characters\n",
    "            if i%2==0:\n",
    "                count=0\n",
    "                index1=(i-1)/2\n",
    "                index2=(i+1)/2\n",
    "                while index1>=0 and index2<n:\n",
    "                    if s[index1]==s[index2]:\n",
    "                        count+=2\n",
    "                        if count>longest:\n",
    "                            longest=count\n",
    "                            longest_palindrome=s[index1:index2+1]\n",
    "                        index1-=1\n",
    "                        index2+=1\n",
    "                    else:\n",
    "                        break\n",
    "            # center at a character\n",
    "            else:\n",
    "                count=1\n",
    "                if count>longest:\n",
    "                    longest=count\n",
    "                    longest_palindrome=s[i/2]\n",
    "                index1=i/2-1\n",
    "                index2=i/2+1\n",
    "                while index1>=0 and index2<n:\n",
    "                    if s[index1]==s[index2]:\n",
    "                        count+=2\n",
    "                        if count>longest:\n",
    "                            longest=count\n",
    "                            longest_palindrome=s[index1:index2+1]\n",
    "                        index1-=1\n",
    "                        index2+=1\n",
    "                    else:\n",
    "                        break\n",
    "                    \n",
    "        return longest_palindrome"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 927,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a'"
      ]
     },
     "execution_count": 927,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s='a'\n",
    "o=Solution()\n",
    "o.longestPalindrome(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Permutations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a collection of distinct numbers, return all possible permutations.\n",
    "\n",
    "For example,\n",
    "[1,2,3] have the following permutations:\n",
    "[\n",
    "  [1,2,3],\n",
    "  [1,3,2],\n",
    "  [2,1,3],\n",
    "  [2,3,1],\n",
    "  [3,1,2],\n",
    "  [3,2,1]\n",
    "]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The algorithm comes into my mind is similar to the N-queen problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 837,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import copy as cp\n",
    "\n",
    "class Solution(object):\n",
    "    def permute(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        solutions=[]\n",
    "        self._permute(solutions,len(nums),0,[None]*len(nums),nums)\n",
    "        return solutions\n",
    "        \n",
    "    def _permute(self,solutions,n,row,perm,nums):\n",
    "        # iterate through column number\n",
    "        for e in nums:\n",
    "            if e not in perm[:row]:\n",
    "                if row==n-1:\n",
    "                    perm[row]=e\n",
    "                    perm2=cp.deepcopy(perm)\n",
    "                    print perm2\n",
    "                    solutions.append(perm2)\n",
    "                else:\n",
    "                    perm[row]=e\n",
    "                    self._permute(solutions,n,row+1,perm,nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 838,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n",
      "[1, 3, 2]\n",
      "[2, 1, 3]\n",
      "[2, 3, 1]\n",
      "[3, 1, 2]\n",
      "[3, 2, 1]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]"
      ]
     },
     "execution_count": 838,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=[1,2,3]\n",
    "o=Solution()\n",
    "o.permute(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reverse Integer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reverse digits of an integer.\n",
    "\n",
    "Example1: x = 123, return 321\n",
    "Example2: x = -123, return -321\n",
    "\n",
    "Caution: make sure to check the **overflow** of the reversed integer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def reverse(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # check negativity\n",
    "        if x==abs(x):\n",
    "            negative=False\n",
    "        else:\n",
    "            negative=True\n",
    "        x=abs(x)\n",
    "        num_list=[]\n",
    "        if x<=2**31:\n",
    "            while x>0:\n",
    "                num_list.append(x%10)\n",
    "                x=x//10\n",
    "            num_list.reverse()\n",
    "            result=0\n",
    "            for i in range(len(num_list)):\n",
    "               result+=num_list[i]*10**i\n",
    "            if negative:\n",
    "                return -result\n",
    "            else:\n",
    "                return result\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-8463847412"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.reverse(-2**31)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## String to Integer (atoi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implement atoi to convert a string to an integer.\n",
    "\n",
    "Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.\n",
    "\n",
    "Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "object of type 'int' has no len()",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-64-954f5ceb39e6>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m12\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: object of type 'int' has no len()"
     ]
    }
   ],
   "source": [
    "len(12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Palindrome Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Determine whether an integer is a palindrome. Do this without extra space."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The most straightforward way is to reverse an integer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isPalindrome(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # handle the negative\n",
    "        if x<0:\n",
    "            return False\n",
    "        n=x\n",
    "        length=0\n",
    "        while n>0:\n",
    "            n=n//10\n",
    "            length+=1\n",
    "        temp=x\n",
    "        for i in range(length):\n",
    "            n+=(temp%10)*10**(length-1-i)\n",
    "            temp=temp//10\n",
    "            \n",
    "        return n==x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 132,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.isPalindrome(1000002000001)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Container With Most Water"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given n non-negative integers $a_1, a_2, ..., a_n$, where each represents a point at coordinate $(i, a_i)$. n vertical lines are drawn such that the two endpoints of line i is at $(i, a_i)$ and $(i, 0)$. Find two lines, which together with x-axis forms a container, such that the container contains the most water.\n",
    "\n",
    "Note: You may not slant the container."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: By double search (brutal force), time O(n^2). It will exceed time limit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def maxArea(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        max_area=0\n",
    "        for i in range(len(height)-1):\n",
    "            for j in range(i+1,len(height)):\n",
    "                area=(j-i)*min(height[i],height[j])\n",
    "                if area>max_area:\n",
    "                    max_area=area\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 134,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "height=[1,2,4,5]\n",
    "o=Solution()\n",
    "o.maxArea(height)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A second approach is by two pointers initially point at the start and the end. then we move the shorter end inwards to check the change of the area (as the maximum area is determined by the shorter end).\n",
    "\n",
    "<img src=https://leetcode.com/media/original_images/11_Container_Water.gif \\>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def maxArea(self, height):\n",
    "        \"\"\"\n",
    "        :type height: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        max_area=0\n",
    "        # pointers\n",
    "        p1=0\n",
    "        p2=len(height)-1\n",
    "        while p1<p2:\n",
    "            if height[p1]<height[p2]:\n",
    "                area=(p2-p1)*height[p1]\n",
    "                p1+=1\n",
    "            else:\n",
    "                area=(p2-p1)*height[p2]\n",
    "                p2-=1\n",
    "            if area>max_area:\n",
    "                max_area=area\n",
    "        \n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3087"
      ]
     },
     "execution_count": 148,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=[4,3,2,1,1,436,346,23,43,2,12,3,5456,343,343]\n",
    "o=Solution()\n",
    "o.maxArea(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Integer to Roman"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an integer, convert it to a roman numeral.\n",
    "\n",
    "Input is guaranteed to be within the range from 1 to 3999."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{array}{llllllll}\n",
    "Symbol &I&\tV&\tX&\tL&\tC&\tD&\tM \\\\\n",
    "Value  &1&\t5&\t10&\t50&\t100& 500&\t1,000\n",
    "\\end{array}\n",
    "\n",
    "<img src=https://s-media-cache-ak0.pinimg.com/736x/9f/69/49/9f694928b32f6bb86ab4bb67ecc886b5.jpg \\>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The Brutal approach is to use a list contains 4 lists to represent different digits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def intToRoman(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        one=['','I','II','III','IV','V','VI','VII','VIII','IX']\n",
    "        ten=['','X','XX','XXX','XL','L','LX','LXX','LXXX','XC']\n",
    "        hundred=['','C','CC','CCC','CD','D','DC','DCC','DCCC','CM']\n",
    "        thousand=['','M','MM','MMM']\n",
    "        roman_dict=[one,ten,hundred,thousand]\n",
    "        num_roman=[]\n",
    "        i=0\n",
    "        while num>0:\n",
    "            num_roman.append(roman_dict[i][num%10])\n",
    "            num=num//10\n",
    "            i+=1\n",
    "        num_roman.reverse()\n",
    "        \n",
    "        return ''.join(num_roman)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 188,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'CXCIX'"
      ]
     },
     "execution_count": 188,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.intToRoman(199)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution seems space expensive. Let me try a different approach."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def intToRoman(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        roman_dict={1:'I',5:'V',10:'X',50:'L',100:'C',500:'D',1000:'M'}\n",
    "        num_list=''\n",
    "        #thousand\n",
    "        num_list+='M'*(num//1000)\n",
    "        num=num-num//1000*1000\n",
    "        #hundred\n",
    "        if num//100<=3:\n",
    "            num_list+='C'*(num//100)\n",
    "        elif num//100>3 and num//100<=8:\n",
    "            num_list+='C'*(5-num//100)+'D'+'C'*(num//100-5)\n",
    "        else:\n",
    "            num_list+='CM'\n",
    "        num=num-num//100*100\n",
    "        #ten\n",
    "        if num//10<=3:\n",
    "            num_list+='X'*(num//10)\n",
    "        elif num//10>3 and num//10<=8:\n",
    "            num_list+='X'*(5-num//10)+'L'+'X'*(num//10-5)\n",
    "        else:\n",
    "            num_list+='XC'\n",
    "        num=num-num//10*10\n",
    "        #one\n",
    "        if num<=3:\n",
    "            num_list+='I'*num\n",
    "        elif num>3 and num<=8:\n",
    "            num_list+='I'*(5-num)+'V'+'I'*(num-5)\n",
    "        else:\n",
    "            num_list+='IX'\n",
    "            \n",
    "        return num_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'CXCIX'"
      ]
     },
     "execution_count": 189,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.intToRoman(199)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pow(x, n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implement pow(x, n)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We would like to do better than the naive solution and improve it to be O(log n)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 274,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def myPow(self, x, n):\n",
    "        \"\"\"\n",
    "        :type x: float\n",
    "        :type n: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        # negative power\n",
    "        if n<0:\n",
    "            x=1.0/x\n",
    "            n=-n\n",
    "        if n==0:\n",
    "            return 1.0\n",
    "        if n%2!=0:\n",
    "            result=x\n",
    "            n-=1\n",
    "        else:\n",
    "            result=1.0\n",
    "            \n",
    "        return result*self.myPow(x*x, n/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 278,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.1111111111111111"
      ]
     },
     "execution_count": 278,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.myPow(3,-2)\n",
    "3**(-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 269,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2147483647"
      ]
     },
     "execution_count": 269,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2**31-1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## N-Queens II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Follow up for N-Queens problem.\n",
    "\n",
    "Now, instead outputting board configurations, return the total number of distinct solutions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 255,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def totalNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        solutions=[]\n",
    "        self._nqueen(solutions,n,0,[None]*n)\n",
    "        return len(solutions)\n",
    "        \n",
    "    def _nqueen(self,solutions,n,row,ColumnForRow):\n",
    "        # iterate through column number\n",
    "        for j in range(n):\n",
    "            diag_checklist=map(lambda x: abs(j-ColumnForRow[x])==abs(row-x), range(len(ColumnForRow[:row])))\n",
    "            if j not in ColumnForRow[:row] \\\n",
    "            and True not in diag_checklist: #not in the same Column and not diagonal with elements in previous rows\n",
    "                if row==n-1:\n",
    "                    ColumnForRow[row]=j\n",
    "                    table=[]\n",
    "                    for i in range(n):\n",
    "                        table.append(['.']*n)\n",
    "                    for i in range(n):\n",
    "                        table[i][ColumnForRow[i]]='Q'\n",
    "                        table[i]=''.join(table[i])\n",
    "                    solutions.append(table)\n",
    "                else:\n",
    "                    ColumnForRow[row]=j\n",
    "                    self._nqueen(solutions,n,row+1,ColumnForRow)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 256,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 256,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.totalNQueens(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 257,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def solveNQueens(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        solutions=[]\n",
    "        self._nqueen(solutions,n,0,[None]*n)\n",
    "        return solutions\n",
    "        \n",
    "    def _nqueen(self,solutions,n,row,ColumnForRow):\n",
    "        # iterate through column number\n",
    "        for j in range(n):\n",
    "            diag_checklist=map(lambda x: abs(j-ColumnForRow[x])==abs(row-x), range(len(ColumnForRow[:row])))\n",
    "            if j not in ColumnForRow[:row] \\\n",
    "            and True not in diag_checklist: #not in the same Column and not diagonal with elements in previous rows\n",
    "                if row==n-1:\n",
    "                    ColumnForRow[row]=j\n",
    "                    table=[]\n",
    "                    for i in range(n):\n",
    "                        table.append(['.']*n)\n",
    "                    for i in range(n):\n",
    "                        table[i][ColumnForRow[i]]='Q'\n",
    "                        table[i]=''.join(table[i])\n",
    "                    solutions.append(table)\n",
    "                else:\n",
    "                    ColumnForRow[row]=j\n",
    "                    self._nqueen(solutions,n,row+1,ColumnForRow)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 259,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['Q.......',\n",
       "  '....Q...',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  '..Q.....',\n",
       "  '......Q.',\n",
       "  '.Q......',\n",
       "  '...Q....'],\n",
       " ['Q.......',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  '..Q.....',\n",
       "  '......Q.',\n",
       "  '...Q....',\n",
       "  '.Q......',\n",
       "  '....Q...'],\n",
       " ['Q.......',\n",
       "  '......Q.',\n",
       "  '...Q....',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  '.Q......',\n",
       "  '....Q...',\n",
       "  '..Q.....'],\n",
       " ['Q.......',\n",
       "  '......Q.',\n",
       "  '....Q...',\n",
       "  '.......Q',\n",
       "  '.Q......',\n",
       "  '...Q....',\n",
       "  '.....Q..',\n",
       "  '..Q.....'],\n",
       " ['.Q......',\n",
       "  '...Q....',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '......Q.',\n",
       "  '....Q...'],\n",
       " ['.Q......',\n",
       "  '....Q...',\n",
       "  '......Q.',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  '...Q....'],\n",
       " ['.Q......',\n",
       "  '....Q...',\n",
       "  '......Q.',\n",
       "  '...Q....',\n",
       "  'Q.......',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  '..Q.....'],\n",
       " ['.Q......',\n",
       "  '.....Q..',\n",
       "  'Q.......',\n",
       "  '......Q.',\n",
       "  '...Q....',\n",
       "  '.......Q',\n",
       "  '..Q.....',\n",
       "  '....Q...'],\n",
       " ['.Q......',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '...Q....',\n",
       "  '......Q.',\n",
       "  '....Q...'],\n",
       " ['.Q......',\n",
       "  '......Q.',\n",
       "  '..Q.....',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  '....Q...',\n",
       "  'Q.......',\n",
       "  '...Q....'],\n",
       " ['.Q......',\n",
       "  '......Q.',\n",
       "  '....Q...',\n",
       "  '.......Q',\n",
       "  'Q.......',\n",
       "  '...Q....',\n",
       "  '.....Q..',\n",
       "  '..Q.....'],\n",
       " ['.Q......',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '....Q...',\n",
       "  '......Q.',\n",
       "  '...Q....'],\n",
       " ['..Q.....',\n",
       "  'Q.......',\n",
       "  '......Q.',\n",
       "  '....Q...',\n",
       "  '.......Q',\n",
       "  '.Q......',\n",
       "  '...Q....',\n",
       "  '.....Q..'],\n",
       " ['..Q.....',\n",
       "  '....Q...',\n",
       "  '.Q......',\n",
       "  '.......Q',\n",
       "  'Q.......',\n",
       "  '......Q.',\n",
       "  '...Q....',\n",
       "  '.....Q..'],\n",
       " ['..Q.....',\n",
       "  '....Q...',\n",
       "  '.Q......',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  '...Q....',\n",
       "  '......Q.',\n",
       "  'Q.......'],\n",
       " ['..Q.....',\n",
       "  '....Q...',\n",
       "  '......Q.',\n",
       "  'Q.......',\n",
       "  '...Q....',\n",
       "  '.Q......',\n",
       "  '.......Q',\n",
       "  '.....Q..'],\n",
       " ['..Q.....',\n",
       "  '....Q...',\n",
       "  '.......Q',\n",
       "  '...Q....',\n",
       "  'Q.......',\n",
       "  '......Q.',\n",
       "  '.Q......',\n",
       "  '.....Q..'],\n",
       " ['..Q.....',\n",
       "  '.....Q..',\n",
       "  '.Q......',\n",
       "  '....Q...',\n",
       "  '.......Q',\n",
       "  'Q.......',\n",
       "  '......Q.',\n",
       "  '...Q....'],\n",
       " ['..Q.....',\n",
       "  '.....Q..',\n",
       "  '.Q......',\n",
       "  '......Q.',\n",
       "  'Q.......',\n",
       "  '...Q....',\n",
       "  '.......Q',\n",
       "  '....Q...'],\n",
       " ['..Q.....',\n",
       "  '.....Q..',\n",
       "  '.Q......',\n",
       "  '......Q.',\n",
       "  '....Q...',\n",
       "  'Q.......',\n",
       "  '.......Q',\n",
       "  '...Q....'],\n",
       " ['..Q.....',\n",
       "  '.....Q..',\n",
       "  '...Q....',\n",
       "  'Q.......',\n",
       "  '.......Q',\n",
       "  '....Q...',\n",
       "  '......Q.',\n",
       "  '.Q......'],\n",
       " ['..Q.....',\n",
       "  '.....Q..',\n",
       "  '...Q....',\n",
       "  '.Q......',\n",
       "  '.......Q',\n",
       "  '....Q...',\n",
       "  '......Q.',\n",
       "  'Q.......'],\n",
       " ['..Q.....',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  'Q.......',\n",
       "  '...Q....',\n",
       "  '......Q.',\n",
       "  '....Q...',\n",
       "  '.Q......'],\n",
       " ['..Q.....',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  'Q.......',\n",
       "  '....Q...',\n",
       "  '......Q.',\n",
       "  '.Q......',\n",
       "  '...Q....'],\n",
       " ['..Q.....',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  '.Q......',\n",
       "  '...Q....',\n",
       "  'Q.......',\n",
       "  '......Q.',\n",
       "  '....Q...'],\n",
       " ['..Q.....',\n",
       "  '......Q.',\n",
       "  '.Q......',\n",
       "  '.......Q',\n",
       "  '....Q...',\n",
       "  'Q.......',\n",
       "  '...Q....',\n",
       "  '.....Q..'],\n",
       " ['..Q.....',\n",
       "  '......Q.',\n",
       "  '.Q......',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  '...Q....',\n",
       "  'Q.......',\n",
       "  '....Q...'],\n",
       " ['..Q.....',\n",
       "  '.......Q',\n",
       "  '...Q....',\n",
       "  '......Q.',\n",
       "  'Q.......',\n",
       "  '.....Q..',\n",
       "  '.Q......',\n",
       "  '....Q...'],\n",
       " ['...Q....',\n",
       "  'Q.......',\n",
       "  '....Q...',\n",
       "  '.......Q',\n",
       "  '.Q......',\n",
       "  '......Q.',\n",
       "  '..Q.....',\n",
       "  '.....Q..'],\n",
       " ['...Q....',\n",
       "  'Q.......',\n",
       "  '....Q...',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  '..Q.....',\n",
       "  '......Q.',\n",
       "  '.Q......'],\n",
       " ['...Q....',\n",
       "  '.Q......',\n",
       "  '....Q...',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '......Q.'],\n",
       " ['...Q....',\n",
       "  '.Q......',\n",
       "  '......Q.',\n",
       "  '..Q.....',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  'Q.......',\n",
       "  '....Q...'],\n",
       " ['...Q....',\n",
       "  '.Q......',\n",
       "  '......Q.',\n",
       "  '..Q.....',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  '....Q...',\n",
       "  'Q.......'],\n",
       " ['...Q....',\n",
       "  '.Q......',\n",
       "  '......Q.',\n",
       "  '....Q...',\n",
       "  'Q.......',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  '..Q.....'],\n",
       " ['...Q....',\n",
       "  '.Q......',\n",
       "  '.......Q',\n",
       "  '....Q...',\n",
       "  '......Q.',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '.....Q..'],\n",
       " ['...Q....',\n",
       "  '.Q......',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '....Q...',\n",
       "  '......Q.'],\n",
       " ['...Q....',\n",
       "  '.....Q..',\n",
       "  'Q.......',\n",
       "  '....Q...',\n",
       "  '.Q......',\n",
       "  '.......Q',\n",
       "  '..Q.....',\n",
       "  '......Q.'],\n",
       " ['...Q....',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  '.Q......',\n",
       "  '......Q.',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '....Q...'],\n",
       " ['...Q....',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '......Q.',\n",
       "  '....Q...',\n",
       "  '.Q......'],\n",
       " ['...Q....',\n",
       "  '......Q.',\n",
       "  'Q.......',\n",
       "  '.......Q',\n",
       "  '....Q...',\n",
       "  '.Q......',\n",
       "  '.....Q..',\n",
       "  '..Q.....'],\n",
       " ['...Q....',\n",
       "  '......Q.',\n",
       "  '..Q.....',\n",
       "  '.......Q',\n",
       "  '.Q......',\n",
       "  '....Q...',\n",
       "  'Q.......',\n",
       "  '.....Q..'],\n",
       " ['...Q....',\n",
       "  '......Q.',\n",
       "  '....Q...',\n",
       "  '.Q......',\n",
       "  '.....Q..',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '.......Q'],\n",
       " ['...Q....',\n",
       "  '......Q.',\n",
       "  '....Q...',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  '.Q......'],\n",
       " ['...Q....',\n",
       "  '.......Q',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '.....Q..',\n",
       "  '.Q......',\n",
       "  '......Q.',\n",
       "  '....Q...'],\n",
       " ['...Q....',\n",
       "  '.......Q',\n",
       "  'Q.......',\n",
       "  '....Q...',\n",
       "  '......Q.',\n",
       "  '.Q......',\n",
       "  '.....Q..',\n",
       "  '..Q.....'],\n",
       " ['...Q....',\n",
       "  '.......Q',\n",
       "  '....Q...',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '......Q.',\n",
       "  '.Q......',\n",
       "  '.....Q..'],\n",
       " ['....Q...',\n",
       "  'Q.......',\n",
       "  '...Q....',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  '.Q......',\n",
       "  '......Q.',\n",
       "  '..Q.....'],\n",
       " ['....Q...',\n",
       "  'Q.......',\n",
       "  '.......Q',\n",
       "  '...Q....',\n",
       "  '.Q......',\n",
       "  '......Q.',\n",
       "  '..Q.....',\n",
       "  '.....Q..'],\n",
       " ['....Q...',\n",
       "  'Q.......',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  '..Q.....',\n",
       "  '......Q.',\n",
       "  '.Q......',\n",
       "  '...Q....'],\n",
       " ['....Q...',\n",
       "  '.Q......',\n",
       "  '...Q....',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '......Q.'],\n",
       " ['....Q...',\n",
       "  '.Q......',\n",
       "  '...Q....',\n",
       "  '......Q.',\n",
       "  '..Q.....',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  'Q.......'],\n",
       " ['....Q...',\n",
       "  '.Q......',\n",
       "  '.....Q..',\n",
       "  'Q.......',\n",
       "  '......Q.',\n",
       "  '...Q....',\n",
       "  '.......Q',\n",
       "  '..Q.....'],\n",
       " ['....Q...',\n",
       "  '.Q......',\n",
       "  '.......Q',\n",
       "  'Q.......',\n",
       "  '...Q....',\n",
       "  '......Q.',\n",
       "  '..Q.....',\n",
       "  '.....Q..'],\n",
       " ['....Q...',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  '.Q......',\n",
       "  '...Q....',\n",
       "  '......Q.'],\n",
       " ['....Q...',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '......Q.',\n",
       "  '.Q......',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  '...Q....'],\n",
       " ['....Q...',\n",
       "  '..Q.....',\n",
       "  '.......Q',\n",
       "  '...Q....',\n",
       "  '......Q.',\n",
       "  'Q.......',\n",
       "  '.....Q..',\n",
       "  '.Q......'],\n",
       " ['....Q...',\n",
       "  '......Q.',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  '...Q....',\n",
       "  '.Q......'],\n",
       " ['....Q...',\n",
       "  '......Q.',\n",
       "  'Q.......',\n",
       "  '...Q....',\n",
       "  '.Q......',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  '..Q.....'],\n",
       " ['....Q...',\n",
       "  '......Q.',\n",
       "  '.Q......',\n",
       "  '...Q....',\n",
       "  '.......Q',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '.....Q..'],\n",
       " ['....Q...',\n",
       "  '......Q.',\n",
       "  '.Q......',\n",
       "  '.....Q..',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '...Q....',\n",
       "  '.......Q'],\n",
       " ['....Q...',\n",
       "  '......Q.',\n",
       "  '.Q......',\n",
       "  '.....Q..',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '.......Q',\n",
       "  '...Q....'],\n",
       " ['....Q...',\n",
       "  '......Q.',\n",
       "  '...Q....',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  '.Q......'],\n",
       " ['....Q...',\n",
       "  '.......Q',\n",
       "  '...Q....',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '.....Q..',\n",
       "  '.Q......',\n",
       "  '......Q.'],\n",
       " ['....Q...',\n",
       "  '.......Q',\n",
       "  '...Q....',\n",
       "  'Q.......',\n",
       "  '......Q.',\n",
       "  '.Q......',\n",
       "  '.....Q..',\n",
       "  '..Q.....'],\n",
       " ['.....Q..',\n",
       "  'Q.......',\n",
       "  '....Q...',\n",
       "  '.Q......',\n",
       "  '.......Q',\n",
       "  '..Q.....',\n",
       "  '......Q.',\n",
       "  '...Q....'],\n",
       " ['.....Q..',\n",
       "  '.Q......',\n",
       "  '......Q.',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '....Q...',\n",
       "  '.......Q',\n",
       "  '...Q....'],\n",
       " ['.....Q..',\n",
       "  '.Q......',\n",
       "  '......Q.',\n",
       "  'Q.......',\n",
       "  '...Q....',\n",
       "  '.......Q',\n",
       "  '....Q...',\n",
       "  '..Q.....'],\n",
       " ['.....Q..',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '......Q.',\n",
       "  '....Q...',\n",
       "  '.......Q',\n",
       "  '.Q......',\n",
       "  '...Q....'],\n",
       " ['.....Q..',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '.......Q',\n",
       "  '...Q....',\n",
       "  '.Q......',\n",
       "  '......Q.',\n",
       "  '....Q...'],\n",
       " ['.....Q..',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '.......Q',\n",
       "  '....Q...',\n",
       "  '.Q......',\n",
       "  '...Q....',\n",
       "  '......Q.'],\n",
       " ['.....Q..',\n",
       "  '..Q.....',\n",
       "  '....Q...',\n",
       "  '......Q.',\n",
       "  'Q.......',\n",
       "  '...Q....',\n",
       "  '.Q......',\n",
       "  '.......Q'],\n",
       " ['.....Q..',\n",
       "  '..Q.....',\n",
       "  '....Q...',\n",
       "  '.......Q',\n",
       "  'Q.......',\n",
       "  '...Q....',\n",
       "  '.Q......',\n",
       "  '......Q.'],\n",
       " ['.....Q..',\n",
       "  '..Q.....',\n",
       "  '......Q.',\n",
       "  '.Q......',\n",
       "  '...Q....',\n",
       "  '.......Q',\n",
       "  'Q.......',\n",
       "  '....Q...'],\n",
       " ['.....Q..',\n",
       "  '..Q.....',\n",
       "  '......Q.',\n",
       "  '.Q......',\n",
       "  '.......Q',\n",
       "  '....Q...',\n",
       "  'Q.......',\n",
       "  '...Q....'],\n",
       " ['.....Q..',\n",
       "  '..Q.....',\n",
       "  '......Q.',\n",
       "  '...Q....',\n",
       "  'Q.......',\n",
       "  '.......Q',\n",
       "  '.Q......',\n",
       "  '....Q...'],\n",
       " ['.....Q..',\n",
       "  '...Q....',\n",
       "  'Q.......',\n",
       "  '....Q...',\n",
       "  '.......Q',\n",
       "  '.Q......',\n",
       "  '......Q.',\n",
       "  '..Q.....'],\n",
       " ['.....Q..',\n",
       "  '...Q....',\n",
       "  '.Q......',\n",
       "  '.......Q',\n",
       "  '....Q...',\n",
       "  '......Q.',\n",
       "  'Q.......',\n",
       "  '..Q.....'],\n",
       " ['.....Q..',\n",
       "  '...Q....',\n",
       "  '......Q.',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '....Q...',\n",
       "  '.Q......',\n",
       "  '.......Q'],\n",
       " ['.....Q..',\n",
       "  '...Q....',\n",
       "  '......Q.',\n",
       "  'Q.......',\n",
       "  '.......Q',\n",
       "  '.Q......',\n",
       "  '....Q...',\n",
       "  '..Q.....'],\n",
       " ['.....Q..',\n",
       "  '.......Q',\n",
       "  '.Q......',\n",
       "  '...Q....',\n",
       "  'Q.......',\n",
       "  '......Q.',\n",
       "  '....Q...',\n",
       "  '..Q.....'],\n",
       " ['......Q.',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  '...Q....',\n",
       "  '.Q......',\n",
       "  '....Q...'],\n",
       " ['......Q.',\n",
       "  '.Q......',\n",
       "  '...Q....',\n",
       "  'Q.......',\n",
       "  '.......Q',\n",
       "  '....Q...',\n",
       "  '..Q.....',\n",
       "  '.....Q..'],\n",
       " ['......Q.',\n",
       "  '.Q......',\n",
       "  '.....Q..',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '...Q....',\n",
       "  '.......Q',\n",
       "  '....Q...'],\n",
       " ['......Q.',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  '....Q...',\n",
       "  '.Q......',\n",
       "  '...Q....'],\n",
       " ['......Q.',\n",
       "  '..Q.....',\n",
       "  '.......Q',\n",
       "  '.Q......',\n",
       "  '....Q...',\n",
       "  'Q.......',\n",
       "  '.....Q..',\n",
       "  '...Q....'],\n",
       " ['......Q.',\n",
       "  '...Q....',\n",
       "  '.Q......',\n",
       "  '....Q...',\n",
       "  '.......Q',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '.....Q..'],\n",
       " ['......Q.',\n",
       "  '...Q....',\n",
       "  '.Q......',\n",
       "  '.......Q',\n",
       "  '.....Q..',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '....Q...'],\n",
       " ['......Q.',\n",
       "  '....Q...',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '.....Q..',\n",
       "  '.......Q',\n",
       "  '.Q......',\n",
       "  '...Q....'],\n",
       " ['.......Q',\n",
       "  '.Q......',\n",
       "  '...Q....',\n",
       "  'Q.......',\n",
       "  '......Q.',\n",
       "  '....Q...',\n",
       "  '..Q.....',\n",
       "  '.....Q..'],\n",
       " ['.......Q',\n",
       "  '.Q......',\n",
       "  '....Q...',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '......Q.',\n",
       "  '...Q....',\n",
       "  '.....Q..'],\n",
       " ['.......Q',\n",
       "  '..Q.....',\n",
       "  'Q.......',\n",
       "  '.....Q..',\n",
       "  '.Q......',\n",
       "  '....Q...',\n",
       "  '......Q.',\n",
       "  '...Q....'],\n",
       " ['.......Q',\n",
       "  '...Q....',\n",
       "  'Q.......',\n",
       "  '..Q.....',\n",
       "  '.....Q..',\n",
       "  '.Q......',\n",
       "  '......Q.',\n",
       "  '....Q...']]"
      ]
     },
     "execution_count": 259,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.solveNQueens(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sqrt(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implement int sqrt(int x).\n",
    "\n",
    "Compute and return the square root of x."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 292,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def mySqrt(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # x=0\n",
    "        if x==0:\n",
    "            return 0\n",
    "        # binary search among numbers<x\n",
    "        begin=1\n",
    "        end=x\n",
    "        while begin<=end:\n",
    "            midpoint=(begin+end)/2\n",
    "            if midpoint**2==x:\n",
    "                return midpoint\n",
    "            elif midpoint**2>x:\n",
    "                end=midpoint-1\n",
    "            elif midpoint**2<x:\n",
    "                begin=midpoint+1\n",
    "                \n",
    "        return end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 294,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 294,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.mySqrt(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Super Pow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Your task is to calculate $a^b$ mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.\n",
    "\n",
    "Example1:\n",
    "\n",
    "a = 2\n",
    "b = [3]\n",
    "\n",
    "Result: 8\n",
    "\n",
    "Example2:\n",
    "\n",
    "a = 2\n",
    "b = [1,0]\n",
    "\n",
    "Result: 1024"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 295,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 295,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum([1,2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Find K Pairs with Smallest Sums"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer $k$.\n",
    "\n",
    "Define a pair $(u,v)$ which consists of one element from the first array and one element from the second array.\n",
    "\n",
    "Find the k pairs $(u_1,v_1),(u_2,v_2) ...(u_k,v_k)$ with the smallest sums."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Merge Sorted Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.\n",
    "\n",
    "Note:\n",
    "You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: This is part of mergesort."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 462,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "#     def merge(self, nums1, m, nums2, n):\n",
    "    \n",
    "       \n",
    "#         i = m-1\n",
    "#         j = n-1\n",
    "#         k = m+n-1\n",
    "        \n",
    "#         while(i >= 0 and j >= 0):\n",
    "#             if nums1[i] > nums2[j]:\n",
    "#                 nums1[k] = nums1[i]\n",
    "#                 k -= 1\n",
    "#                 i -= 1\n",
    "#             else:\n",
    "#                 nums1[k] = nums2[j]\n",
    "#                 k -= 1\n",
    "#                 j -= 1\n",
    "#         while(j >= 0):\n",
    "#             nums1[k] = nums2[j]\n",
    "#             k -= 1\n",
    "#             j -= 1\n",
    "    def merge(self, nums1, m, nums2, n):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type m: int\n",
    "        :type nums2: List[int]\n",
    "        :type n: int\n",
    "        :rtype: void Do not return anything, modify nums1 in-place instead.\n",
    "        \"\"\"\n",
    "            \n",
    "        # merge left and right sublist\n",
    "        i=0\n",
    "        j=0\n",
    "        inserted=0\n",
    "        while j<n:\n",
    "            if(i>=m):\n",
    "                nums1.insert(inserted+i,nums2[j])\n",
    "                inserted+=1\n",
    "                j+=1\n",
    "            elif(nums1[inserted+i]<nums2[j]):\n",
    "                i+=1\n",
    "            else:\n",
    "                nums1.insert(inserted+i,nums2[j])\n",
    "                inserted+=1\n",
    "                j+=1\n",
    "        while len(nums1)>m+n:\n",
    "            nums1.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 463,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1]"
      ]
     },
     "execution_count": 463,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "nums1=[0]\n",
    "nums2=[1]\n",
    "o.merge(nums1,0,nums2,1)\n",
    "nums1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Valid Palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.\n",
    "\n",
    "For example,\n",
    "\"A man, a plan, a canal: Panama\" is a palindrome.\n",
    "\"race a car\" is not a palindrome.\n",
    "\n",
    "Note:\n",
    "Have you consider that the string might be empty? This is a good question to ask during an interview.\n",
    "\n",
    "For the purpose of this problem, we define empty string as valid palindrome."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We could identify Palindrome by a deque. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 493,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        import re\n",
    "        str_list=list(s.lower())\n",
    "        r = re.compile('[a-z0-9]+')\n",
    "        str_list=filter(r.match,str_list)\n",
    "        while len(str_list)>1:\n",
    "            if(str_list.pop()!=str_list.pop(0)):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 494,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 494,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.isPalindrome(\"Ab,2s2ba.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is probably because we do not need to convert string to list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 506,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        import re\n",
    "        s=s.lower()\n",
    "        r = re.compile('[a-z0-9]+')\n",
    "        s=filter(r.match,s)\n",
    "        while len(s)>1:\n",
    "            if(s[len(s)-1]!=s[0]):\n",
    "                return False\n",
    "            s=s[1:len(s)-1]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 507,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 507,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.isPalindrome(\"Ab,2s2ba.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This improves a little bit. But let me consider the two pointer method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 510,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        import re\n",
    "        s=s.lower()\n",
    "        r = re.compile('[a-z0-9]+')\n",
    "        s=filter(r.match,s)\n",
    "        p1=0\n",
    "        p2=len(s)-1\n",
    "        while p1<=p2:\n",
    "            if(s[p1]!=s[p2]):\n",
    "                return False\n",
    "            p1+=1\n",
    "            p2-=1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 511,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 511,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.isPalindrome(\"Ab,2s2ba.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Shortest Palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.\n",
    "\n",
    "For example:\n",
    "\n",
    "Given \"aacecaaa\", return \"aaacecaaa\".\n",
    "\n",
    "Given \"abcd\", return \"dcbabcd\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Naive solution: linear search to find the longest from the start of the string, then add at the front the reverse of the remaining part of the string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 549,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def shortestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        max_index=0\n",
    "        index=0\n",
    "        while index<len(s):\n",
    "            if self.isPalindrome(s[:index+1]):\n",
    "                max_index=index\n",
    "            index+=1\n",
    "        return s[max_index+1:][::-1]+s\n",
    "        \n",
    "    def isPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        import re\n",
    "        s=s.lower()\n",
    "        r = re.compile('[a-z0-9]+')\n",
    "        s=filter(r.match,s)\n",
    "        p1=0\n",
    "        p2=len(s)-1\n",
    "        while p1<=p2:\n",
    "            if(s[p1]!=s[p2]):\n",
    "                return False\n",
    "            p1+=1\n",
    "            p2-=1\n",
    "        return True   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 548,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 548,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.shortestPalindrome(\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No wonder, the above solution exceeds the time limit. Is there an alternative strategy without using isPalindrome? One way is to reverse the string and check s[:n-i] with newS[i:]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 566,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def shortestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        index=0\n",
    "        newS=s[::-1]\n",
    "        for i in xrange(len(s)):\n",
    "            if(newS[i:]==s[:len(s)-i]):\n",
    "                index=i\n",
    "                break\n",
    "        return newS[:index]+s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 560,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'dcbabcd'"
      ]
     },
     "execution_count": 560,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.shortestPalindrome(\"abcd\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We could further improve the above without reversing s as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 592,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def shortestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        index=0\n",
    "        n=len(s)\n",
    "        for i in xrange(n):\n",
    "            if(s[:n-i]==s[-(i+1):-n-1:-1]):\n",
    "                index=i\n",
    "                break\n",
    "        return s[-1:-index-1:-1]+s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 594,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'dcbabcd'"
      ]
     },
     "execution_count": 594,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.shortestPalindrome(\"abcd\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It still exceed time limit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Longest Palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.\n",
    "\n",
    "This is case sensitive, for example \"Aa\" is not considered a palindrome here.\n",
    "\n",
    "Note:\n",
    "Assume the length of given string will not exceed 1,010."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Find all distinct char in the string, count their numbers. If number of a character is odd, then it can be placed at the center of the palindrome. For other odd number chars we have to discard one in each to make them even for constructing the longest palindrome."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 604,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # create a dictionary of char and counts\n",
    "        dict_ch={ch:0 for ch in set(s)}\n",
    "        # count the number of appearance of char c in s\n",
    "        for c in s:\n",
    "            if c in dict_ch.keys():\n",
    "                dict_ch[c]+=1\n",
    "        # check if char with odd counts has been used as center\n",
    "        odd_added=False\n",
    "        # length\n",
    "        length=0\n",
    "        for ch in dict_ch.keys():\n",
    "            if dict_ch[ch]%2==0:\n",
    "                length+=dict_ch[ch]\n",
    "            elif odd_added==False:\n",
    "                length+=dict_ch[ch]\n",
    "                odd_added=True\n",
    "            else:\n",
    "                length+=dict_ch[ch]-1\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 605,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 605,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.longestPalindrome(\"sdffasfd\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Tree Inorder Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a binary tree, return the inorder traversal of its nodes' values.\n",
    "\n",
    "For example:\n",
    "Given binary tree [1,null,2,3],\n",
    "\n",
    "   1\n",
    "   \n",
    "    \\\n",
    "    \n",
    "     2\n",
    "     \n",
    "    /\n",
    "    \n",
    "   3\n",
    "   \n",
    "return [1,3,2].\n",
    "\n",
    "Note: Recursive solution is trivial, could you do it iteratively?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: First we consider recursive solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 610,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "class TreeNode(object):\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def inorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return []\n",
    "        List=[]\n",
    "        if root.left!=None:\n",
    "            List=List+self.inorderTraversal(root.left)\n",
    "        List.append(root.val)\n",
    "        if root.right!=None:\n",
    "            List=List+self.inorderTraversal(root.right)\n",
    "        return List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 611,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "root=TreeNode(1)\n",
    "root.right=TreeNode(2)\n",
    "root.right.left=TreeNode(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 612,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 2]"
      ]
     },
     "execution_count": 612,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.inorderTraversal(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we consider non-iterative solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "class TreeNode(object):\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def inorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Same Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given two binary trees, write a function to check if they are equal or not.\n",
    "\n",
    "Two binary trees are considered equal if they are structurally identical and the nodes have the same value."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: To check same tree we check the node, left subtree, right subtree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 615,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "class TreeNode(object):\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def isSameTree(self, p, q):\n",
    "        \"\"\"\n",
    "        :type p: TreeNode\n",
    "        :type q: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if p==None or q==None:\n",
    "            return p==None and q==None\n",
    "        # check root\n",
    "        if p.val!=q.val:\n",
    "            return False\n",
    "        # check left subtree\n",
    "        if p.left!=None and q.left!=None:\n",
    "            leftmatch=self.isSameTree(p.left, q.left)\n",
    "        elif p.left==None and q.left==None:\n",
    "            leftmatch=True\n",
    "        else:\n",
    "            leftmatch=False\n",
    "            \n",
    "        # check right subtree\n",
    "        if p.right!=None and q.right!=None:\n",
    "            rightmatch=self.isSameTree(p.right, q.right)\n",
    "        elif p.right==None and q.right==None:\n",
    "            rightmatch=True\n",
    "        else:\n",
    "            rightmatch=False\n",
    "                    \n",
    "        return leftmatch and rightmatch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Tree Paths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a binary tree, return all root-to-leaf paths.\n",
    "\n",
    "For example, given the following binary tree:\n",
    "\n",
    "   1\n",
    "   \n",
    " /   \\\n",
    " \n",
    "2     3\n",
    "\n",
    " \\\n",
    " \n",
    "  5\n",
    "\n",
    "All root-to-leaf paths are:\n",
    "\n",
    "[\"1->2->5\", \"1->3\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We consider a recursive solution and keep track of a list of paths and a string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 616,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    # @param {TreeNode} root\n",
    "    # @return {string[]}\n",
    "    def binaryTreePaths(self, root):\n",
    "        path_list=[]\n",
    "        self._binaryTreePaths(root,'',path_list)\n",
    "        return path_list\n",
    "        \n",
    "    def _binaryTreePaths(self,root,path,path_list):\n",
    "        if root==None:\n",
    "            return\n",
    "        path+=str(root.val)\n",
    "        if root.left!=None:\n",
    "            path_left=path+'->'\n",
    "            self._binaryTreePaths(root.left,path_left,path_list)\n",
    "        if root.right!=None:\n",
    "            path_right=path+'->'\n",
    "            self._binaryTreePaths(root.right,path_right,path_list)\n",
    "        if root.left==None and root.right==None:\n",
    "            path_list.append(path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 617,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tree=TreeNode(1)\n",
    "tree.left=TreeNode(2)\n",
    "tree.left.right=TreeNode(5)\n",
    "tree.right=TreeNode(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 619,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1->2->5', '1->3']"
      ]
     },
     "execution_count": 619,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.binaryTreePaths(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Balanced Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a binary tree, determine if it is height-balanced.\n",
    "\n",
    "For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: For a balanced Binary Tree, the difference between maxdepth and mindepth should not be greater than 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 621,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def isBalanced(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.maxDepth(root)-self.minDepth(root)<2\n",
    "        \n",
    "    def maxDepth(self,root):\n",
    "        if root==None:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1+max(self.maxDepth(root.left),self.maxDepth(root.right))\n",
    "        \n",
    "    def minDepth(self,root):\n",
    "        if root==None:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1+min(self.minDepth(root.left),self.minDepth(root.right))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above code does not pass the tests. I misunderstand the problem. we should compare **the depth of the two subtrees instead of all the leafs**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 624,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def isBalanced(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return True\n",
    "        balance=abs(self.gotDepth(root.left)-self.gotDepth(root.right))<2\n",
    "        return balance and (self.isBalanced(root.left) and self.isBalanced(root.right))\n",
    "    \n",
    "    #gotdepth of a subtree start from a root\n",
    "    def gotDepth(self,root):\n",
    "        if root==None:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1+max(self.gotDepth(root.left),self.gotDepth(root.right))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Symmetric Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).\n",
    "\n",
    "For example, this binary tree [1,2,2,3,4,4,3] is symmetric:\n",
    "\n",
    "But the following [1,2,2,null,3,null,3] is not:\n",
    "\n",
    "Note:\n",
    "Bonus points if you could solve it both recursively and iteratively."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Let me first consider recursive method. We consider modification to same tree method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 625,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def isSymmetric(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return True\n",
    "        return self._isSymmetric(root.left,root.right)\n",
    "        \n",
    "    def _isSymmetric(self,p,q):\n",
    "        if p==None or q==None:\n",
    "            return p==None and q==None\n",
    "        # check root\n",
    "        if p.val!=q.val:\n",
    "            return False\n",
    "        # check p.left and q.right\n",
    "        if p.left!=None and q.right!=None:\n",
    "            match1=self._isSymmetric(p.left, q.right)\n",
    "        elif p.left==None and q.right==None:\n",
    "            match1=True\n",
    "        else:\n",
    "            match1=False\n",
    "            \n",
    "        # check p.right and q.left\n",
    "        if p.right!=None and q.left!=None:\n",
    "            match2=self._isSymmetric(p.right, q.left)\n",
    "        elif p.right==None and q.left==None:\n",
    "            match2=True\n",
    "        else:\n",
    "            match2=False\n",
    "                    \n",
    "        return match1 and match2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next consider iterative method."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Tree Level Order Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).\n",
    "\n",
    "For example:\n",
    "Given binary tree [3,9,20,null,null,15,7],\n",
    "\n",
    "    3\n",
    "    \n",
    "   / \\\n",
    "   \n",
    "  9  20\n",
    "  \n",
    "    /  \\\n",
    "    \n",
    "   15   7\n",
    "   \n",
    "return its level order traversal as:\n",
    "[\n",
    "  [3],\n",
    "  [9,20],\n",
    "  [15,7]\n",
    "]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The algorithm is similar to bfs. The only difference is we need to keep track of the level."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def levelOrder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        level=0\n",
    "        nodes_list=[]\n",
    "        if root==None:\n",
    "            return nodes_list\n",
    "        alist=[root]\n",
    "        nodes_list.append(alist)\n",
    "        while True:\n",
    "            alist=[]\n",
    "            for node in nodes_list[level]:\n",
    "                if node.left!=None:\n",
    "                    alist.append(node.left)\n",
    "                if node.right!=None:\n",
    "                    alist.append(node.right)\n",
    "            level+=1\n",
    "            if len(alist)>0:\n",
    "                nodes_list.append(alist)\n",
    "            else:\n",
    "                break\n",
    "            \n",
    "        # convert nodes_list to node_val list\n",
    "        node_val_list=[]\n",
    "        for level_list in nodes_list:\n",
    "            val_list=[e.val for e in level_list]\n",
    "            node_val_list.append(val_list)\n",
    "            \n",
    "        return node_val_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 629,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[]]"
      ]
     },
     "execution_count": 629,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "level_list=[]\n",
    "level_list.insert(0,[])\n",
    "level_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 633,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1], [2]]"
      ]
     },
     "execution_count": 633,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=[[1],[2]]\n",
    "for e in a:\n",
    "    e=[3]\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Tree Level Order Traversal II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).\n",
    "\n",
    "For example:\n",
    "Given binary tree [3,9,20,null,null,15,7],\n",
    "\n",
    "    3\n",
    "    \n",
    "   / \\\n",
    "   \n",
    "  9  20\n",
    "  \n",
    "    /  \\\n",
    "    \n",
    "   15   7\n",
    "   \n",
    "return its bottom-up level order traversal as:\n",
    "\n",
    "[\n",
    "  [15,7],\n",
    "  [9,20],\n",
    "  [3]\n",
    "]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The trivial solution is to reverse the list in level order traversal from root to leaf."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def levelOrderBottom(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        level=0\n",
    "        nodes_list=[]\n",
    "        if root==None:\n",
    "            return nodes_list\n",
    "        alist=[root]\n",
    "        nodes_list.append(alist)\n",
    "        while True:\n",
    "            alist=[]\n",
    "            for node in nodes_list[level]:\n",
    "                if node.left!=None:\n",
    "                    alist.append(node.left)\n",
    "                if node.right!=None:\n",
    "                    alist.append(node.right)\n",
    "            level+=1\n",
    "            if len(alist)>0:\n",
    "                nodes_list.append(alist)\n",
    "            else:\n",
    "                break\n",
    "            \n",
    "        # convert nodes_list to node_val list\n",
    "        node_val_list=[]\n",
    "        for level_list in reversed(nodes_list):\n",
    "            val_list=[e.val for e in level_list]\n",
    "            node_val_list.append(val_list)\n",
    "            \n",
    "        return node_val_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Tree Zigzag Level Order Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).\n",
    "\n",
    "For example:\n",
    "Given binary tree [3,9,20,null,null,15,7],\n",
    "\n",
    "    3\n",
    "    \n",
    "   / \\\n",
    "   \n",
    "  9  20\n",
    "  \n",
    "    /  \\\n",
    "    \n",
    "   15   7\n",
    "   \n",
    "return its zigzag level order traversal as:\n",
    "\n",
    "[\n",
    "  [3],\n",
    "  [20,9],\n",
    "  [15,7]\n",
    "]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: we could solve this problem by a variation of the level order traversal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 635,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def zigzagLevelOrder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        level=0\n",
    "        nodes_list=[]\n",
    "        if root==None:\n",
    "            return nodes_list\n",
    "        alist=[root]\n",
    "        nodes_list.append(alist)\n",
    "        while True:\n",
    "            alist=[]\n",
    "            level+=1\n",
    "            if level%2==0:\n",
    "                for node in reversed(nodes_list[level-1]):\n",
    "                    if node.left!=None:\n",
    "                        alist.append(node.left)\n",
    "                    if node.right!=None:\n",
    "                        alist.append(node.right)\n",
    "            else:\n",
    "                for node in reversed(nodes_list[level-1]):\n",
    "                    if node.right!=None:\n",
    "                        alist.append(node.right)\n",
    "                    if node.left!=None:\n",
    "                        alist.append(node.left)\n",
    "                        \n",
    "            if len(alist)>0:\n",
    "                nodes_list.append(alist)\n",
    "            else:\n",
    "                break\n",
    "            \n",
    "        # convert nodes_list to node_val list\n",
    "        node_val_list=[]\n",
    "        for level_list in nodes_list:\n",
    "            val_list=[e.val for e in level_list]\n",
    "            node_val_list.append(val_list)\n",
    "            \n",
    "        return node_val_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Minimum Depth of Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a binary tree, find its minimum depth.\n",
    "\n",
    "The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Notice that if there is only one branch coming out of a root we should move on until we find the leaf node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def minDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return 0\n",
    "        if root.left!=None and root.right!=None:\n",
    "            return 1+min(self.minDepth(root.left),self.minDepth(root.right))\n",
    "        elif root.left!=None:\n",
    "            return 1+self.minDepth(root.left)\n",
    "        elif root.right!=None:\n",
    "            return 1+self.minDepth(root.right)\n",
    "        else:\n",
    "            return 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=red>Invert Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Invert a binary tree.\n",
    "\n",
    "     4\n",
    "     \n",
    "   /   \\\n",
    "   \n",
    "  2     7\n",
    "  \n",
    " / \\   / \\\n",
    " \n",
    "1   3 6   9\n",
    "\n",
    "to\n",
    "\n",
    "     4\n",
    "     \n",
    "   /   \\\n",
    "   \n",
    "  7     2\n",
    "  \n",
    " / \\   / \\\n",
    " \n",
    "9   6 3   1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We apply similar methodology in Symmetric Tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 637,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def invertTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return None\n",
    "        invert_root=TreeNode(root.val)\n",
    "        self._invertTree(root,invert_root)\n",
    "        \n",
    "        return invert_root\n",
    "        \n",
    "    def _invertTree(self,p,q):\n",
    "        # root\n",
    "        q.val=p.val\n",
    "        \n",
    "        # check p.left\n",
    "        if p.left!=None:\n",
    "            q.right=TreeNode(p.left.val)\n",
    "            self._invertTree(p.left, q.right)\n",
    "        else:\n",
    "            q.right=None\n",
    "            \n",
    "        # check p.right\n",
    "        if p.right!=None:\n",
    "            q.left=TreeNode(p.right.val)\n",
    "            self._invertTree(p.right, q.left)\n",
    "        else:\n",
    "            q.left=None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Convert Sorted Array to Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array where elements are sorted in ascending order, convert it to a height balanced BST."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Since we are converting a list. We should always have access to sublists. Our algorithm should work as follows:\n",
    "\n",
    "1. insert middle into root node\n",
    "2. create left subtree from the left sublist\n",
    "3. create right subtree from the right sublist\n",
    "4. recurse until sublist is empty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 639,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def sortedArrayToBST(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        return self._sortedArrayToBST(None,nums)\n",
    "        \n",
    "    def _sortedArrayToBST(self,root,nums):\n",
    "        if nums==[]:\n",
    "            return None\n",
    "        start=0\n",
    "        end=len(nums)-1\n",
    "        mid=(start+end)/2\n",
    "        root=TreeNode(nums[mid])\n",
    "        root.left=self._sortedArrayToBST(root.left,nums[:mid])\n",
    "        root.right=self._sortedArrayToBST(root.right,nums[mid+1:])\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Convert Sorted List to Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: In this case, a trivial solution is to convert the sorted linked list into an array. But a more direct approach is two use two pointers: one fast and one slow. I will focus on the second approach."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 643,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "# class ListNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def sortedListToBST(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        root=self._sortedListToBST(head,None)\n",
    "        return root\n",
    "        \n",
    "    def _sortedListToBST(self,head,tail):\n",
    "        if head==tail:\n",
    "            return None\n",
    "        #initialize fast and slow pointer nodes\n",
    "        fast=slow=head\n",
    "        while fast!=tail and fast.next!=tail:\n",
    "            slow=slow.next\n",
    "            fast=fast.next.next\n",
    "        root=TreeNode(slow.val)\n",
    "        root.left=self._sortedListToBST(head,slow)\n",
    "        root.right=self._sortedListToBST(slow.next,tail)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The time complexity is analyzed as\n",
    "\n",
    "(n+n/2)+2*1/2(n+n/2)+4*1/4(n+n/2)+...n*1/n*(n+n/2)\n",
    "\n",
    "which contains log n terms and as a result gives O(n log n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lowest Common Ancestor of a Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.\n",
    "\n",
    "According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”\n",
    "\n",
    "        _______6______\n",
    "       /              \\\n",
    "    ___2__          ___8__\n",
    "   /      \\        /      \\\n",
    "   0      _4       7       9\n",
    "         /  \\\n",
    "         3   5\n",
    "\n",
    "\n",
    "For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: A naive solution is to check every subtree whether it contains the two node. An alternative solution is as follows: For any node r\n",
    "\n",
    "1. If p is on one side and q is on the other, r is the first common ancestor.\n",
    "2. Else, the first common ancestor is on the left or right side"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 644,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def lowestCommonAncestor(self, root, p, q):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type p: TreeNode\n",
    "        :type q: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if root==p or root==q:\n",
    "            return root\n",
    "        ret_left=self.covers(root.left,p,q)\n",
    "        if ret_left==0:\n",
    "            return self.lowestCommonAncestor(root.right, p, q)\n",
    "        elif ret_left==1:\n",
    "            return root\n",
    "        else:\n",
    "            return self.lowestCommonAncestor(root.left, p, q)\n",
    "    \n",
    "    # check if p and q is in the subtree\n",
    "    def covers(self,root,p,q):\n",
    "        ret=0\n",
    "        if root==None:\n",
    "            return ret\n",
    "        if root==p or root==q:\n",
    "            ret+=1\n",
    "        ret+=self.covers(root.left,p,q)\n",
    "        if ret==2:\n",
    "            return ret\n",
    "        ret+=self.covers(root.right,p,q)\n",
    "        \n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sum of left leaves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find the sum of all left leaves in a given binary tree.\n",
    "\n",
    "Example:\n",
    "\n",
    "    3\n",
    "    \n",
    "   / \\\n",
    "   \n",
    "  9  20\n",
    "  \n",
    "    /  \\\n",
    "    \n",
    "   15   7\n",
    "\n",
    "There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: To sum over left leaves we need to find all the left leaves. What is the condition of being a left leaf? \n",
    "\n",
    "1. No child.\n",
    "2. Left descendent of its parent.\n",
    "\n",
    "Based on these two condition, we could use recursive method to traverse all the lowest parents and their left child and then sum them up."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 788,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "class TreeNode(object):\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def sumOfLeftLeaves(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return 0\n",
    "        left_sum=0\n",
    "        if root.left!=None:\n",
    "            if root.left.left==None and root.left.right==None:\n",
    "                left_sum+=root.left.val\n",
    "            else:\n",
    "                left_sum+=self.sumOfLeftLeaves(root.left)\n",
    "        if root.right!=None:\n",
    "            left_sum+=self.sumOfLeftLeaves(root.right)\n",
    "            \n",
    "        return left_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 789,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 789,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "root=TreeNode(3)\n",
    "root.left=TreeNode(9)\n",
    "root.right=TreeNode(20)\n",
    "root.right.left=TreeNode(15)\n",
    "root.right.right=TreeNode(7)\n",
    "o.sumOfLeftLeaves(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Merge k Sorted Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: I would like to think of the problem as variation of mergesort with time complexity O(n k log k). The base problem is to merge two list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 344,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "class ListNode(object):\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution(object):\n",
    "    def mergeKLists(self, lists):\n",
    "        \"\"\"\n",
    "        :type lists: List[ListNode]\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        newlists=[]\n",
    "        for i in range(0,len(lists),2):\n",
    "            if i+1<len(lists):\n",
    "                newlists.append(self.merge2Lists(lists[i],lists[i+1]))\n",
    "            else:\n",
    "                newlists.append(lists[i])\n",
    "                \n",
    "        if len(newlists)==1:\n",
    "            return newlists[0]\n",
    "        \n",
    "        return self.mergeKLists(newlists)\n",
    "            \n",
    "    def merge2Lists(self,left,right):\n",
    "        head=merged=ListNode(-1)\n",
    "\n",
    "        while left!=None or right!=None:\n",
    "            if left==None:\n",
    "                merged.next=ListNode(right.val)\n",
    "                right=right.next\n",
    "                merged=merged.next\n",
    "            elif right==None:\n",
    "                merged.next=ListNode(left.val)\n",
    "                left=left.next\n",
    "                merged=merged.next\n",
    "            elif left.val<right.val:\n",
    "                merged.next=ListNode(left.val)\n",
    "                left=left.next\n",
    "                merged=merged.next\n",
    "            else:\n",
    "                merged.next=ListNode(right.val)\n",
    "                right=right.next\n",
    "                merged=merged.next\n",
    "                \n",
    "        return head.next      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 345,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "n1=ListNode(1)\n",
    "n1.next=ListNode(3)\n",
    "n1.next.next=ListNode(5)\n",
    "n1.next.next.next=ListNode(7)\n",
    "\n",
    "n2=ListNode(2)\n",
    "n2.next=ListNode(4)\n",
    "n2.next.next=ListNode(6)\n",
    "n2.next.next.next=ListNode(8)\n",
    "\n",
    "n3=ListNode(-7)\n",
    "n3.next=ListNode(-5)\n",
    "n3.next.next=ListNode(-3)\n",
    "n3.next.next.next=ListNode(-1)\n",
    "\n",
    "lists=[n1,n2,n3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 350,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-7\n",
      "-5\n",
      "-3\n",
      "-1\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "o=Solution()\n",
    "result=o.mergeKLists(lists)\n",
    "while result!=None:\n",
    "    print result.val\n",
    "    result=result.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It turns out that the above solution exceeds memory limit. The extra memory should come from the newlists I created. Let me improve that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 354,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "class ListNode(object):\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution(object):\n",
    "    def mergeKLists(self, lists):\n",
    "        \"\"\"\n",
    "        :type lists: List[ListNode]\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if len(lists)==0:\n",
    "            return None\n",
    "        elif len(lists)==1:\n",
    "            return lists[0]\n",
    "        elif len(lists)==2:\n",
    "            return self.merge2Lists(lists[0],lists[1])\n",
    "        else:\n",
    "            mid=len(lists)/2+1\n",
    "            return self.merge2Lists(self.mergeKLists(lists[:mid]),self.mergeKLists(lists[mid:]))\n",
    "        \n",
    "            \n",
    "    def merge2Lists(self,left,right):\n",
    "        head=merged=ListNode(-1)\n",
    "\n",
    "        while left!=None or right!=None:\n",
    "            if left==None:\n",
    "                merged.next=ListNode(right.val)\n",
    "                right=right.next\n",
    "                merged=merged.next\n",
    "            elif right==None:\n",
    "                merged.next=ListNode(left.val)\n",
    "                left=left.next\n",
    "                merged=merged.next\n",
    "            elif left.val<right.val:\n",
    "                merged.next=ListNode(left.val)\n",
    "                left=left.next\n",
    "                merged=merged.next\n",
    "            else:\n",
    "                merged.next=ListNode(right.val)\n",
    "                right=right.next\n",
    "                merged=merged.next\n",
    "                \n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 355,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "n1=ListNode(1)\n",
    "n1.next=ListNode(3)\n",
    "n1.next.next=ListNode(5)\n",
    "n1.next.next.next=ListNode(7)\n",
    "\n",
    "n2=ListNode(2)\n",
    "n2.next=ListNode(4)\n",
    "n2.next.next=ListNode(6)\n",
    "n2.next.next.next=ListNode(8)\n",
    "\n",
    "n3=ListNode(-7)\n",
    "n3.next=ListNode(-5)\n",
    "n3.next.next=ListNode(-3)\n",
    "n3.next.next.next=ListNode(-1)\n",
    "\n",
    "lists=[n1,n2,n3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 357,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-7\n",
      "-5\n",
      "-3\n",
      "-1\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "o=Solution()\n",
    "result=o.mergeKLists(lists)\n",
    "while result!=None:\n",
    "    print result.val\n",
    "    result=result.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Sum of Two Integers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.\n",
    "\n",
    "Example:\n",
    "Given a = 1 and b = 2, return 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 963,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def getSum(self, a, b):\n",
    "        \"\"\"\n",
    "        :type a: int\n",
    "        :type b: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 32 bits integer max\n",
    "        MAX = 0x7FFFFFFF\n",
    "        # 32 bits interger min\n",
    "        MIN = 0x80000000\n",
    "        # mask to get last 32 bits\n",
    "        mask = 0xFFFFFFFF\n",
    "        while b != 0:\n",
    "            # ^ get different bits and & gets double 1s, << moves carry\n",
    "            a, b = (a ^ b) & mask, ((a & b) << 1) & mask\n",
    "        # if a is negative, get a's 32 bits complement positive first\n",
    "        # then get 32-bit positive's Python complement negative\n",
    "        print ~(a ^ mask)\n",
    "        return a if a <= MAX else ~(a ^ mask)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 964,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-3\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "-3"
      ]
     },
     "execution_count": 964,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.getSum(-1,-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 737,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4294967294"
      ]
     },
     "execution_count": 737,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2**32-2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 746,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-4294967294"
      ]
     },
     "execution_count": 746,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "~(2^mask)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 776,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2147483647"
      ]
     },
     "execution_count": 776,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MAX = 0x7FFFFFFF\n",
    "MAX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 777,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2147483647"
      ]
     },
     "execution_count": 777,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2**31-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 778,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-2"
      ]
     },
     "execution_count": 778,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "~1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 56. Merge Intervals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a collection of intervals, merge all overlapping intervals.\n",
    "\n",
    "For example,\n",
    "\n",
    "Given [1,3],[2,6],[8,10],[15,18],\n",
    "\n",
    "return [1,6],[8,10],[15,18]."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We can first sort according to the start of the interval. Then we add list to our results one by one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for an interval.\n",
    "class Interval(object):\n",
    "    def __init__(self, s=0, e=0):\n",
    "        self.start = s\n",
    "        self.end = e\n",
    "\n",
    "class Solution(object):\n",
    "    def merge(self, intervals):\n",
    "        \"\"\"\n",
    "        :type intervals: List[Interval]\n",
    "        :rtype: List[Interval]\n",
    "        \"\"\"\n",
    "        def getKey(item):\n",
    "            return item.start\n",
    "        intervals=sorted(intervals, key=getKey)\n",
    "        results=[]\n",
    "        for interval in intervals:\n",
    "            if results!=[] and results[-1].end>=interval.start:\n",
    "                results[-1].end=max(interval.end,results[-1].end)\n",
    "            else:\n",
    "                results.append(interval)\n",
    "                \n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 2]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}