python

3月 222014
 
One trivial routine to work with PC SAS is to clear many HTML files created by using SAS, which usually occupy large hard disk space. By default, Windows does not have shell language to find the files with the same prefix as sashtml. I found that iPython is a convenient alternative for a shell language to conduct regular expression, and I only need a few lines of codes to realize my goal.
%bookmark saswork c:\mydocument
!cd saswork
a = !dir
b = a.grep('sashtml').fields(4)
!del $b.s
11月 222013
 
  • Fibonacci number
  • #-------------------------------------------------------------------------------
    # Name: Fibonacci number
    # Purpose:
    #
    # Note: http://en.wikipedia.org/wiki/Fibonacci_number
    #-------------------------------------------------------------------------------

    # Bad solution by recursion
    def fib_rcs(n):
    if n in [1, 2]:
    return 1
    return fib_rcs(n-1) + fib_rcs(n-2)

    # Good solution by iteration
    def fib_itr(n):
    a = [1]*n
    for i in range(2, n):
    a[i] = a[i-1] + a[i-2]
    return a[n-1]

    # Better solution by mathematics
    def fib_mth(n):
    cnst = 5**0.5
    phi = (1 + cnst)/2;
    return int((phi**n - (1-phi)**n) / cnst)

    print fib_rcs(25) # cost too much time
    print fib_itr(25)
    print fib_mth(25)
    • Pascal’s Triangle
    #-------------------------------------------------------------------------------
    # Name: Pascal's Triangle
    # Purpose:
    #
    # Given an index k, return the kth row of the Pascal's triangle.
    #
    # For example, given k = 3,
    # Return [1,3,3,1].
    #
    # Note:
    # Could you optimize your algorithm to use only O(k) extra space?
    #
    #-------------------------------------------------------------------------------

    # Bad solution by recursion
    def pascal_rcs(n):
    if n == 0: return [1]
    return [1] + [pascal_rcs(n-1)[i] + pascal_rcs(n-1)[i-1] for i in range(1, n)] + [1]

    # Good solution by iteration
    def pascal_itr(n):
    result = [1]
    for row in range(1, n + 1):
    current = [1]
    for col in range(1, row):
    current.append(result[col-1] + result[col])
    result = current + [1]
    return result

    print pascal_rcs(5)
    print pascal_itr(5)
    print pascal_rcs(9) # cost too much time
    print pascal_itr(9)

    #-------------------------------------------------------------------------------
    # Name: Pascal's Triangle II
    # Purpose:
    # Given numRows, generate the first numRows of Pascal's triangle.
    #
    # For example, given numRows = 5,
    # Return
    #
    # [
    # [1],
    # [1,1],
    # [1,2,1],
    # [1,3,3,1],
    # [1,4,6,4,1]
    # ]
    #
    #-------------------------------------------------------------------------------

    def pascal_tgl_inside(n):
    result = [1]
    for row in range(1, n + 1):
    yield result
    current = [1]
    for col in range(1, row):
    current.append(result[col-1] + result[col])
    result = current + [1]

    def pascal_tgl(n):
    if n < 1:
    return []
    return list(pascal_tgl_inside(n))

    print pascal_tgl(8)
    • Unique Paths
    #-------------------------------------------------------------------------------
    # Name: Unique Paths
    # Purpose:
    #
    # A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
    #
    # The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
    #
    # How many possible unique paths are there?
    #
    #
    # Above is a 3 x 7 grid. How many possible unique paths are there?
    #
    # Note: m and n will be at most 100.
    #-------------------------------------------------------------------------------

    # Bad solution by recursion
    def path_rcs(m, n):
    if m == 1 or n == 1:
    return 1
    return path_itr(m-1, n) + path_itr(m, n-1)

    # Good solution by iteration
    def path_itr(row, col):
    res = [[1]*col]*row
    for i in range(1, row):
    for j in range(1, col):
    res[i][j] = res[i-1][j] + res[i][j-1]
    return res[row-1][col-1]

    print path_rcs(4, 4)
    print path_itr(4, 4)
    • Merge Intervals
    #-------------------------------------------------------------------------------
    # Name: Merge Intervals
    # Purpose:
    #
    # Given a collection of intervals, merge all overlapping intervals.
    #
    # For example,
    # Given [1,3],[2,6],[8,10],[15,18],
    # return [1,6],[8,10],[15,18].
    #
    #-------------------------------------------------------------------------------

    def mrg_itr(z):
    if len(z) == 0:
    return []
    z.sort(key = lambda x: x[0])
    carrier = z[0]
    result = [carrier]
    for i in range(1, len(z)):
    if carrier[1] >= z[i][0]:
    current = [carrier[0], max(carrier[1], z[i][1])]
    result.pop()
    else:
    current = z[i]
    result.append(current)
    carrier = result[-1]
    return result

    z = [[1,4],[2,6],[8,10],[9, 12],[15,18]]
    print mrg_itr(z)
    11月 222013
     
    There are many interesting questions about Python programming. Most likely the questions can fit into three categories, including data structure, algorithm and system design. Most solutions should be less than 20 lines.

    Data Structure

    The most common data structures in Python are list and dictionary. The two are very flexible to hold data to suit need. Especially the dictionary can be used to construct hash table to decrease complexity. 

    1. List

    List is used below as a character buffer.
    Test if a string has all unique characters
    def is_unique(s):
    a = [False]*256
    for n in s:
    # Use the ord() function to find the ASCII value of a character
    if a[ord(n)]:
    return False # jump out of the loop
    a[ord(n)] = True
    return True

    if __name__ == "__main__":
    testcases = ["abcdefg", "abcdefga", "5523231"]
    for case in testcases:
    print is_unique(case)

    2. Dictionary

    The set operations are my favorite to compare two dictionaries.
    Find the commonality between two dictionaries
    from collections import defaultdict 
    def find_common(a, b):
    c = defaultdict(list)
    c['key_common'].append(set(a.keys()) & set(b.keys()))
    c['item_common'].append(set(a.items()) & set(b.items()))
    return c

    if __name__ == "__main__":
    dict1 = {'a': 1, 'b': 2, 'c': 3}
    dict2 = {'x': 4, 'y': 5, 'a': 4, 'b': 2, 'c': 3}
    print find_common(dict1, dict2)

    3. Hash table

    This is the famous 2-um question. The two solutions by Python below have different complexity.
    Given an array of integers, find two numbers such that they add up to a specific target number.
    # Solution 1
    def two_sum(numbers, target):
    res = []
    for i in range(len(numbers)):
    for j in range(i+1, len(numbers)):
    if numbers[i] + numbers[j] == target:
    res.append([i+1, j+1])
    return res

    # Solution 2
    def two_sum2(numbers, target):
    res = [0]*2
    hashmap = {}
    for i in range(len(numbers)):
    if hashmap.has_key(numbers[i]):
    index = hashmap.get(numbers[i])
    res[0] = index+1 ;
    res[1] = i+1;
    return res
    else:
    hashmap[target - numbers[i]] = i
    return res

    if __name__ == "__main__":
    testcase = [1, 2, 4, 3, 10, 9]
    target = 5
    print two_sum(numbers, target)
    print two_sum2(numbers, target)

    Algorithm

    Most common algorithms linked with Python are mathematics\matrix, sorting\searching and recursion.

    4. Mathematics

    We can use either nested array or the NumPy module to manipulate matrices.
    If one cell in a matrix is 0, then set both the column and the row to be 0.
    # Solution 1
    def set_zero(a):
    # Use two lists as buffer
    row = [0]*len(a)
    col = [0]*len(a[0])
    for i in range(len(row)):
    for j in range(len(col)):
    if a[i][j] == 0:
    row[i] = col[j] = 1
    # Use the buffer to set the elements
    for i, x in enumerate(row):
    for j, y in enumerate(col):
    if x == 1 or y == 1:
    a[i][j] = 0
    return a

    # Solution 2
    import numpy as np
    def set_zero2(a):
    a = np.array(a)
    # Use a list as buffer
    b = [(x, y) for (x, y), value in np.ndenumerate(a) if value == 0]
    for i, j in b:
    a[i, :] = 0
    a[:, j] = 0
    return a

    if __name__ == "__main__":
    testcase1 = [[1,2,3], [3,2,1], [1,0,9]]
    print set_zero(testcase1)
    testcase1 = [[1,2,3], [3,2,1], [1,0,9]]
    print set_zero2(testcase1)

    5. Search and sort

    Searching and sorting are the very basis for computing algorithm.
    Find an element in a list and return its index
    def search(a, x):
    # Use two pointers
    l = 0
    u = len(a) - 1
    while l <= u:
    m = (l + u) / 2
    if x == a[m]:
    return m
    elif a[l] <= a[m]:
    if x > a[m]:
    l = m + 1
    elif x > a[l]:
    u = m - 1
    else:
    l = m + 1
    elif x < a[m]:
    u = m - 1
    elif x <= a[u]:
    l = m + 1
    else:
    u = m - 1
    return -1

    if __name__ == "__main__":
    testcase = [15, 16, 99, 1, 3, 4, 5, 7, 10, 14, 19, 20, 25]
    assert search(testcase, 5) == testcase.index(5)

    6. Recursion

    The question asks to emulate the permutations method from the built-in collections module.
    Find all possible permutations of the characters in a string
    # Solution 1
    def permu(s):
    permutation = []
    # Error case
    if s == None:
    return None
    # Bad case
    elif len(s) == 0:
    permutation.append("")
    return permutation
    # Normal case
    first = s[0]
    remainder = s[1:]
    words = permu(remainder) #start to use recursion
    for word in words:
    for j in range(len(word)+1):
    start = word[:j]
    end = word[j:]
    permutation.append(start + first + end)
    return permutation

    # Solution 2
    from itertools import permutations
    def permu2(s):
    permutation = []
    for x in permutations(s):
    permutation.append(''.join(x))
    return permutation

    if __name__ == "__main__":
    print permu('abcd'), permu2('abcd')

    7. Generator

    To create an iteratable object, the generator can save quite a few codes other than the option of function.
    Flatten a nested list and save all elements from it as a simple list
    from collections import Iterable
    def flatten(items, ignore_types=(str, bytes)):
    for x in items:
    if isinstance(x, Iterable) and not isinstance(x, ignore_types):
    for y in flatten(x, ignore_types):
    yield y
    else:
    yield x

    if __name__ == "__main__":
    items = [1, 2, [3, 4, [5, 6], 7], 8]
    print flatten(items)

    System Design

    Decorator, OOP and testing are the frequent topics in designing a system.

    8. Decorator

    Implement a chain decorator
    def bread(func):
    def wrapper():
    print "</''''''\>"
    func()
    print "<\______/>"
    return wrapper

    def ingredients(func):
    def wrapper():
    print "#tomatoes#"
    func()
    print "~salad~"
    return wrapper

    @bread
    @ingredients
    def sandwich(food="--ham--"):
    print food

    if __name__ == "__main__":
    sandwich()

    9. Class

    Implement a queue
    from array import array
    class Queue:
    def __init__(self, size_max):
    assert size_max > 0
    self.max = size_max
    self.head = 0
    self.tail = 0
    self.size = 0
    self.data = array('i', range(size_max))

    def empty(self):
    return self.size == 0

    def full(self):
    return self.size == self.max

    def enqueue(self,x):
    if self.size == self.max:
    return False
    self.data[self.tail] = x
    self.size += 1
    self.tail += 1
    if self.tail == self.max:
    self.tail = 1
    return True

    def dequeue(self):
    if self.size == 0:
    return None
    x = self.data[self.head]
    self.size -= 1
    self.head += 1
    if self.head == self.max:
    self.head = 0
    return x

    10. Testing

    The Plus One question is a good example to use testing to make the unit complete.
    Given a number represented as an array of digits, plus one to the number.
    def plus_one(a):
    # Error case
    assert isinstance(a, list) == True, 'Must have a list as argument'
    # Bad case
    if len(a) == 0:
    return None
    # Normal case
    for i in reversed(range(len(a))):
    if a[i] != 9:
    a[i] += 1
    return a
    else:
    a[i] = 0
    # Special case
    a.insert(0, 1)
    return a

    if __name__ == "__main__":
    testcase1 = [1, 2, 3, 4]
    print plus_one(testcase1)
    testcase2 = [8, 9, 9, 9]
    print plus_one(testcase2)
    testcase3 = [9, 9, 9, 9]
    print plus_one(testcase3)
    testcase4 = 0
    print plus_one(testcase4)
    P.S. Another function to tell if the string is unique.
    def is_unique(str):
    a = {}
    for x in str:
    try:
    a[x] += 1
    except:
    a[x] = 1
    if a[x] == 2:
    return False
    return True
    11月 182013
     
    #-------------------------------------------------------------------------------
    # Name: Methods of sorting
    # Purpose: implements the sortings mentioned by Robert Sedgewick and
    # Kevin Wayne, Algorithms 4ed
    #
    #-------------------------------------------------------------------------------

    def selection_sort(a):
    for i in range(len(a)):
    min = i
    for j in range(i+1, len(a)):
    if a[j] < a[min]:
    min = j
    a[i], a[min] = a[min], a[i]

    def insertion_sort(a):
    for i in range(len(a)):
    j = i
    while j > 0:
    if a[j] < a[j-1]:
    a[j], a[j-1] = a[j-1], a[j]
    j -= 1

    def shell_sort(a):
    h = 1
    while h <= len(a)/3:
    h = 3*h+ 1 # in the test use 4 as increment sequence
    while h >= 1:
    for i in range(len(a)):
    j = i
    while j >= h and a[j] < a[j-h]:
    a[j], a[j-h] = a[j-h], a[j]
    j -= h
    h /= 3

    def merge_sort(x):
    result = []
    if len(x) < 2:
    return x
    mid = int(len(x)/2)
    y = merge_sort(x[:mid])
    z = merge_sort(x[mid:])
    i = 0
    j = 0
    while i < len(y) and j < len(z):
    if y[i] > z[j]:
    result.append(z[j])
    j += 1
    else:
    result.append(y[i])
    i += 1
    result += y[i:]
    result += z[j:]
    return result

    def quick_sort(a):
    if len(a) <= 1:
    return a
    else:
    return quick_sort([x for x in a[1:] if x < a[0]]) + [a[0]] \
    + quick_sort([x for x in a[1:] if x >= a[0]])

    if __name__ == '__main__':
    a = [7, 10, 1, 1, 3, 4, 5, 9, 2, 8]
    b = {}
    for i in range(1, 6):
    b['test'+str(i)] = a[:]
    # Test the three simple sortings
    insertion_sort(b['test1']) #1
    selection_sort(b['test2']) #2
    shell_sort(b['test3']) #3
    print b
    # Test the sortings that requires recursion
    print merge_sort(b['test4']) #4
    print quick_sort(b['test5']) #5
    # Timsort that is native in Python
    a.sort() #6
    print a
    11月 132013
     
  • Unique String
  • #-------------------------------------------------------------------------------
    # Name: Unique String
    # Purpose: Find if a string has all unique characters or not
    #
    #-------------------------------------------------------------------------------

    # Solution 1
    def is_unique(s):
    a = [False]*256
    for n in s:
    # Use the ord() function to find the ASCII value of a character
    if a[ord(n)]:
    return False # jump out of the loop
    a[ord(n)] = True
    return True

    # Solution 2
    def is_unique2(s):
    a = {}
    for x in s:
    try:
    a[x] += 1
    return False
    except:
    a[x] = 1
    return True

    if __name__ == "__main__":
    testcases = ["abcdefg", "abcdefga", "5523231"]
    for case in testcases:
    print is_unique(case)
    print is_unique2(case)
    • Two Sum
    #-------------------------------------------------------------------------------
    # Name: Two Sum
    # Purpose: Given an array of integers, find two numbers
    # such that they add up to a specific target number
    #
    #-------------------------------------------------------------------------------

    # Solution 1
    def two_sum(a, target):
    res = []
    for i in range(len(a)):
    for j in range(i+1, len(a)):
    if a[i] + a[j] == target:
    res.append([a[i], a[j]])
    return res

    # Solution 2
    def two_sum2(a, target):
    h = {}
    res = []
    for x in a:
    if h.has_key(x):
    res.append([target-x, x])
    h[target - x] = x
    return res

    if __name__ == "__main__":
    testcase = [1, 2, 4, 3, 10, 9]
    target = 5
    print two_sum(testcase, target)
    print two_sum2(testcase, target)
    • Longest Consecutive Sequence
    #-------------------------------------------------------------------------------
    # Name: Longest Consecutive Sequence
    # Purpose: Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
    #
    # For example,
    # Given [100, 4, 200, 1, 3, 2],
    # The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
    #
    # Your algorithm should run in O(n) complexity.
    #-------------------------------------------------------------------------------

    def find_lgst(a):
    h = {} # use a hash table
    st = set(a) # use a hash set
    cnt = 0
    for x in a: # iteration is O(n)
    h[x] = 1
    right = x + 1
    left = x - 1
    while right in st: # search in a hash set is O(1)
    st.discard(right) # reduce the size and increase speed
    h[x] += 1
    right +=1
    while left in st:
    st.discard(left) # reduce the size and increase speed
    h[x] += 1
    left -= 1
    cnt = max(cnt, h[x])
    return cnt # don't use max(h.values()), which is not O(n)

    if __name__ == '__main__':
    a = [100, 4, 200, 1, 3, 2, 5, 2321, 6, 9, 10, 42343, 10, 7, 32424, 8]
    print find_lgst(a)
    • Longest Common Prefix
    #-------------------------------------------------------------------------------
    # Name: Longest Common Prefix
    # Purpose: Write a function to find the longest common prefix string amongst an array of strings.
    #
    #-------------------------------------------------------------------------------

    def find_prefix(a):
    h = {}
    prefix = ''
    for s in a:
    for i, x in enumerate(s):
    key = str(i) + x
    try:
    h[key] += 1
    except:
    h[key] = 1
    # Recover the character and the order from the key
    for key in sorted(h, key=lambda x: int(x[0:-1])):
    if h[key] != len(a):
    return prefix
    prefix += key[-1]
    return prefix

    if __name__ == "__main__":
    a = ['ab', 'abc', 'abaffsfas']
    b = ["a"]
    c = ["c", "c"]
    d = []
    e = ["aca","cba"]
    g = ["abab","aba","abc"]
    print find_prefix(a)
    print find_prefix(b)
    print find_prefix(c)
    print find_prefix(d)
    print find_prefix(e)
    print find_prefix(g)
    • First Missing Positive
    #-------------------------------------------------------------------------------
    # Name: First Missing Positive
    # Purpose: Given an unsorted integer array, find the first missing positive integer.
    #
    # For example,
    # Given [1,2,0] return 3,
    # and [3,4,-1,1] return 2.
    #
    # Your algorithm should run in O(n) time and uses constant space.
    #
    #-------------------------------------------------------------------------------
    def fst_mis( a):
    if len(a) == 0:
    return 1
    st = set(range(1, len(a)+1))
    for x in a:
    if x in st:
    st.discard(x)
    if len(st) == 0:
    return max(a) + 1
    return st.pop()

    if __name__ == "__main__":
    test1 = []
    test2 = [1,2,0]
    test3 = [3,4,-1,1]
    print fst_mis(test1)
    print fst_mis(test2)
    print fst_mis(test3)
    11月 102013
     
    1. Translate the numbers to an array of integer to avoid stack overflow
    2. Use while to control flow once the iteration times are unknown
    3. Apply % and \ to retrieve digits from a integer
    4. Be careful of the direction of the iteration

    • Reverse Integer
    Reverse digits of an integer.
    Example1: x = 123, return 321
    Example2: x = -123, return -321
    def rev_int(a):
    negative = False
    result = 0
    if a == 0:
    return a
    if a < 0:
    negative = True
    a = -a
    while a > 0:
    result = result*10 + a%10
    a /= 10
    if negative:
    return -result
    return result

    if __name__ == "__main__":
    print rev_int(123)
    print rev_int(-4124324)
    • Multiply Strings
    Given two numbers represented as strings, return multiplication of the numbers as a string.
    Note: The numbers can be arbitrarily large and are non-negative.
    class multiply:
    def mul(self, int1, int2):
    a = self.toArray(int1)
    b = self.toArray(int2)
    c = [0]*(len(a) + len(b))
    d = [0]*(len(a) + len(b))
    for i in range(len(a)):
    for j in range(len(b)):
    p = a[i] * b[j]
    c[i+j+1] += p
    rem = 0
    for i in reversed(range(len(c))):
    c[i] += rem
    carry = c[i]%10
    rem = c[i]/10
    d[i] = carry
    return self.toInt(d)

    def toArray(self, n):
    result = []
    while n > 0:
    a = n%10
    result.append(int(a)) # a is possibly a long type given the value of n
    n = n/10
    return [x for x in reversed(result)]

    def toInt(self, a):
    y = 0
    for i in range(len(a)):
    mul = 10**( len(a)-1-i )
    y += a[i]*mul
    return y

    if __name__ == "__main__":
    a = multiply()
    # Testcase1
    print a.mul(9934248, 983204442)
    print 9934248*983204442
    # Testcase2
    print a.mul(1, 2)
    • Valid Number
    Validate if a given string is numeric.
    Some examples:
    “0” => true
    “ 0.1 “ => true
    “abc” => false
    “1 a” => false
    “2e10” => true
    def valid_num(a):
    try:
    a = float(a)
    except:
    return False
    return True
    • Add Binary
    Given two binary strings, return their sum (also a binary string).
    For example,
    a = “11”
    b = “1”
    Return “100”.
    def bin_add(a, b):
    if len(a) < len(b):
    a, b = b, a
    c = [0]*len(a)
    b = '0'*(len(a)-len(b)) + b

    carry = 0
    for i in range(len(a)):
    index = -i - 1 # from the right to the left
    c[index] = carry + int(a[index]) + int(b[index])
    carry = 0
    if c[index] == 2:
    c[index] = 0
    carry = 1
    if i == len(a) - 1:
    c.insert(0, 1)
    return ''.join([str(x) for x in c])

    if __name__ == "__main__":
    print bin_add('1', '1001')
    print bin_add('11', '1')
    print bin_add('0', '0')
    • Plus one
    def plus_one(a):
    # Error case and bad case
    if not isinstance(a, list) or len(a) == 0:
    raise ValueError
    # Normal case
    for i in reversed(range(len(a))):
    if a[i] == 9:
    a[i] = 0
    else:
    a[i] += 1
    return a
    # Special case
    a.insert(0, 1)
    return a

    if __name__ == "__main__":
    testcase1 = [1, 2, 3, 4]
    print plus_one(testcase1)
    testcase2 = [8, 9, 9, 9]
    print plus_one(testcase2)
    testcase3 = [9, 9, 9, 9]
    print plus_one(testcase3)
    testcase4 = 0
    print plus_one(testcase4)
    • Count and Say
    The count-and-say sequence is the sequence of integers beginning as follows:
    1, 11, 21, 1211, 111221, …
    1 is read off as “one 1” or 11.
    11 is read off as “two 1s” or 21.
    21 is read off as “one 2, then one 1” or 1211.
    Given an integer n, generate the nth sequence.
    def read(a):
    # The array for counter and value
    current = [0, 10]
    result = []
    for i in range(len(a)+1):
    if i == len(a):
    result += current
    return result[2:] # return result from the last loop
    if a[i] == current[1]:
    current[0] += 1
    else:
    result += current
    current[1] = a[i]
    current[0] = 1
    carrier = a[i]

    def cnt_say(n):
    # Set the initial seed
    result = [1]
    for i in range(n):
    result = read(result)
    # Return the result as a string
    return ''.join(str(x) for x in result)

    if __name__ == "__main__":
    for i in range(10):
    print cnt_say(i)
    • Read Numbers
    1 -> one
    100 -> one hundred
    500234 -> five hundred thousand two hundred thirty four
    1232232 -> 1 million two hundred ….
    def read_piece(s):
    if len(s) < 2:
    return s
    return s[0] + ' hundred ' + s[1:]

    def read(s):
    alen = len(s)
    read2 = {0: '', 1: 'thousand', 2: 'million', 3: 'billion', 4: 'trillion'}
    b = []
    result = []
    while alen > 0:
    low = max(0, alen-3)
    high = alen
    b.append(s[low: high])
    alen -= 3

    for i, x in enumerate(reversed(b)):
    index = len(b) - i - 1
    result += [read_piece(x), read2[index]]
    return ' '.join(n for n in result)
    11月 042013
     
    The functions such as max() and min() play a role such as
    if a < b:
    a = b
    Using them in programing will bring flexibility and simply coding.

    1. Best Time to Buy and Sell Stock Total

    Say you have an array for which the ith element is the price of a given stock on day i.
    If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
    The stock prices fluctuate, which results into profitable gaps(see the graph). The first question only wants to capture the possible profit given only one transaction. There are two other variants originating from it: unlimited transactions and two transactions.
    from ggplot import *
    import pandas as pd

    # If the stock could be traded just once
    from sys import maxint
    def stock1(a):
    min_price = maxint
    max_profit = 0
    for x in a:
    min_price = min(x, min_price)
    max_profit = max(x - min_price, max_profit)
    return max_profit

    def stock1A(a):
    max_price = 0
    max_profit = 0
    for x in reversed(a):
    max_price = max(x, max_price)
    max_profit = max(max_price - x, max_profit)
    return max_profit

    #------------------------EXTENSION--------------------------------------------
    # If the stock could be traded multiple times and you can only have one stock all time
    def stock2(a):
    max_profit = 0
    for i in range(len(a)):
    profit = max(a[i] - a[i-1], 0)
    max_profit += profit
    return max_profit

    # If the stock could be traded at most twice and you can only have one stock all time
    from collections import defaultdict
    def stock3(a):
    min_price = maxint
    fst_max_profit = 0
    h = defaultdict(list)
    for i in range(len(a)):
    min_price = min(a[i], min_price)
    fst_max_profit = max(a[i] - min_price, fst_max_profit)
    h[i].append(fst_max_profit)
    max_price = 0
    snd_max_profit = 0
    for i in reversed(range(len(a))):
    max_price = max(a[i], max_price)
    snd_max_profit = max(max_price - a[i], snd_max_profit)
    h[i].append(snd_max_profit)
    return max([sum(h[i]) for i in h.keys()])

    if __name__ == "__main__":
    a = [1, 3, 6, 3, 1, 2, 4, 4, 2, 5]
    print stock1(a)
    print stock1A(a)
    print stock2(a)
    print stock3(a)

    # Draw the plot of stock price
    df = pd.DataFrame()
    df['price'] = a
    df['day'] = df.index + 1
    print ggplot(aes(x='day', y='price'), data = df) + geom_line()

    2. Minimum Window Substring

    Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
    For example,
    S = “ADOBECODEBANC”
    T = “ABC”
    Minimum window is “BANC”.
    def min_wds(s, t):
    if not isinstance(s, str) or not isinstance(t, str):
    raise ValueError("Must be strings")
    if len(s) == 0 or len(t) == 0:
    return ""
    a = {}
    for i in xrange(len(s)):
    try:
    a[s[i]] = i
    except:
    pass
    start = len(s)
    end = 0
    cnt = 0
    for x in t:
    if a.has_key(x):
    start = min(start, a[x])
    end = max(end, a[x])
    cnt += 1
    if cnt == len(t):
    return s[start:end+1]
    return ""

    if __name__ == '__main__':
    print min_wds("ADOBECODEBANC", "ABC")

    3. Maximum Subarray

    Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
    For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
    the contiguous subarray [4,−1,2,1] has the largest sum = 6.
    This question only asks about the maximum length for the non-repetitive subarray. Thus, two max functions will solve it quick.
    from sys import maxint
    def find_max(A):
    overall_max = -maxint
    running_max = 0
    for x in A:
    running_max += x
    running_max = max(0, running_max)
    overall_max = max(running_max, overall_max)
    return overall_max

    if __name__ == "__main__":
    a = [-2,1,-3,4,-1,2,1,-5,4]
    print find_max(a)