<file_sep>"""
>>> A = [2, 3, -2, 4]
>>> max_product(A)
6
>>> A = [-7, -4, -2, 4]
>>> max_product(A)
28
>>> A = [2, 3]
>>> max_product(A)
6
>>> A = [2, 3, 9, 4]
>>> max_product(A)
36
>>> A = [-2, -3, -2, 0]
>>> max_product(A)
6
>>> A = [-2, -10, 2, 3, -2, 4, 20]
>>> max_product(A)
80
>>> A = [0, 0, 0, 0]
>>> max_product(A)
0
"""


def max_product(A):
    if not A:
        return

    if len(A) == 1:
        return A[0]
    else:
        max_prod = None
        for ind in range(len(A)-1):
            if A[ind] <= 0:
                if A[ind+1] >= 0:
                    curr_prod = A[ind+1]
                else:
                    curr_prod = A[ind] * A[ind+1]
            else:
                curr_prod = A[ind] * A[ind+1]

            if curr_prod > max_prod:
                max_prod = curr_prod

        return max_prod

<file_sep># https://oj.leetcode.com/problems/palindrome-number/

import unittest

class Solution:
    # @return a boolean
    def isPalindrome(self, x):
      return self.isPalindromeNumeric(x)

    def isPalindromeNumeric(self, x):
      # print "\n--------------\nx:{}\n".format(x)
      i = 0
      if(x<0 or (x % 10 == 0 and x != 0)):
        return False
      while (i < x):
        i = i * 10 + x % 10
        x = x / 10
        # print "i: {0: >6}\t\tx: {1: >6}\t\ti/10: {2: >6}".format(i, x, i/10)
      return (i == x or i/10 == x)

    def isPalindromeAsStr(self, x):
      # print "-------------------------"
      if x < 0:
        return False
      elif x / 10 == 0:
        return True
      else:
        return self.isPalindromeStrRec(str(x))

    def isPalindromeStrRec(self, x):
      #print x
      l = len(x)
      if not l or l == 1:
        return True
      if x[0] ==  x[-1]:
        return self.isPalindromeStrRec(x[1:-1])
      else:
        return False

    def isPalindromeNumericFail(self, x):
        print "-------------------------"
        if x < 0:
          return False
        if x / 10 == 0:
          return True

        pow10 = 0
        tenx = x / 10
        while tenx:
          tenx = tenx / 10
          pow10 += 1
        mag = int(pow(10,pow10))
        least = x % 10
        most = x / mag
        print "%d %d %d %d %d" % (x, pow10, mag, least, most)
        if least == most:
          new_x = (x / 10) - ((mag / 10) * (x / mag))
          print "new_x = %d" % new_x
          return self.isPalindrome(new_x)
        else:
          return False

    def isPalindromeTooEasy(self, x):
        return int(str(abs(x))[::-1]) == x


class TestSolution(unittest.TestCase):


    def test_a1000021(self):
        sln = Solution()
        self.assertEqual(False, sln.isPalindrome(1000021))

    def test_a1200021(self):
        sln = Solution()
        self.assertEqual(True, sln.isPalindrome(1202021))

    def test_121(self):
        sln = Solution()
        self.assertEqual(True, sln.isPalindrome(121))

    def test_11(self):
        sln = Solution()
        self.assertEqual(True, sln.isPalindrome(11))

    def test_1(self):
        sln = Solution()
        self.assertEqual(True, sln.isPalindrome(1))

    def test_1221(self):
        sln = Solution()
        self.assertEqual(True, sln.isPalindrome(1221))

    def test_12521(self):
        sln = Solution()
        self.assertEqual(True, sln.isPalindrome(12521))

    def test_12(self):
        sln = Solution()
        self.assertEqual(False, sln.isPalindrome(12))

    def test_115(self):
        sln = Solution()
        self.assertEqual(False, sln.isPalindrome(115))

if __name__ == '__main__':
    unittest.main()
<file_sep>"""
>>> from DataStruct import Node
>>> headC = Node(4)
>>> headC.next = Node(5)
>>> headC.next.next = Node(6)
>>> headA = Node(2)
>>> headA.next = Node(3)
>>> headA.next.next = headC
>>> headB = Node(1)
>>> headB.next = Node(2)
>>> headB.next.next = Node(3)
>>> headB.next.next.next = headC
>>> intersectNode = get_intersection_node(headA, headB)
>>> print intersectNode.val
4
>>> headA.next.next = None
>>> intersectNode = get_intersection_node(headA, headB)
>>> print intersectNode
None
"""


def get_intersection_node(headA, headB):
    """ Intersection of Two Linked Lists """

    # scan through for intersection and length of each linked list
    cnt_a = 0
    cnt_b = 0
    node_a = headA
    node_b = headB

    while node_a or node_b:
        if node_a == node_b:
            return node_a

        if node_a:
            node_a = node_a.next
            cnt_a += 1

        if node_b:
            node_b = node_b.next
            cnt_b += 1

    a_leads_by = cnt_b - cnt_a

    # scan through for intersection by delaying the start through the
    # shorter linked list
    cnt_a = 0
    cnt_b = 0
    node_a = headA
    node_b = headB
    while node_a or node_b:
        if node_a == node_b:
            return node_a

        if a_leads_by > 0:
            # a leads b so have a wait
            if cnt_a >= a_leads_by and node_a:
                node_a = node_a.next

            if node_b:
                node_b = node_b.next

            cnt_a += 1
            cnt_b += 1

        else:
            # b leads a so have b wait
            if node_a:
                node_a = node_a.next

            if cnt_b >= -a_leads_by and node_b:
                node_b = node_b.next

            cnt_a += 1
            cnt_b += 1


if __name__ == "__main__":
    import doctest
    doctest.testmod()

<file_sep>"""
>>> plus_one([0])
[1]
>>> plus_one([9, 9, 9])
[1, 0, 0, 0]
"""


def plus_one(digits):
    """ Plus One """

    overflow = True
    idx = 0
    while overflow:
        idx -= 1
        if -idx > len(digits):
            digits = [1] + digits
            overflow = False
        else:
            digits[idx] += 1
            if digits[idx] > 9:
                digits[idx] = 0
            else:
                overflow = False

    return digits


if __name__ == "__main__":
    import doctest
    doctest.testmod()<file_sep>def testRemoveDuplicates():
    case_1 = [1, 1, 4, 5, 6, 6, 6]
    case_2 = [3, 9, 10]
    assert removeDuplicates(case_1) == 4
    # assert case_1 == [1, 4, 5, 6]
    assert removeDuplicates(case_2) == 3
    # assert case_2 == [3, 9, 10]


def removeDuplicates(A):
    """
    for each element in the list do
        if the current element is the same as last element in new list
            do nothing
        else
            append the current element to new list
    """
    new_list = []
    for ind, val in enumerate(A):
        if ind == 0:
            new_list.append(val)
        if ind > 0:
            if val != new_list[-1]:
                new_list.append(val)
    print(new_list)
    return(len(new_list))


def betterRemoveDuplicates(A):
    """
    """


testRemoveDuplicates()
<file_sep>import unittest

# https://oj.leetcode.com/problems/single-number/
class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        return reduce(lambda i,n: i^n, A, 0)

    def singleNumberUsingForLoop(self, A):
        i = 0
        for n in A:
            i ^= n
        return i

class TestSolution(unittest.TestCase):

    def test_one_three(self):
        sln = Solution()
        self.assertEqual(3, sln.singleNumber([1,1,2,2,3,4,4]))

    def test_two_zeros(self):
        sln = Solution()
        self.assertEqual(4, sln.singleNumber([3,3,0,1,1,0,4]))

    def test_one_zero(self):
        sln = Solution()
        self.assertEqual(0, sln.singleNumber([3,3,0,1,1,4,4]))

    def test_neg_one(self):
        sln = Solution()
        self.assertEqual(-1, sln.singleNumber([3,3,-1,1,1,4,4]))

if __name__ == '__main__':
    unittest.main()
<file_sep>"""
>>> search_range([1, 2, 4, 5, 7, 7, 7, 8, 8, 8], 8)
[7, 9]
>>> search_range([1, 2, 4, 5, 7, 7, 7, 8, 8, 8], 3)
[-1, -1]
"""


def midpoint(start, end):
    return (end-start)/2 + start


def search_range(A, target):
    """ Search for a Range """

    # find a single target
    ptr_l, ptr_r = -1, -1
    imin, imax = 0, len(A)-1
    while imax >= imin:

        ptr = midpoint(imin, imax)
        if A[ptr] == target:
            ptr_l = ptr
            ptr_r = ptr
            break
        elif A[ptr] > target:
            imax = ptr-1
        else:
            imin = ptr+1

    # search for neighboring targets if present
    if ptr_l != -1 and ptr_r != -1:
        at_beg = ptr_l == 0
        while not at_beg:
            if A[ptr_l-1] == target:
                ptr_l -= 1
            else:
                break
            at_beg = ptr_l == 0

        at_end = ptr_r == len(A)-1
        while not at_end:
            if A[ptr_r+1] == target:
                ptr_r += 1
            else:
                break
            at_end = ptr_r == len(A)-1

    return [ptr_l, ptr_r]


if __name__ == "__main__":
    import doctest
    doctest.testmod()<file_sep>"""
>>> board = ["OOO","OOO","OOO"]
>>> solve(board)
>>> print board
['OOO', 'OOO', 'OOO']
>>> print board[0]
OOO
"""


