最近换工作，面了几家公司，超大，大，中，小都有，不过就不提名字了。 唯一的感触就是自己实在是太浪费四年的时间在游戏上了，要是腾出时间搞算法那是极好啊。
不过我总觉得知识的欠缺是可以通过学习来弥补的，同时，记录也是学习的一部分，现在我就写写我还记得的几道面试题。

骑士巡游问题

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

在一个国际象棋棋盘上 (NN)，有一个棋子"马(Knight)"，处在任意位置(x, y)；
马的走法是日字型，即其可以在一个方向上前进或后退两格，在另一方向上前 进或 后退一格。 请编程找出马如何从位置(x, y)走到棋盘右下角(N,
N)的位置的步骤。 例如：假设棋盘大小为33，马处在（1，2）位置，马只需要走一步， 即 (1,2)-> (3,3)即可到达目的地。

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

Fibonacci数列

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

用Python生成指定长度的斐波那契数列

考递归：

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缓存

现场编程题，1小时之内写出可用的LRU cache util

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