骑士巡游问题

一道简单的BFS（广度优先）算法题

具体代码我已经push到github上了，链接在此
对于从来没有研究过算法的我来说，整个题目的难处在理解队列这个概念上。
广度优先的队列之奇妙的地方在于，每一层的尝试，都先放入队列中，紧接着，挨个判断队列中的元素是否达成了目标。对，就这么简单。

Fibonacci数列

好吧～两家公司都考这斐波那契……

考递归：

 def fib_recursion(n):

    if 0< = n < 2:
        return 1
    else:
        return fib_recursion(n-1)+fib_recursion(n-2)
print fib_recursion(99) # 调用即可

不错吧～完美地使用了递归，当然，如果能用字典存储，这样更完美了对吧？
错！
其实考的是iterable的使用，Python CookBook 19.3里那极为精妙的解法才可以称得上答案：

 def fib():
    x, y = 0,1
    while True:
        yield x
        x, y = y,x+y

if __name__ == '__main__':
    import itertools
    print list(itertools.islice(fib(), 10))

LRU缓存

其实当场没有写出来，主要是因为还不清楚list的pop()中如果有数字的话，就是O(n)的复杂度，我当时的水平最多写得出这个源里的程度。用的是dict的popitem，而且是面试官说在生产系统中也使用这样的方法。
后来，仔细看了Python Cookbook（知道是好书了吧），发现collections的deque神器，不过正反向双list也是个不错的ADT选择，而且这些连面试官都不知道。
具体的应用以后写读书笔记时会和大家分享下的。

Python如何查找Follow关系

Twitter中Follower和Followee，现需要找到互相关注的两个人（不关心顺序）
例如：现有列表

 l = [(1, 2), (2, 3), (3, 2), (3, 4), (4, 1),
(4, 3), (4, 3)]

可以通过下列函数生成

def gen_pairs():
    return (random.randint(0, 30), random.randint(0, 30))

l = [gen_pairs() for x in xrange(20)]

解法一：

import collections
[x for x, y in collections.Counter([tuple(sorted(x)) for x in l]).iteritems() if y > 1]

[tuple(sorted(x)) for x in l] 首先是将列表的内容按小到大重新排列
通过计数器collections.Counter，来统计重复的数量
if y > 1 将大于一个的放入结果集中

最后统计用时best of 3: 38.9 ?s per loop

老湿，还能给力点吗？

解法二：
Stackover上的解答

[x for x in set_l if x[::-1] in set(l)]

快了6倍……答主说到这个算法最快也就是O(n)了，因为必须遍历所有项有木有啊

第47节：辗转相除法

或称欧几里得求最大公约数算法

#!/usr/bin/env python
# encoding: utf-8

def Euclid(x, y):
    if x < y:
        tmp = x
        x = y
        y = tmp

    while y != 0:
        rod = x % y
        x = y
        y = rod
    return x

if __name__ == '__main__':
    print Euclid(126, 90) # should be 18

第50节：桶排序

#!/usr/bin/env python
# encoding: utf-8

def bucket_sort(lis):

    max_item = max(lis)
    bucket = [-1 for x in xrange(max_item+1)]

    for item in lis:
        if item < 0:
            raise ValueError("Can't handle %d" % item)
        bucket[int(item)] = item

    return filter(lambda x: x != -1, bucket)

if __name__ == '__main__':
    print bucket_sort([8,2,1,5,9,7])  # should be [1,2,5,7,8,9]

第51节：基位排序——桶排序的升级版

#!/usr/bin/env python
# encoding: utf-8
from copy import deepcopy

def bit_sort(lis):

    bucket = [[] for x in xrange(len(lis))]
    k = len(str(max(lis))) # sort time
    array = [deepcopy(bucket) for x in xrange(k)]

    for time in xrange(k):
        if time == 0:
            for l in lis:
                array[0][int(str(l)[-1])].append(l)
        else:
            for b in array[time-1]:
                for item in b:
                    try:
                        array[time][int(str(item)[-1-time])].append(item)
                    except IndexError:
                        array[time][0].append(item)
    return array

if __name__ == '__main__':
    for line in bit_sort([123, 602, 82, 777, 57, 510, 396, 196, 843, 138]):
        print line
    print "The Last line should be:[[57, 82], [123, 138, 196], [], [396], [], [510], [602], [777], [843], []]"

原文：http://mengzhuo.org/blog/%E6%9C%80%E8%BF%91%E4%B8%80%E4%BA%9B%E9%9D%A2%E8%AF%95%E9%A2%98%EF%BC%88python%EF%BC%89.html

com_vip