python面试攻略（coding篇）

1.台阶问题/斐波那契

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少中跳法：

fib = lambda n: n if n <= 2 else fib(n - 1) + fib(n - 2)

第二种方法：

def memo(func):
   cache = {}
   def wrap(*args):
       if args not in cache:
           cache[args] = func(*args)
       return cache[args]
   return wrap
 
 
@memo
def fib(i):
   if i < 2:
       return 1
   return fib(i-1) + fib(i-2)

第三种方法：

def fib(n):
   a, b = 0, 1
   for _ in range(n):
       a, b = b, a + b
   return b

2.去除列表中的重复元素

用集合

list(set(l))

用字典

l1 = ['b','c','d','b','c','a','a']
l2 = {}.fromkeys(l1).keys()
print (l2)

列表推导式

l1 = ['b','c','d','b','c','a','a']
l2 = []
[l2.append(i) for i in l1 if not i in l2]

3.合并两个有序列表

尾递归

def _recursion_merge_sort2(l1, l2, tmp):
   if len(l1) == 0 or len(l2) == 0:
       tmp.extend(l1)
       tmp.extend(l2)
       return tmp
   else:
       if l1[0] < l2[0]:
           tmp.append(l1[0])
           del l1[0]
       else:
           tmp.append(l2[0])
           del l2[0]
       return _recursion_merge_sort2(l1, l2, tmp)
 
def recur