mzh/blog

最近一些面试题(Python)

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

骑士巡游问题

一道简单的BFS(广度优先)算法题

在一个国际象棋棋盘上 (N*N),有一个棋子”马(Knight)“,处在任意位置(x, y); 马的走法是日字型,即其可以在一个方向上前进或后退两格,在另一方向上前 进或 后退一格。 请编程找出马如何从位置(x, y)走到棋盘右下角(N, N)的位置的步骤。 例如:假设棋盘大小为3*3,马处在(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)的复杂度,我当时的水平最多写得出这个源里的程度。用的是dict的popitem,而且是面试官说在生产系统中也使用这样的方法。 后来,仔细看了Python Cookbook(知道是好书了吧),发现collections的deque神器,不过正反向双list也是个不错的ADT选择,而且这些连面试官都不知道。 具体的应用以后写读书笔记时会和大家分享下的。