def solve(board):
    """ Surrounded Regions """
    # search for "O" on border
    # replace any neighboring "O" with "P"
    # iterate until end of perimeter
    # replace all "O" with "X"
    # replace all "P" with "O"

    # minimum size has to be 3 by 3
    m = len(board)
    if m <= 2:
        return

    n = len(board[0])
    if n <= 2:
        return

    def tag_non_enclosed(board_in, curr_x, curr_y):
        board_in[curr_x][curr_y] = "P"

        try:
            # check if you can move down
            if curr_x-1 >= 0:
                if board_in[curr_x-1][curr_y] == "O":
                    tag_non_enclosed(board_in, curr_x-1, curr_y)
        except:
            pass

        try:
            # check if you can move up
            if curr_x+1 < len(board_in):
                if board_in[curr_x+1][curr_y] == "O":
                    tag_non_enclosed(board_in, curr_x+1, curr_y)
        except:
            pass

        try:
            # check if you can move left
            if curr_y-1 >= 0:
                if board_in[curr_x][curr_y-1] == "O":
                    tag_non_enclosed(board_in, curr_x, curr_y-1)
        except:
            pass

        try:
            # check if you can move right
            if curr_y+1 < len(board_in[0]):
                if board_in[curr_x][curr_y+1] == "O":
                    tag_non_enclosed(board_in, curr_x, curr_y+1)
        except:
            pass

    m_border = range(0, m)
    n_border = range(0, n)
    mn_border = [0, m-1, n-1, 0]

    board[:] = [list(a) for a in board]

    for border, mn_val in enumerate(mn_border):
        # iterate on top, right, bottom, left border
        along_m = border % 2 != 0
        if along_m:
            x = mn_val
            for y in n_border:
                if board[x][y] == "O":
                    tag_non_enclosed(board, x, y)
        else:
            y = mn_val
            for x in m_border:
                if board[x][y] == "O":
                    tag_non_enclosed(board, x, y)

    for m_ind in range(m):
        for n_ind in range(n):
            if board[m_ind][n_ind] == "O":
                board[m_ind][n_ind] = "X"
            elif board[m_ind][n_ind] == "P":
                board[m_ind][n_ind] = "O"

    board[:] = ["".join(a) for a in board]

<file_sep>"""
>>> from DataStruct import Node
>>> head = Node(1)
>>> head.next = Node(2)
>>> head.next.next = Node(3)
>>> head.next.next.next = Node(4)
>>> head.next.next.next.next = Node(5)
>>> head = remove_nth_from_end(head, 5)
>>> print head.val, head.next.val, head.next.next.val, head.next.next.next.val
"""


def remove_nth_from_end(head, n):
    """ Remove Nth Node From the End of List """

    if head is None:
        return

    cnt = 0
    node_del = head
    node_search = head
    while node_search.next is not None:
        node_search = node_search.next
        if cnt == n:
            node_del = node_del.next
        else:
            cnt += 1

    if cnt == n:
        node_del.next = node_del.next.next
    else:
        head = head.next

    return head<file_sep>"""
>>> from DataStruct import TreeNode
>>> root = TreeNode(2)
>>> root.left = TreeNode(4)
>>> root.right = TreeNode(7)
>>> root.left.left = TreeNode(5)
>>> root.left.right = TreeNode(8)
>>> root.right.left = TreeNode(1)
>>> has_path_sum(root, 22)
False
>>> has_path_sum(root, 10)
True
"""


def has_path_sum(root, sum):
    """ Path Sum """

    if not root:
        return False

    next_sum = sum - root.val
    if not root.left and not root.right:
        return sum-root.val == 0

    if root.left and root.right:
        return has_path_sum(root.left, next_sum) or \
               has_path_sum(root.right, next_sum)
    elif root.left:
        return has_path_sum(root.left, next_sum)
    else:
        return has_path_sum(root.right, next_sum)<file_sep># Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a boolean
    def isSymmetric(self, root):
        """
        BFS: in each level, do comparison on the list of node values with its .reverse()
        """
        # special case of {}
        if root is None:
            return True

        reached_bottom = False
        current_nodes = [root]
        current_nodes_vals = [root.val]

        while reached_bottom is False:
            current_nodes_vals_reverse = current_nodes_vals[:]
            current_nodes_vals_reverse.reverse()
            if current_nodes_vals_reverse != current_nodes_vals:
                return False

            # update next nodes and vals
            next_nodes = []
            next_nodes_vals = []
            for node in current_nodes:
                if node.left is not None:
                    next_nodes.append(node.left)
                    next_nodes_vals.append(node.left.val)
                else:
                    next_nodes_vals.append(None)
                if node.right is not None:
                    next_nodes.append(node.right)
                    next_nodes_vals.append(node.right.val)
                else:
                    next_nodes_vals.append(None)
            current_nodes = next_nodes[:]
            current_nodes_vals = next_nodes_vals[:]
            if len(current_nodes) == 0:
                reached_bottom = True
        return True
<file_sep>class Solution:
    # @param root, a tree node
    # @return an integer

    def minDepth(self, root):
        if root is None:
            return 0
        if root.left is None and root.right is None:
            return 1
        elif root.right is None:
            return 1 + self.minDepth(root.left)
        elif root.left is None:
            return 1 + self.minDepth(root.right)
        else:
            return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
<file_sep>"""
>>> is_palindrome("aA")
True
>>> is_palindrome("1aA2")
False
>>> is_palindrome("ra c,e.c:ar")
True
"""


def is_palindrome(s):
    """ Is Valid Palindrome """

    if s is None:
        return True

    m = 0
    n = len(s)-1
    while m < n:
        while not s[m].isalnum():
            m += 1
            if m > n:
                return True

        while not s[n].isalnum():
            n -= 1
            if m > n:
                return True

        if s[m].lower() != s[n].lower():
            return False

        m += 1
        n -= 1

    return True

<file_sep>"""
>>> from DataStruct import Node
>>> head = Node(1)
>>> head.next = Node(2)
>>> head.next.next = Node(3)
>>> head.next.next.next = Node(4)
>>> head.next.next.next.next = Node(5)
>>> head = rotate_right(head, 5)
>>> print head.val, head.next.val, head.next.next.val, head.next.next.next.val, head.next.next.next.next.val
"""


def rotate_right(head, k):
    if head is None:
        return

    node_tail = head
    node_new_tail = head
    cnt = 0
    len = 0

    while node_tail.next is not None:
        node_tail = node_tail.next
        if cnt == k:
            node_new_tail = node_new_tail.next
        else:
            cnt += 1
        len += 1

    if cnt != len:
        node_tail.next = head
        new_head = node_new_tail.next
        node_new_tail.next = None
        head = new_head

    return head<file_sep>"""
>>> grid = [[0, 0, 0],
...         [0, 1, 0],
...         [0, 0, 0]]
>>> unique_paths_with_obstacles(grid)
2
"""

memo = {}


def unique_paths_with_obstacles(obstacle_grid):
    """ Unique Paths With Obstacles """

    def unique_paths(m, n):

        if obstacle_grid[m-1][n-1] == 1:
            return 0

        if m == 1 and n == 1:
            return 1

        if m == 1:
            if (m, n-1) not in memo:
                memo[(m, n-1)] = unique_paths(m, n-1)
            return memo[(m, n-1)]
        elif n == 1:
            if (m-1, n) not in memo:
                memo[(m-1, n)] = unique_paths(m-1, n)
            return memo[(m-1, n)]
        else:
            if (m, n-1) not in memo:
                memo[(m, n-1)] = unique_paths(m, n-1)

            if (m-1, n) not in memo:
                memo[(m-1, n)] = unique_paths(m-1, n)

            return memo[(m, n-1)] + memo[(m-1, n)]

    m_grid, n_grid = len(obstacle_grid), len(obstacle_grid[0])
    return unique_paths(m_grid, n_grid)

<file_sep>"""
>>> from DataStruct import Node
>>> head = Node(1)
>>> head.next = Node(1)
>>> head.next.next = Node(2)
>>> head.next.next.next = Node(3)
>>> head.next.next.next.next = Node(3)
>>> head = delete_duplicates(head)
>>> print head.val, head.next.val, head.next.next.val, head.next.next.next
1 2 3 None
"""


def delete_duplicates(head):
    """ Remove Duplicates from Sorted List """

    if not head:
        return

    curr_head = head
    search = head
    while search:
        if curr_head.val != search.val:
            curr_head.next = search
            curr_head = search
        search = search.next

    curr_head.next = None
    return head<file_sep>"""
>>> add_binary("0","0")
'0'
>>> add_binary("0","1")
'1'
>>> add_binary("1","0")
'1'
>>> add_binary("1","1")
'10'
>>> add_binary("1010","101")
'1111'
>>> add_binary("1111","1")
'10000'
"""


def add_binary(a, b):
    """ Add Binary """

    a_len = len(a)
    b_len = len(b)

    offset = a_len - b_len

    max_len = a_len
    if offset > 0:
        b = "0"*offset + b
        max_len = a_len
    elif offset < 0:
        a = "0"*-offset + a
        max_len = b_len

    carryover = 0
    c = ""
    for idx in range(max_len):
        rev_idx = max_len - idx - 1
        a_val = a[rev_idx]
        b_val = b[rev_idx]
        if a_val == "1" and b_val == "1":
            if carryover == 1:
                c = "1" + c
            else:
                c = "0" + c
            carryover = 1
        elif (a_val == "1" and b_val == "0") or \
             (a_val == "0" and b_val == "1"):
            if carryover == 1:
                c = "0" + c
                carryover = 1
            else:
                c = "1" + c
                carryover = 0
        else:
            if carryover == 1:
                c = "1" + c
                carryover = 0
            else:
                c = "0" + c

    if carryover == 1:
        c = "1" + c

    return c<file_sep>"""
>>> stack = MinStack()
>>> stack.push(5)
>>> stack.push(1)
>>> stack.push(2)
>>> stack.push(3)
>>> stack.push(7)
>>> stack.push(4)
>>> stack.top()
4
>>> stack.pop()
>>> stack.top()
7
>>> stack.get_min()
1
>>> stack.pop()
>>> stack.get_min()
1
>>> stack.pop()
>>> stack.get_min()
1
>>> stack.pop()
>>> stack.get_min()
1
>>> stack.pop()
>>> stack.get_min()
5
"""


