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 Trueif __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 cif __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 1def 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 2def two_sum2(numbers, target):    res = *2    hashmap = {}     for i in range(len(numbers)):        if hashmap.has_key(numbers[i]):            index = hashmap.get(numbers[i])            res = index+1 ;            res = i+1;            return res        else:            hashmap[target - numbers[i]] = i    return resif __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 1def set_zero(a):    # Use two lists as buffer    row = *len(a)    col = *len(a)    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 2import 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 aif __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 1def permu(s):    permutation = []    # Error case    if s == None:        return None    # Bad case    elif len(s) == 0:        permutation.append("")        return permutation    # Normal case    first = s    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 2from itertools import permutationsdef permu2(s):    permutation = []    for x in permutations(s):        permutation.append(''.join(x))    return permutationif __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 Iterabledef 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 xif __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 wrapperdef ingredients(func):    def wrapper():        print "#tomatoes#"        func()        print "~salad~"    return wrapper@bread@ingredientsdef sandwich(food="--ham--"):    print foodif __name__ == "__main__":    sandwich()``

### 9. Class

Implement a queue
``from array import arrayclass 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 aif __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`` ``#-------------------------------------------------------------------------------# 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 -= 1def 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 /= 3def 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 resultdef quick_sort(a):     if len(a) <= 1:          return a     else:          return quick_sort([x for x in a[1:] if x < a]) + [a] \                + quick_sort([x for x in a[1:] if x >= a])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`` • Unique String
• ``#-------------------------------------------------------------------------------# Name:       Unique String# Purpose:   Find if a string has all unique characters or not##-------------------------------------------------------------------------------# Solution 1def 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 2def is_unique2(s):    a = {}    for x in s:       try:            a[x] += 1            return False       except:            a[x] = 1    return Trueif __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 1def 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 2def 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 resif __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 prefixif __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)`` 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 resultif __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 = *(len(a) + len(b))        d = *(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 yif __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``
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 = *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 aif __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:            current += 1        else:            result += current            current = a[i]            current = 1        carrier = a[i]def cnt_say(n):    # Set the initial seed    result =     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)``
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 + ' 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)`` 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 oncefrom sys import maxintdef 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_profitdef 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 timedef 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 timefrom collections import defaultdictdef 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,
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 maxintdef 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_maxif __name__ == "__main__":    a = [-2,1,-3,4,-1,2,1,-5,4]    print find_max(a)``  数据挖掘过程一个重要环节就是展会数据挖掘结果，譬如将数据挖掘的结果直观的展示给需求方或者用户，进行数据结果进行直观上的测试，这样方便沟通，交换意见。常用的处理方法，就是开发一个展示数据挖掘结果信息的查询页面，或者可视化信息展示。面临的问题，大数据查询，譬如10亿条数据，一般搞个数据库也能承受，分库处理，或者采用一些nosql的方法，hbasecassandra等存储。

python + web.py + mysql

麻雀虽小五脏俱全

1 python基本编程

2 mysql数据库

3 web.py web框架原理

4 基本的html

入口：

1 后期需要处理可视化展示，常见的信息可视化方法，要拿起毕业论文的内容了

2 大数据检索（10亿）

3 python webpy深入学习，功能更多的web开发 青春就应该这样绽放  游戏测试：三国时期谁是你最好的兄弟！！  你不得不信的星座秘密   Pandas is an emerging open source framework on Python and a substitute to R. Both apply a data structure called DataFrame. Although their data frames look quite similar, there are some cautions for a R programmer who like to play Pandas. A few examples are listed in the table below.
• Pandas mostly uses the syntax of `a.b.c()`, while R uses the nesting parenthesis like `a(b(c()))`. The dot separation actually has no sense in R.
• Python's indexes start from zero, while R's indexes begin with one. The first element in a data frame of Pandas is `mydata.ix[0, 0]`, while the counterpart in R is `mydata[1, 1]`.
• Pandas has to use DataFrame's *ix property to allow two-way indexing, while R has no such limit.
PurposeRPandas
view data`head(mydata, 3)``mydata.head(3)`
summary statistics`summary(mydata)``mydata.describe()`
transpose data`t(mydata)``mydata.T`
sort by two variables`mydata[order(A, -B)]``mydata.sort(['A', 'B'], ascending=[1, 0])`
select the first element`mydata[1, 1]``mydata.ix[0, 0]`
select a column by label`mydata['A']``mydata['A']`
select first 3 rows`mydata[1:3,]``mydata[0:3]`
select first 3 columns`mydata[, 1:3]``mydata.ix[:, 0:3]`
select by a variable`mydata[mydata\$A > 10,]``mydata[mydata.A > 10]`
select by all variables`mydata[mydata > 10,]``mydata[mydata > 10]` 