class MinStack(object):
    """ Min Stack """

    def __init__(self):
        self.__my_list = []
        self.__min_list = []

    def push(self, x):
        self.__my_list.append(x)
        if not self.__min_list or x <= self.__min_list[-1]:
            self.__min_list.append(x)

    def pop(self):
        if self.__my_list:
            val = self.__my_list.pop()
            if val == self.get_min():
                self.__min_list.pop()

    def top(self):
        return self.__my_list[-1]

    def get_min(self):
        return self.__min_list[-1]<file_sep>__author__ = 'aouyang1'

import unittest
from DataStruct import StackClass, sort_stack

# run nosetests in the terminal


class TestStack(unittest.TestCase):

    def test_stack(self):
        s = StackClass()

        self.assertEqual(s.is_empty(), True)
        s.push(4)
        s.push('dog')
        self.assertEqual(s.peek(), 'dog')
        s.push(True)
        self.assertEqual(s.size(), 3)
        self.assertEqual(s.is_empty(), False)
        s.push(8.4)
        self.assertEqual(s.pop(), 8.4)
        self.assertEqual(s.pop(), True)
        self.assertEqual(s.size(), 2)

    def test_min(self):
        s = StackClass()
        num_list = [1, 2, 3, 4, 5]
        for val in num_list:
            s.push(val)

        self.assertEqual(s.min(), 1)

        s = StackClass()
        num_list = [5, 4, 3, 2, 1, 2, 3, 4, 5]
        for val in num_list:
            s.push(val)

        self.assertEqual(s.min(), 1)

        s.pop()
        self.assertEqual(s.min(), 1)

        s.pop()
        self.assertEqual(s.min(), 1)

        s.pop()
        self.assertEqual(s.min(), 1)

        s.pop()
        self.assertEqual(s.min(), 1)

        s.pop()
        self.assertEqual(s.min(), 2)

        s.pop()
        self.assertEqual(s.min(), 3)

    def test_sort_stack(self):
        s1 = StackClass()
        num_list = [5, 7, 2, 4, 9, 1, 3, 6]
        for val in num_list:
            s1.push(val)

        s1 = sort_stack(s1=s1)

        num_list = sorted(num_list, reverse=True)

        for val in num_list:
            self.assertEqual(s1.pop(), val)
<file_sep>"""
>>> generate(5)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
"""


def generate(num_rows):
    """ Pascal's Triangle """

    tri = []
    for i in range(num_rows):
        if i == 0:
            tri.append([1])
        elif i == 1:
            tri.append(tri[i-1] + [1])
        else:
            prev_tri = tri[i-1]
            new_tri = [1]
            for k in range(len(prev_tri)-1):
                new_tri.append(prev_tri[k] + prev_tri[k+1])
            new_tri.append(1)
            tri.append(new_tri)

    return tri


if __name__ == "__main__":
    import doctest
    doctest.testmod()<file_sep># https://oj.leetcode.com/problems/implement-strstr/

import unittest

class Solution:
    # @param haystack, a string
    # @param needle, a string
    # @return an integer
    def strStr(self, haystack, needle, depth=0):
        # print "{} in {} ? d={}".format(needle,haystack,depth)
        if not len(needle):
            return 0
        if not len(haystack):
            return -1
        if len(haystack) < len(needle):
            return -1
        if haystack[:len(needle)] == needle:
            return depth
        else:
            return self.strStr(haystack[1:], needle, depth+1)


    def strStrSlowWithHelperMethod(self, haystack, needle):
        for i in range(len(haystack)):
            if self.starts_with(haystack[i:], needle):
                return i
        if len(haystack) == 0:
            if len(needle) == 0:
                return 0
        return -1

    def starts_with(self, full, prefix):
        f_len = len(full)
        p_len = len(prefix)
        if f_len < p_len:
            return False
        # print "Full: {}, Prefix: {}".format(full, prefix)
        for i in range(p_len):
            if full[i] != prefix[i]:
                return False
        return True

    def strStrBrute(self, haystack, needle):
        h_len = len(haystack)
        n_len = len(needle)
        if not n_len:
            return 0
        if h_len < n_len:
            return -1

        # print "Full: {} ({}), Prefix: {} ({})".format(haystack, h_len, needle, n_len)
        for i in range(h_len):
            for j in range(n_len):
                # print "h[{}]:n[{}] {}:{}".format(i+j, j, haystack[i+j], needle[j])                
                if i + n_len > h_len :
                    return -1 
                if haystack[i+j] == needle[j]:
                    if j == n_len-1:
                        return i
                    next
                else:
                    break
        return -1

class TestSolution(unittest.TestCase):
    def test_01(self):
        sln = Solution()
        haystack = 'abcffoob'
        needle = 'foo'
        self.assertEqual(haystack.find(needle), sln.strStr(haystack, needle))

    def test_mississippi(self):
        sln = Solution()
        haystack = 'mississippi'
        needle = 'issipi'
        self.assertEqual(haystack.find(needle), sln.strStr(haystack, needle))

    def test_aaa(self):
        sln = Solution()
        haystack = 'aaa'
        needle = 'aaaa'
        self.assertEqual(haystack.find(needle), sln.strStr(haystack, needle))

    def test_a_empty(self):
        sln = Solution()
        haystack = 'a'
        needle = ''
        self.assertEqual(haystack.find(needle), sln.strStr(haystack, needle))

    def test_empty_a(self):
        sln = Solution()
        haystack = ''
        needle = 'a'
        self.assertEqual(haystack.find(needle), sln.strStr(haystack, needle))

    def test_a_a(self):
        sln = Solution()
        haystack = 'a'
        needle = 'a'
        self.assertEqual(haystack.find(needle), sln.strStr(haystack, needle))

    def test_empty_empty(self):
        sln = Solution()
        haystack = ''
        needle = ''
        self.assertEqual(haystack.find(needle), sln.strStr(haystack, needle))

if __name__ == '__main__':
    unittest.main()
<file_sep>__author__ = 'aouyang1'

import unittest
from DataStruct import QueueClass

# run nosetests in the terminal


class TestQueue(unittest.TestCase):

    def test_queue(self):
        q = QueueClass()

        q.enqueue(4)
        q.enqueue('dog')
        q.enqueue(True)
        self.assertEqual(q.size(), 3)
        self.assertEqual(q.is_empty(), False)
        q.enqueue(8.4)
        self.assertEqual(q.dequeue(), 4)
        self.assertEqual(q.dequeue(), 'dog')
        self.assertEqual(q.size(), 2)
<file_sep>"""
>>> from DataStruct import TreeNode
>>> p = TreeNode(3)
>>> p.left = TreeNode(9)
>>> p.right = TreeNode(20, left=TreeNode(15), right=TreeNode(7))
>>> q = TreeNode(3)
>>> q.left = TreeNode(9)
>>> q.right = TreeNode(20, left=TreeNode(15), right=TreeNode(7))
>>> is_same_tree(p, q)
True
>>> q = TreeNode(3)
>>> q.left = TreeNode(2)
>>> q.right = TreeNode(20, left=TreeNode(15), right=TreeNode(7))
>>> is_same_tree(p, q)
False
>>> q = TreeNode(3)
>>> q.left = TreeNode(9)
>>> q.right = TreeNode(20, left=TreeNode(15))
>>> is_same_tree(p, q)
False
"""


def is_same_tree(p, q):
    """ Same Tree """

    if not p and not q:
        return True
    else:
        if p and q:
            if p.val != q.val:
                return False
            else:
                return is_same_tree(p.left, q.left) and \
                       is_same_tree(p.right, q.right)
        else:
            return False


if __name__ == "__main__":
    import doctest
    doctest.testmod()<file_sep>"""
>>> majority_element([1, 2, 3, 4, 4, 4, 7, 2, 3])
4
"""


def majority_element(num):
    """ Majority Element """

    elem = {}
    maj_elem = num[0]
    for val in num:
        if val not in elem:
            elem[val] = 1
        else:
            elem[val] += 1
            if elem[val] > elem[maj_elem]:
                maj_elem = val

    return maj_elem


if __name__ == "__main__":
    import doctest
    doctest.testmod()<file_sep>"""
>>> title_to_number("A")
1
>>> title_to_number("Z")
26
>>> title_to_number("AA")
27
>>> title_to_number("AAA")
703
"""


def map_chr_to_int(char_in):
    return ord(char_in)-64


def title_to_number(s):
    """ Excel Sheet Column Number """

    if len(s) == 0:
        return 0

    tot_sum = map_chr_to_int(s[0])*26**(len(s)-1)
    return tot_sum + title_to_number(s[1:])


if __name__ == "__main__":
    import doctest
    doctest.testmod()<file_sep>"""
>>> is_valid("{([])([][])}")
True
>>> is_valid("{([])([]])}")
False
"""


def is_valid(s):
    """ Valid Parentheses """

    brackets = {"(": ")", "{": "}", "[": "]"}

    if len(s) % 2 == 1 or s[0] not in brackets:
        return False

    char_stack = []
    for val in s:
        if val in brackets:
            char_stack.append(val)
        elif val == brackets[char_stack[-1]]:
            char_stack.pop()
        else:
            return False

    if len(char_stack) != 0:
        return False

    return True


if __name__ == "__main__":
    import doctest
    doctest.testmod()<file_sep>class MinStack:
    """
    [1, 4, 5, 5, 7, 0, 8]
    [1, 4, 5, 5, 7, 8]
    """
    def __init__(self):
        self.__stack = []
        self.__min = []

    def push(self, x):
        self.__stack.append(x)
        if self.min_top() is not None:
            if x <= self.min_top():
                self.__min.append(x)
        else:
            self.__min.append(x)

    # @return nothing
    def pop(self):
        if self.top() == self.min_top():
            self.__min.pop()
        self.__stack.pop()

    # @return an integer
    def top(self):
        if len(self.__stack) == 0:
            return None
        else:
            return self.__stack[-1]

    def min_top(self):
        if len(self.__min) == 0:
            return None
        else:
            return self.__min[-1]

    # @return an integer
    def getMin(self):
        return self.min_top()

lol = MinStack()
<file_sep>class Solution:
    # @param root, a tree node
    # @return an integer

    def minDepth(self, root):
        if root is None:
            return 0
        if root.left is None or root.right is None:
            return 1 + self.minDepth(root.left) + self.minDepth(root.right)
        else:
            return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
<file_sep>"""
>>> remove_element([4,5,4], 4)
1
>>> remove_element([1], 1)
0
>>> remove_element([1, 4, 3, 1, 7, 2, 8, 2, 9, 3, 10, 3, 3, 3, 5], 3)
10
"""


def remove_element(a, elem):
    """ Remove Element """

    if not a:
        return

    a_len = len(a)
    a_idx = a_len-1
    for idx in range(a_len):
        if a[a_len-idx-1] == elem:
            a[a_len-idx-1], a[a_idx] = a[a_idx], a[a_len-idx-1]
            a_idx -= 1

    return a_idx+1


if __name__ == "__main__":
    import doctest
    doctest.testmod()

<file_sep>"""
>>> from DataStruct import Node
>>> head = Node(1)
>>> head.next = Node(2)
>>> head.next.next = Node(3)
>>> head.next.next.next = Node(4)
>>> head.next.next.next.next = Node(5)
>>> head = swap_pairs(head)
>>> print head.val, head.next.val, head.next.next.val, head.next.next.next.val, head.next.next.next.next.val
2 1 4 3 5
"""


def swap_pairs(head):
    """ Swap Nodes in Pairs """

    if not head:
        return

    if head.next is None:
        return head

    curr_tail = head
    curr_head = curr_tail.next
    next_head = curr_head.next

    curr_head.next = curr_tail
    curr_tail.next = next_head
    prev_node = curr_tail

    head = curr_head
    print prev_node, prev_node.next

    while prev_node.next is not None and prev_node.next.next is not None:
        curr_tail = prev_node.next
        curr_head = curr_tail.next
        next_head = curr_head.next

        prev_node.next = curr_head

        curr_head.next = curr_tail
        curr_tail.next = next_head
        prev_node = curr_tail

    return head
<file_sep>"""
>>> count_and_say(5)
'111221'
>>> count_and_say(6)
'312211'
>>> count_and_say(10)
'13211311123113112211'
"""


def count_and_say(n):
    """ Count and Say """

    num_list = [1]
    for i in range(n-1):
        curr_val = num_list[0]
        val_cnt = 0
        list_str = []
        for val in num_list:
            if val == curr_val:
                val_cnt += 1
            else:
                list_str.append(val_cnt)
                list_str.append(curr_val)
                curr_val = val
                val_cnt = 1
        list_str.append(val_cnt)
        list_str.append(curr_val)

        num_list = list_str

    return reduce(lambda x, y: x+y, map(lambda x: str(x), num_list))


if __name__ == "__main__":
    import doctest
    doctest.testmod()<file_sep>def testIsValid():
    assert isValid("(([]))") is True
    assert isValid("([]}") is False


def isValid(s):
    """
    for each char inside for loop,
        if char is an opening parenthesis:
            we push it onto our stack
        else
            we check if it is the correct closing parenthesis for
            last item in stack
            (return False if not correct)
            if correct we pop the last item in stack
    if either stack or remaining list is not empty return False
    return True
    """
    parentheses = {'(': ')', '{': '}', '[': ']'}
    s_list = list(s)
    stack = []
    for char_position in range(len(s_list)):
        char = s_list.pop(0)
        if char in parentheses:
            stack.append(char)
        else:
            if char != parentheses[stack[-1]]:
                return False
            stack.pop()
    if len(stack) + len(s_list) > 0:
        return False
    return True


testIsValid()
<file_sep>"""
>>> from DataStruct import TreeNode
>>> root = TreeNode(1)
>>> root.left = TreeNode(2)
>>> level_order(root)
[[1], [2]]
"""


def level_order(root):
    """ Binary Tree Level Order Traversal """

    if root is None:
        return []

    level_list = []
    level = [root]
    while level:
        temp_level = []
        next_level = []
        for node in level:
            temp_level.append(node.val)
            if node.left:
                next_level.append(node.left)

            if node.right:
                next_level.append(node.right)

        level_list.append(temp_level)
        level = next_level

    return level_list<file_sep>"""
>>> get_row(3)
[1, 3, 3, 1]
>>> get_row(5)
[1, 5, 10, 10, 5, 1]
"""

def get_row(rowIndex):
    """ Pascal's Triangle II """

    rowIndex += 1

    for i in range(rowIndex):
        if i == 0:
            tri = [1]
        elif i == 1:
            tri.append(1)
        else:
            last_val = tri[0]
            for j in range(len(tri)-1):
                new_val = last_val + tri[j+1]
                last_val = tri[j+1]
                tri[j+1] = new_val
            tri.append(last_val)

    return tri


if __name__ == "__main__":
    import doctest
    doctest.testmod()<file_sep>"""
>>> climb_stairs(5)
8
>>> climb_stairs(20)
10946
"""


def climb_stairs(n):
    """ Climbing Stairs """

    arr = []
    for i in range(n+1):
        if i <= 1:
            arr.append(1)
        else:
            arr.append(arr[-1]+arr[-2])
    return arr[-1]


if __name__ == "__main__":
    import doctest
    doctest.testmod()<file_sep>Practice Questions and Solutions for Insight Interview Practice
=============================================
Compiled by <NAME> and <NAME>


WHERE DID THESE CAMELS COME FROM

## Table Of Contents
- [Data Structure](#data-structure)
- [SQL](#sql)


## Data Structure
[3Sum Closest](https://oj.leetcode.com/problems/3sum-closest/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/three_sum_closest_austin.py)

[Add Binary](https://oj.leetcode.com/problems/add-binary/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/add_binary_austin.py)

[Binary Tree Zigzag Level Order Traversal](https://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/zigzag_level_order_austin.py)

[Climbing Stairs](https://oj.leetcode.com/problems/climbing-stairs/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/climb_stairs_austin.py)

[Compare Version Numbers](https://oj.leetcode.com/problems/compare-version-numbers/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/compare_version_austin.py)

[Count and Say](https://oj.leetcode.com/problems/count-and-say/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/count_and_say_austin.py)
- [Brant](https://github.com/aouyang1/InsightInterviewPractice/blob/master/count_and_say_brant.py)

[Excel Sheet Column Number](https://oj.leetcode.com/problems/excel-sheet-column-number/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/title_to_number_austin.py)

[Implement strStr](https://github.com/aouyang1/InsightInterviewPractice/blob/master/implement_strstr_brant.py)
- [Brant](https://oj.leetcode.com/problems/implement-strstr/)

[Intersection of Two Linked Lists](https://oj.leetcode.com/problems/intersection-of-two-linked-lists/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/get_intersection_node_austin.py)
- [Brant](https://github.com/aouyang1/InsightInterviewPractice/blob/master/intersection_of_two_linked_lists_brant.py)

[Largest Number](https://oj.leetcode.com/problems/largest-number/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/largest_number_austin.py)

[Length of Last Word](https://oj.leetcode.com/problems/length-of-last-word/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/length_of_last_word_austin.py)

[Majority Element](https://oj.leetcode.com/prsoblems/majority-element/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/majority_element_austin.py)
- [Brant](https://github.com/aouyang1/InsightInterviewPractice/blob/master/majority_element_brant.py)

[Merge Sorted Array](https://oj.leetcode.com/problems/merge-sorted-array/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/merge_austin.py)

[Merge Two Sorted Lists](https://oj.leetcode.com/problems/merge-two-sorted-lists/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/merge_two_lists_austin.py)

[Pascal's Triangle](https://oj.leetcode.com/problems/pascals-triangle/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/generate_austin.py)

[Pascal's Triangle II](https://oj.leetcode.com/problems/pascals-triangle-ii/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/get_row_austin.py)

[Palindrome Number](https://oj.leetcode.com/problems/palindrome-number/)
-[Brant](https://github.com/aouyang1/InsightInterviewPractice/blob/master/palindrome_number_brant.py)

[Plus One](https://oj.leetcode.com/problems/plus-one/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/plus_one_austin.py)

[Remove Duplicates from Sorted Array](https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/remove_duplicates_austin.py)

[Remove Element](https://oj.leetcode.com/problems/remove-element/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/remove_element_austin.py)

[Reverse Integer](https://oj.leetcode.com/problems/reverse-integer/)
-[Brant](https://github.com/aouyang1/InsightInterviewPractice/blob/master/reverse_number_brant.py)

[Rotate Array](https://oj.leetcode.com/problems/rotate-array/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/rotate_austin.py)

[Same Tree](https://oj.leetcode.com/problems/same-tree/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/is_same_tree_austin.py)

[Search for a Range](https://oj.leetcode.com/problems/search-for-a-range/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/search_range_austin.py)

[Single Number](https://oj.leetcode.com/problems/single-number/)
-[Brant](https://github.com/aouyang1/InsightInterviewPractice/blob/master/single_number_brant.py)

[Spiral Matrix](https://oj.leetcode.com/problems/spiral-matrix/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/spiral_order_austin.py)

[Two Sum](https://oj.leetcode.com/problems/two-sum/)
- [Guang]
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/two_sum_austin.py)

[Valid Parentheses](https://oj.leetcode.com/problems/valid-parentheses/)
- [Guang](https://github.com/aouyang1/InsightInterviewPractice/raw/master/valid_parentheses_guang.py)
- [Austin](https://github.com/aouyang1/InsightInterviewPractice/raw/master/is_valid_austin.py)
- [Brant](https://github.com/aouyang1/InsightInterviewPractice/blob/master/valid_parentheses_brant.py)

## SQL
<file_sep>"""
>>> A = [1, 1, 2, 2, 2, 3, 3, 5, 7]
>>> idx = remove_duplicates(A)
>>> print idx, A[:idx]
5 [1, 2, 3, 5, 7]
"""


def remove_duplicates(A):
    """ Remove Duplicates from Sorted Array """

    if not A:
        return

    a_idx = 0
    for idx, val in enumerate(A):
        if A[a_idx] != val:
            a_idx += 1
            A[a_idx], A[idx] = A[idx], A[a_idx]

    return a_idx+1


if __name__ == "__main__":
    import doctest
    doctest.testmod()<file_sep>__author__ = 'aouyang1'


import unittest
from DataStruct import TreeNode


class TestTree(object):

    def test_binary_tree(self):

        root = TreeNode(7)
        root.left = TreeNode(4)
        root.right = TreeNode(6)


<file_sep>"""
>>> from DataStruct import Node
>>> head = Node(1)
>>> head.append_data([2, 3, 4, 5, 6, 7])
>>> head.print_values()
1
2
3
4
5
6
7
>>> head = reverse_between(head, 1, 7)
>>> head.print_values()
7
6
5
4
3
2
1
"""


def reverse_between(head, m, n):
    """ Reverse Linked List II """

    if not head:
        return

    lag = n - m + 1

    if lag == 1:
        return head

    run_tail = head
    run_n = head
    while n > 0:
        run_n = run_n.next
        if n == m:
            run_tail = run_tail.next

        n -= 1

    run_m = run_tail.next

    for i in range(lag):

        temp_node = run_m.next
        run_m.next = run_n
        run_n = run_m
        if i == lag-1:
            break
        run_m = temp_node


    run_tail.next = run_m

    return head



<file_sep>"""
>>> str_str(",nkzkergqkwe,kawef", "ker")
4
"""


def str_str(haystack, needle):
    if not needle:
        return 0
    elif not haystack:
        return -1

    for i in range(len(haystack)-len(needle)+1):
        if haystack[i] == needle[0]:
            valid = True
            for j in range(len(needle)):
                if haystack[i+j] != needle[j]:
                    valid = False
                    break
            if valid:
                return i

    return -1<file_sep>"""
>>> three_sum_closest([0, 1, 2, -3], 1)
0
>>> three_sum_closest([5, 7, -4, -10, 0, 12, 21, -3], 15)
15
"""


def three_sum_closest(num, target):
    """ 3Sum Closest """

    num.sort()
    curr_sum = None
    curr_delta = None
    jk_sum = {}
    for i in range(len(num)-2):
        j = i+1
        k = len(num)-1
        while j != k:
            if (j, k) not in jk_sum:
                jk_sum[(j, k)] = num[j] + num[k]

            temp_sum = num[i] + jk_sum[(j, k)]
            if temp_sum == target:
                return target
            elif temp_sum < target:
                j += 1
            else:
                k -= 1

            temp_delta = temp_sum - target
            if temp_delta < 0:
                temp_delta *= -1

            if curr_sum is None or temp_delta < curr_delta:
                curr_sum = temp_sum
                curr_delta = temp_delta

    return curr_sum


if __name__ == "__main__":
    import doctest
    doctest.testmod()
<file_sep>import unittest

class Solution:
    # @param num, a list of integers
    # @return an integer
    def majorityElementDict1(self, num):
        threshold = len(num)/2
        # print "threshold = %d" % threshold
        counts = {}
        for i in num:
            n_occur = 1
            if i in counts:
                n_occur = counts[i]+1
            if n_occur > threshold:
                return i
            counts[i] = n_occur
            # print "counts of %d's = %d" % (i, counts[i])
        # print "Shouldn't get here! No majority found"
        return None

    def majorityElementDict2(self, num):
        threshold = len(num)/2
        counts = {}
        for i in num:
            n_occur = 1
            if i in counts:
                n_occur = counts[i]+1
            if n_occur > threshold:
                return i
            counts[i] = n_occur
        return None

    majorityElementDict = majorityElementDict1

class TestSolution(unittest.TestCase):
    def test_number_of_the_feast(self):
        l = [6,6,5,5,5]
        a = 5
        self.assertEqual(a, Solution().majorityElementDict(l))
 
    def test_one_two_one_two(self):
        l = [1,2,1,2,1,2,1]
        a = 1
        self.assertEqual(a, Solution().majorityElementDict(l))
 
if __name__ == '__main__':
    unittest.main()
<file_sep>"""
>>> find_peak_element([3, 2])
0
>>> find_peak_element([1, 2, 3])
2
>>> find_peak_element([0, 1, 2, 3, 2])
3
"""


def slope(val0, val1):
    if val1 > val0:
        return 1
    elif val1 < val0:
        return -1
    else:
        return 0


def find_peak_element(num):
    """ Find Peak Element """

    num_len = len(num)
    if num_len == 1:
        return 0
    elif num_len >= 2:
        if slope(num[0], num[1]) == -1:
            return 0

        if num_len >= 3:
            curr_slope = slope(num[0], num[1])

            for idx in range(num_len-2):
                next_slope = slope(num[idx+1], num[idx+2])
                if curr_slope == 1 and next_slope == -1:
                    return idx + 1

                curr_slope = next_slope

        if slope(num[num_len-2], num[num_len-1]) == 1:
            return num_len - 1
<file_sep>import unittest

class Solution:
    # @return an integer
    def reverse(self, x):
        debug = False

        if debug:
          print "x: %d" % x

        sign = 1
        if x < 0:
          sign = -1
          x = 0 - x

        rx = 0
        while x:
          rx = rx * 10 + x % 10
          x = x / 10
          if debug:
            print "x: {0: >6}\t rx: {1: >6}\t rem = {2}".format(x,rx,x%10)

        if debug:
          print "rx: %d" % rx * sign

        # Special case for silly fake overflow
        if 2147483648 < rx:
          return 0

        return rx * sign

class TestSolution(unittest.TestCase):

    def test_1234(self):
        sln = Solution()
        self.assertEqual(4321, sln.reverse(1234))

    def test_1(self):
        sln = Solution()
        self.assertEqual(1, sln.reverse(1))

    def test_0(self):
        sln = Solution()
        self.assertEqual(0, sln.reverse(0))

    def test_100021(self):
        sln = Solution()
        self.assertEqual(120001, sln.reverse(100021))

    def test_neg12(self):
        sln = Solution()
        self.assertEqual(-21, sln.reverse(-12))

    def test_overflow(self):
        sln = Solution()
        #self.assertEqual(9646324351, sln.reverse(1534236469))
        self.assertEqual(0, sln.reverse(1534236469))

if __name__ == '__main__':
    unittest.main()
<file_sep>"""
>>> num = [1,2,3,4,5,6,7]
>>> rotate(num, 3)
>>> print num
[5, 6, 7, 1, 2, 3, 4]
>>> num = [1,2,3,4,5,6,7]
>>> rotate(num, 7)
>>> print num
[1, 2, 3, 4, 5, 6, 7]
>>> num = [1]
>>> rotate(num, 3)
>>> print num
[1]
>>> num = []
>>> rotate(num, 3)
>>> print num
[]
>>> num = [1, 2, 3, 4, 5, 6]
>>> rotate(num, 2)
>>> print num
[5, 6, 1, 2, 3, 4]
"""


def rotate(nums, k):
    """ Rotate Array """
    num_len = len(nums)
    if num_len <= 1:
        return

    offset = 0
    idx = (offset + k) % num_len
    for rep in range(num_len-1):

        nums[idx], nums[offset] = nums[offset], nums[idx]
        prev_idx = idx

        if prev_idx == offset:
            offset += 1
            idx = offset
        idx = (idx + k) % num_len


if __name__ == "__main__":
    import doctest
    doctest.testmod()<file_sep>"""
>>> from DataStruct import TreeNode
>>> root = TreeNode(2)
>>> root.left = TreeNode(4)
>>> root.right = TreeNode(7)
>>> root.left.left = TreeNode(5)
>>> root.left.right = TreeNode(8)
>>> min_depth(root)
2
"""


def min_depth(root):
    """ Minimum Depth of Binary Tree """

    if not root:
        return 0

    if not root.left and not root.right:
        return 1

    if root.left and root.right:
        return min(min_depth(root.left), min_depth(root.right)) + 1
    elif root.left:
        return min_depth(root.left) + 1
    else:
        return min_depth(root.right) + 1<file_sep>"""
>>> length_of_last_word("Hello")
5
>>> length_of_last_word(" Hello")
5
>>> length_of_last_word("Hello ")
5
>>> length_of_last_word(" Hello ")
5
>>> length_of_last_word("He l lo00 ")
4
"""


def length_of_last_word(s):
    """ Length of Last Word """

    space_idx = None

    space_from_end = True
    num_spaces_from_end = 0

    for idx in range(len(s)):
        rev_idx = len(s)-idx-1
        if s[rev_idx] == " ":
            if space_from_end:
                num_spaces_from_end += 1
            else:
                space_idx = rev_idx
                return len(s) - space_idx - num_spaces_from_end - 1

        else:
            space_from_end = False

    if space_idx is None:
        return len(s) - num_spaces_from_end<file_sep>"""
>>> from DataStruct import TreeNode
>>> root = TreeNode(3)
>>> root.left = TreeNode(9)
>>> root.right = TreeNode(20, left=TreeNode(15), right=TreeNode(7))
>>> zigzag_level_order(root)
[[3], [20, 9], [15, 7]]
"""


def zigzag_level_order(root):
    """ Binary Tree Zigzag Level Order Traversal """

    if not root:
        return []

    # breadth first approach
    level_list = [root]
    tree_list = []
    scan_right = True
    while level_list:
        curr_level = []
        next_level = []

        for node in level_list:
            curr_level.append(node.val)
            if scan_right:
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            else:
                if node.right:
                    next_level.append(node.right)
                if node.left:
                    next_level.append(node.left)

        scan_right = not scan_right
        next_level.reverse()
        level_list = next_level
        tree_list.append(curr_level)

    return tree_list


if __name__ == "__main__":
    import doctest
    doctest.testmod()<file_sep>"""
>>> compare_str("824", "8247")
1
>>> largest_number([3, 30, 34, 5, 9])
'9534330'
>>> largest_number([0, 0])
'0'
>>> largest_number([824,938,1399,5607,6973,5703,9609,4398,8247])
'9609938824824769735703560743981399'
"""


def compare_str(str1, str2):
    if str1 + str2 > str2 + str1:
        return 1
    elif str1 + str2 < str2 + str1:
        return -1
    else:
        return 0


def merge_str(num1, num2):
    ptr1 = 0
    ptr2 = 0
    new_num = []
    while ptr1 < len(num1) and ptr2 < len(num2):
        if compare_str(num1[ptr1], num2[ptr2]) == 1:
            new_num.append(num1[ptr1])
            ptr1 += 1
        else:
            new_num.append(num2[ptr2])
            ptr2 += 1

    if ptr2 == len(num2):
        new_num.extend(num1[ptr1:])
        return new_num

    if ptr1 == len(num1):
        new_num.extend(num2[ptr2:])
        return new_num


def mergesort_str(num):
    num_len = len(num)
    left = num[:num_len/2]
    right = num[num_len/2:]
    if not right:
        return left
    elif not left:
        return right
    else:
        return merge_str(mergesort_str(left), mergesort_str(right))


def largest_number(num):
    """ Largest Number """

    num = map(lambda x: str(x), num)
    num = mergesort_str(num)
    while num[0] == "0" and len(num) > 1:
        num = num[1:]

    return "".join(num)


if __name__ == "__main__":
    import doctest
    doctest.testmod()



<file_sep>"""
>>> A = [1, 3, 5, 7]
>>> B = [2, 4, 6, 8]
>>> merge(A, len(A), B, len(B))
>>> print A
[1, 2, 3, 4, 5, 6, 7, 8]
>>> A = [1, 2, 10]
>>> B = [3, 4, 6, 8, 12, 15, 19, 200]
>>> merge(A, len(A), B, len(B))
>>> print A
[1, 2, 3, 4, 6, 8, 10, 12, 15, 19, 200]
"""


def merge(A, m, B, n):
    """ Merge Sorted Array """

    A.extend([0]*n)
    ptrA = m-1
    ptrB = n-1
    ptrAex = m+n-1

    while True:
        if ptrB < 0:
            #done
            return
        if ptrA < 0:
            # flush remaining B list to A
            A[ptrAex] = B[ptrB]
            ptrAex -= 1
            ptrB -= 1
        else:
            # checking for swaps
            if A[ptrA] > B[ptrB]:
                A[ptrAex] = A[ptrA]
                ptrAex -= 1
                ptrA -= 1
            else:
                A[ptrAex] = B[ptrB]
                ptrAex -= 1
                ptrB -= 1


if __name__ == "__main__":
    import doctest
    doctest.testmod()<file_sep>

def is_leaf(node):
    return node.left is None and node.right is None


def funnel(left, right, first_pass=True):
    if left.next is None:
        print "{} next is: {}".format(left.val, right.val)
        left.next = right

    if is_leaf(left) or is_leaf(right):
        return

    if left.right and right.left:
        funnel(left.right, right.left, first_pass)

    if not first_pass:
        if left.left and right.left:
            funnel(left.left, right.left, first_pass)

        if left.right and right.right:
            funnel(left.right, right.right, first_pass)

        if left.left and right.right:
            funnel(left.left, right.right, first_pass)


def connect(root):
    """ Populating Next Right Pointers In Each Node """

    def build(root, first_pass=True):
        if not root or is_leaf(root):
            return

        if first_pass:
            if root.left and root.right:
                funnel(root.left, root.right, first_pass)
                build(root.left, first_pass)
                build(root.right, first_pass)
        else:
            if not root.left:
                build(root.right, first_pass)
            elif not root.right:
                build(root.left, first_pass)
            else:
                funnel(root.left, root.right, first_pass)
                build(root.left, first_pass)
                build(root.right, first_pass)

    build(root, True)
    build(root, False)



from DataStruct import TreeNode
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
root.left.left.left = TreeNode(8)
root.left.left.right = TreeNode(9)
#root.left.right.left = TreeNode(10)
#root.left.right.right = TreeNode(11)
root.right.left.left = TreeNode(12)
#root.right.left.right = TreeNode(13)
#root.right.right.left = TreeNode(14)
root.right.right.right = TreeNode(15)
connect(root)
print "level 1: val: {}".format(root.val)
print "       : next: {}\n".format(root.next)
print "level 2: val: {}".format([root.left.val,
                                 root.right.val])
print "       : next: {}\n".format([root.left.next.val,
                                    root.right.next])
print "level 3: val: {}".format([root.left.left.val,
                                 root.left.right.val,
                                 root.right.left.val,
                                 root.right.right.val])
print "       : next: {}\n".format([root.left.left.next.val,
                                    root.left.right.next.val,
                                    root.right.left.next.val,
                                    root.right.right.next])
print "level 4: val: {}".format([root.left.left.left.val,
                                 root.left.left.right.val,
                                 #root.left.right.left.val,
                                 #root.left.right.right.val,
                                 root.right.left.left.val,
                                 #root.right.left.right.val,
                                 #root.right.right.left.val,
                                 root.right.right.right.val])
print "       : next: {}\n".format([root.left.left.left.next.val,
                                    root.left.left.right.next.val,
                                    #root.left.right.left.next.val,
                                    #root.left.right.right.next.val,
                                    root.right.left.left.next.val,
                                    #root.right.left.right.next,
                                    #root.right.right.left.next.val,
                                    root.right.right.right.next])
<file_sep>"""
>>> from DataStruct import TreeNode
>>> root = TreeNode(1)
>>> root.left = TreeNode(2)
>>> root.left.left = TreeNode(3)
>>> root.left.right = TreeNode(4)
>>> root.right = TreeNode(5)
>>> root.right.right = TreeNode(6)
>>> flatten(root)
>>> print root.val, root.right.val, root.right.right.val, root.right.right.right.val, root.right.right.right.right.val, root.right.right.right.right.right.val, root.right.right.right.right.right.right
1 2 3 4 5 6 None
"""


def append_right(root):
    temp_right = root.right
    root.right = root.left
    root.left = None
    tail = root.right
    while tail.right is not None:
        tail = tail.right

    tail.right = temp_right


def is_leaf(root):
    return not root.left and not root.right


def flatten(root):
    """ Flatten Binary Tree to Linked List """

    if not root or is_leaf(root):
        return

    if root.left:
        append_right(root)

    flatten(root.right)<file_sep>def count_and_say(n):
    """ computes nth element in the sequence of count-and-say
    numbers.

    Args:
        n: how many elements should be in the sequence

    Returns:
        nth_elt: resulting element in count-and-say sequence

    Examples:
    >>> count_and_say(0)
    '1'
    >>> count_and_say(1)
    '11'
    >>> count_and_say(2)
    '21'
    >>> count_and_say(3)
    '1211'
    >>> count_and_say(4)
    '111221'
    """

    if n == 0:
        return '1'
    else:
        raw = count_and_say(n-1)
        return say(raw)


def say(raw_str):
    """ say a given raw string

    partition into substrings that have identical elements
    get (len, val) pair for each substring
    concatenate the resulting (len, val) pairs

    Examples:
    >>> say('11')
    '21'
    >>> say('21')
    '1211'
    >>> say('1211')
    '111221'
    """

    if len(raw_str) == 1:
        return '11'
    else:
        curr_len = 1
        len_val_pairs = []
        raw_str = raw_str + ' '     # appends space at end
        for ind in range(1, len(raw_str)):
            val = raw_str[ind]
            prev_val = raw_str[ind-1]
            if val == prev_val:
                curr_len += 1
            else:
                len_val_pairs.append(str(curr_len))
                len_val_pairs.append(prev_val)
                curr_len = 1
        return ''.join(len_val_pairs)
<file_sep># https://oj.leetcode.com/problems/valid-parentheses/

import unittest

class Solution:
    # @return a string
    def countAndSay(self, n):
        if n == 1:
            return "1"

        i = 1
        for x in range(n-1):
            i = self.say_num_of(i)
        return str(i)

    def say_num_of(self, n):

        accum = []
        prev = None
        seq_count = 0
        for i in str(n):
            if not prev:
                seq_count = 1
                prev = i
            elif i == prev:
                seq_count += 1
            else:
                accum.append("%d%s" % (seq_count, prev))                
                seq_count = 1
                prev = i
        accum.append("%d%s" % (seq_count, prev))                
        result = int("".join(accum))
        # print "%d -> %d" % (n, result)
        return result

def countAndSayConcise(self, n):
    res = '1'
    for i in range(n-1):
        stack = []
        for (k, g) in itertools.groupby(res):
            stack.append(str(len(list(g)))+k)
        res = ''.join(stack)
    return res

class TestSolution(unittest.TestCase):
    def test_01(self):
        sln = Solution()
        self.assertEqual("1", sln.countAndSay(1))

    def test_02(self):
        sln = Solution()
        self.assertEqual("11", sln.countAndSay(2))
 
    def test_03(self):
        sln = Solution()
        self.assertEqual("21", sln.countAndSay(3))
 
    def test_04(self):
        sln = Solution()
        self.assertEqual("1211", sln.countAndSay(4))
 
    def test_05(self):
        sln = Solution()
        self.assertEqual("111221", sln.countAndSay(5))
 
    def test_06(self):
        sln = Solution()
        self.assertEqual("312211", sln.countAndSay(6))
 
    def test_07(self):
        sln = Solution()
        self.assertEqual("13112221", sln.countAndSay(7))
 
if __name__ == '__main__':
    unittest.main()
<file_sep>"""
>>> from DataStruct import Node
>>> l1 = Node(5)
>>> l1.next = Node(8)
>>> l2 = Node(2)
>>> l2.next = Node(4)
>>> l2.next.next = Node(6)
>>> l2.next.next.next = Node(7)
>>> l2.next.next.next.next = Node(9)
>>> l3 = merge_two_lists(l1, l2)
>>> for i in range(7):
...     print l3.val
...     l3 = l3.next
2
4
5
6
7
8
9
"""


def merge_two_lists(l1, l2):
    """ Merge Two Sorted Lists """

    if l1 is None and l2 is None:
        return
    elif l1 is None:
        head = l2
        return head
    elif l2 is None:
        head = l1
        return head

    if l1.val < l2.val:
        head = l1
        l1 = l1.next
    else:
        head = l2
        l2 = l2.next

    curr_head = head
    while l1 or l2:
        if l1 and l2:
            if l1.val < l2.val:
                curr_head.next = l1
                l1 = l1.next
            else:
                curr_head.next = l2
                l2 = l2.next
        elif l1 and l2 is None:
            curr_head.next = l1
            l1 = l1.next
        elif l2 and l1 is None:
            curr_head.next = l2
            l2 = l2.next

        curr_head = curr_head.next

    return head<file_sep># https://oj.leetcode.com/problems/valid-parentheses/

import unittest
from collections import deque

class Solution:
    # @return a boolean
    # openers = {'{':'}','[':']', '(':')'}
    # closers = {v: k for k, v in openers.items()}
    
    # def isValid1(self, s):
    #     next_close = []
    #     for c in s:
    #         #print "c: %c" % c
    #         if c in self.openers.keys():
    #             next_close.append(self.openers[c])
    #         elif c in self.closers.keys():
    #             if not next_close or next_close.pop() != c:
    #                 #print "INVALID"
    #                 return False
    #     #print "next_close len = %d --> %r" % (len(next_close), len(next_close) == 0)
    #     return not next_close

    def isValid(self, s):
        paren_stack = deque()
        for c in s:
            #print "<-- %c" % c
            if not paren_stack:
                paren_stack.append(c)
            else:
                if (ord(c) == 1 + ord(paren_stack[-1]) or (ord(c) == 2 + ord(paren_stack[-1]))):
                    paren_stack.pop()
                else:
                    paren_stack.append(c)
            #print paren_stack
        if not paren_stack:
            return True
        return False


class TestSolution(unittest.TestCase):
    def test_one_of_each(self):
        sln = Solution()
        self.assertEqual(True, sln.isValid("{}()[]"))
 
    def test_one_of_each_nested(self):
        sln = Solution()
        self.assertEqual(True, sln.isValid("{([])}"))
 
    def test_two_interleaved(self):
        sln = Solution()
        self.assertEqual(False, sln.isValid("([)]"))
 
    def test_two_left_open(self):
        sln = Solution()
        self.assertEqual(False, sln.isValid("(["))
 
    def test_two_close_only(self):
        sln = Solution()
        self.assertEqual(False, sln.isValid("])"))
 
    def test_extra_open(self):
        sln = Solution()
        self.assertEqual(False, sln.isValid("([)"))
 
if __name__ == '__main__':
    unittest.main()
<file_sep>"""
>>> from DataStruct import TreeNode
>>> root = TreeNode(2)
>>> root.left = TreeNode(4)
>>> root.right = TreeNode(7)
>>> root.left.left = TreeNode(5)
>>> root.left.right = TreeNode(8)
>>> root.right.left = TreeNode(1)
>>> max_depth(root)
3
"""


def max_depth(root):
    """ Maximum Depth of Binary Tree """

    if not root:
        return 0

    if not root.left and not root.right:
        return 1

    if root.left and root.right:
        return max(max_depth(root.left), max_depth(root.right)) + 1
    elif root.left:
        return max_depth(root.left) + 1
    else:
        return max_depth(root.right) + 1<file_sep>"""
>>> fizzbuzz(1, 17)
1
2
fizz
4
buzz
fizz
7
8
fizz
buzz
11
fizz
13
14
fizzbuzz
16
"""


def fizzbuzz(start_idx, end_idx):
    """ Fizz Buzz """

    for val in range(start_idx, end_idx):
        if val % 3 == 0 and val % 5 == 0:
            print "fizzbuzz"
        elif val % 3 == 0:
            print "fizz"
        elif val % 5 == 0:
            print "buzz"
        else:
            print val

if __name__ == "__main__":
    import doctest
    doctest.testmod()


<file_sep>"""
>>> compare_version("0.1", "1.1")
-1
>>> compare_version("1.2", "1.1")
1
>>> compare_version("13.37", "13")
1
>>> compare_version("1.2.3.4", "1.2.3.70")
-1
>>> compare_version("1.2.3.4", "1.2.3.4")
0
"""


def compare_version(version1, version2):
    """ Compare Version Numbers """

    split_ver1 = map(lambda x: int(x), version1.split("."))
    split_ver2 = map(lambda x: int(x), version2.split("."))

    ver1_len = len(split_ver1)
    ver2_len = len(split_ver2)

    if ver1_len > ver2_len:
        split_ver2 += [0]*(ver1_len-ver2_len)
    elif ver2_len > ver1_len:
        split_ver1 += [0]*(ver2_len-ver1_len)

    for ver1, ver2 in zip(split_ver1, split_ver2):
        if ver1 > ver2:
            return 1
        elif ver2 > ver1:
            return -1

    return 0


if __name__ == "__main__":
    import doctest
    doctest.testmod()<file_sep>class Solution:
    # @param s, a string
    # @return an integer
    def lengthOfLastWord(self, s):
        if len(s) == 0:
            return 0

        last_word_ind = None
        current_ind = len(s) - 1
        while (last_word_ind is None):
            if current_ind == 0:
                last_word_ind = 0
            if s[current_ind] == ' ':
                last_word_ind = current_ind + 1
            else:
                current_ind -= 1
        return len(s) - last_word_ind + 1
<file_sep>"""
>>> two_sum([3, 2, 4], 6)
(2, 3)
>>> two_sum([4, 6, 2, 8, 3, 9], 9)
(2, 5)
"""


def two_sum(num, target):
    """ Two Sum """

    num_dict = {}
    for idx, val in enumerate(num):
        num_dict[val] = idx

    for idx, val in enumerate(num):
        search_val = target - val
        if search_val in num_dict:
            if num_dict[search_val] > idx:
                index1 = idx+1
                index2 = num_dict[search_val]+1
                return index1, index2


if __name__ == "__main__":
    import doctest
    doctest.testmod()<file_sep>__author__ = 'aouyang1'


import ipdb


class TreeNode(object):

    def __init__(self, item, left=None, right=None, next=None):
        self.left = left
        self.right = right
        self.val = item
        self.next = next


class Node(object):

    def __init__(self, d):
        self.next = None
        self.prev = None
        self.val = d

    def print_values(self, num_elem=None):
        cnt = 0
        next_node = self.next
        print self.val

        while next_node is not None:
            cnt += 1
            if num_elem is not None and cnt == num_elem:
                break

            print next_node.val
            next_node = next_node.next

    def append_data(self, val_list):
        curr_node = self
        for val in val_list:
            curr_node.next = Node(val)
            curr_node = curr_node.next






class StackClass(object):

    def __init__(self):
        self.top = None
        self.num_elem = 0
        self.min_top = None

    def push(self, item):
        if not self.top:
            self.top = Node(item)
            self.min_top = Node(item)
        else:
            # push item to top of stack
            old_top = self.top
            self.top = Node(item)
            self.top.next = old_top

            # node with minimum value in stack to top
            old_min = self.min_top
            if self.min_top.val > item:
                new_min = item
            else:
                new_min = self.min_top.val
            self.min_top = Node(new_min)
            self.min_top.next = old_min

        self.num_elem += 1

    def pop(self):
        if not self.top:
            return None
        else:
            item = self.top.val
            self.top = self.top.next

            self.min_top = self.min_top.next

            self.num_elem -= 1
            return item

    def peek(self):
        if not self.top:
            return None
        else:
            item = self.top.val
            return item

    def is_empty(self):
        return not self.top

    def size(self):
        return self.num_elem

    def min(self):
        if self.top:
            return self.min_top.val
        else:
            return None


class QueueClass(object):

    def __init__(self):
        self.front = None
        self.rear = None
        self.num_elem = 0

    def enqueue(self, item):
        if not self.rear:
            self.rear = Node(item)
            self.front = self.rear
        else:
            old_rear = self.rear
            self.rear = Node(item)
            self.rear.next = old_rear
            old_rear.prev = self.rear

        self.num_elem += 1

    def dequeue(self):
        if not self.front:
            return None
        else:
            item = self.front.val
            print self.front.prev, self.size()
            self.front = self.front.prev
            self.front.next = None
            self.num_elem -= 1
            return item

    def is_empty(self):
        return not self.rear

    def size(self):
        return self.num_elem


def sort_stack(s1):
    s2 = StackClass()

    while not s1.is_empty():

        if s2.is_empty() or s1.peek() >= s2.peek():
            s2.push(s1.pop())
        else:
            temp_val = s1.pop()
            while not s2.is_empty() and temp_val < s2.peek():

                s1.push(s2.pop())
            s2.push(temp_val)

    return s2


class MyQueue(object):
    s1 = StackClass()
    s2 = StackClass()

    def __init__(self):
        self.front = None
        self.rear = None
        self.num_elem = 0

    def enqueue(self, item):
        if not self.rear:
            self.rear = Node(item)
            self.front = self.rear
        else:
            old_rear = self.rear
            self.rear = Node(item)
            self.rear.next = old_rear
            old_rear.prev = self.rear

        self.num_elem += 1

    def dequeue(self):
        if not self.front:
            return None
        else:
            item = self.front.val
            print self.front.prev, self.size()
            self.front = self.front.prev
            self.front.next = None
            self.num_elem -= 1
            return item
<file_sep># https://oj.leetcode.com/problems/valid-parentheses/

import unittest

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def __repr__(self):
        return str(self.val)

class LList:
    def __init__(self, head=None):
        self.head = head

    def insert(self, new_node):
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def len(self):
        count = 0;
        current = self.head
        while current:
            count += 1
            current = current.next
        return count

    def __repr__(self):
        current = self.head
        nodes = []
        while current:
            nodes.append("{}".format(current))
            current = current.next
        return " -> ".join(nodes)

class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
        long_head = headA
        short_head = headB
        long_len = self.list_len(headA)
        short_len = self.list_len(headB)
        if long_len < short_len: # nope, reverse it
            temp = long_head
            temp_len = long_len
            long_head = short_head
            long_len = short_len
            short_head = temp
            short_len = temp_len
        long_start_offset = long_len - short_len
        print "Offset = %d" % long_start_offset

        short_node = short_head
        long_node = long_head
        for x in range(long_start_offset):
            #print "Skipping {}".format(long_node)
            long_node = long_node.next

        for x in range(short_len):
            #print "Comparing {} - {}".format(long_node, short_node)
            if short_node == long_node:
                return short_node
            short_node = short_node.next
            long_node = long_node.next

        return None

    def list_len(self, list_head):
        count = 0;
        current = list_head
        while current:
            count += 1
            current = current.next
        return count


class TestSolution(unittest.TestCase):
    def test_prob_example(self):
        sln = Solution()
        
        la = LList()
        la.insert(ListNode('a1'))
        la.insert(ListNode('a2'))

        lb = LList()
        lb.insert(ListNode('b1'))
        lb.insert(ListNode('b2'))
        lb.insert(ListNode('b3'))

        c1 = ListNode('c1')
        lc = LList()
        lc.insert(c1)
        lc.insert(ListNode('c2'))
        lc.insert(ListNode('c3'))

        la.insert(c1)
        lb.insert(c1)

        # print la
        # print lb
        # print lc

        sln = Solution()
        self.assertEqual('c1', sln.getIntersectionNode(la.head, lb.head).val)
 
    def test_a_longer(self):
        sln = Solution()
        
        la = LList()
        la.insert(ListNode('a1'))
        la.insert(ListNode('a2'))
        la.insert(ListNode('a3'))

        lb = LList()
        lb.insert(ListNode('b1'))
        lb.insert(ListNode('b2'))

        c1 = ListNode('c1')
        lc = LList()
        lc.insert(c1)
        lc.insert(ListNode('c2'))
        lc.insert(ListNode('c3'))

        la.insert(c1)
        lb.insert(c1)

        sln = Solution()
        self.assertEqual('c1', sln.getIntersectionNode(la.head, lb.head).val)
 
    def test_same_len(self):
        sln = Solution()
        
        la = LList()
        la.insert(ListNode('a1'))
        la.insert(ListNode('a2'))

        lb = LList()
        lb.insert(ListNode('b1'))
        lb.insert(ListNode('b2'))

        c1 = ListNode('c1')
        lc = LList()
        lc.insert(c1)
        lc.insert(ListNode('c2'))

        la.insert(c1)
        lb.insert(c1)

        sln = Solution()
        self.assertEqual('c1', sln.getIntersectionNode(la.head, lb.head).val)
 
    def test_only_one_list(self):
        sln = Solution()
        
        la = LList()
        lb = LList()

        c1 = ListNode('c1')
        lc = LList()
        lc.insert(c1)
        lc.insert(ListNode('c2'))

        la.insert(c1)
        lb.insert(c1)

        sln = Solution()
        self.assertEqual('c1', sln.getIntersectionNode(la.head, lb.head).val)
 
if __name__ == '__main__':
    unittest.main()
<file_sep>"""
>>> from DataStruct import TreeNode
>>> root = TreeNode(1)
>>> root.left = TreeNode(2)
>>> root.right = TreeNode(2)
>>> root.left.left = TreeNode(3)
>>> root.left.right = TreeNode(4)
>>> root.right.left = TreeNode(4)
>>> root.right.right = TreeNode(3)
>>> is_symmetric(root)
True
>>> root = TreeNode(1)
>>> root.left = TreeNode(2)
>>> root.right = TreeNode(2)
>>> root.left.right = TreeNode(3)
>>> root.right.right = TreeNode(3)
>>> is_symmetric(root)
False
"""


def is_symmetric(root):
    """ Symmetric Tree """

    def is_leaf(node):
        return node.left is None and node.right is None

    if not root or is_leaf(root):
        return True

    level = [root]
    while level:
        # fill next level and values of current level
        next_level = []
        node_val = []
        for node in level:
            if node.left:
                next_level.append(node.left)
                node_val.append(node.left.val)
            else:
                node_val.append(None)

            if node.right:
                next_level.append(node.right)
                node_val.append(node.right.val)
            else:
                node_val.append(None)

        #check if node_val list is symmetric
        for n_idx in range(len(node_val)/2):
            if node_val[n_idx] != node_val[len(node_val)-n_idx-1]:
                return False

        # clean level if all None
        level = next_level

    return True<file_sep>"""
>>> unique_paths(2, 2)
2
>>> unique_paths(3, 3)
6
>>> unique_paths(10, 10)
48620
>>> unique_paths(12, 12)
705432
>>> unique_paths(100, 100)
22750883079422934966181954039568885395604168260154104734000L
"""

memo = {}


def unique_paths(m, n):
    """ Unique Paths """

    if m == 1 and n == 1:
        return 1

    if m == 1:
        if (m, n-1) not in memo:
            memo[(m, n-1)] = unique_paths(m, n-1)
        return memo[(m, n-1)]

    elif n == 1:
        if (m-1, n) not in memo:
            memo[(m-1, n)] = unique_paths(m-1, n)
        return memo[(m-1, n)]
    else:
        if (m, n-1) not in memo:
            memo[(m, n-1)] = unique_paths(m, n-1)

        if (m-1, n) not in memo:
            memo[(m-1, n)] = unique_paths(m-1, n)

        return memo[(m, n-1)] + memo[(m-1, n)]<file_sep># Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param p, a tree node
    # @param q, a tree node
    # @return a boolean
    def isSameTree(self, p, q):
        # first two levels edge cases
        if p is None and q is None:
            return True
        if (p is None) is (q is not None):
            return False

        # check base structure is same
        if (p.left is None) is (q.left is not None):
            return False
        if (p.right is None) is (q.right is not None):
            return False

        # check current node values
        if p.val != q.val:
            return False

        # base case
        if p.left is None and p.right is None:
            return True

        # other cases
        elif p.left is None:
            return self.isSameTree(p.right, q.right)

        elif p.right is None:
            return self.isSameTree(p.left, q.left)
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
