InterviewFAQ-python

Python语言特性

1 Python的函数参数传递

a = 1
def fun(a):
 a = 2
fun(a)
print a # 1

a = []
def fun(a):
 a.append(1)
fun(a)
print a # [1]

a = 1
def fun(a):
 print "func_in",id(a) # func_in 41322472
 a = 2
 print "re-point",id(a), id(2) # re-point 41322448 41322448
print "func_out",id(a), id(1) # func_out 41322472 41322472
fun(a)
print a # 1

a = []
def fun(a):
 print "func_in",id(a) # func_in 53629256
 a.append(1)
print "func_out",id(a) # func_out 53629256
fun(a)
print a # [1]

2 Python中的元类(metaclass)

3 @staticmethod和@classmethod

def foo(x):
 print "executing foo(%s)"%(x)
class A(object):
 def foo(self,x):
 print "executing foo(%s,%s)"%(self,x)
 @classmethod
 def class_foo(cls,x):
 print "executing class_foo(%s,%s)"%(cls,x)
 @staticmethod
 def static_foo(x):
 print "executing static_foo(%s)"%x
a=A()

4 类变量和实例变量

class Test(object): 
 num_of_instance = 0 
 def __init__(self, name): 
 self.name = name 
 Test.num_of_instance += 1 
 
if __name__ == '__main__': 
 print Test.num_of_instance # 0
 t1 = Test('jack') 
 print Test.num_of_instance # 1
 t2 = Test('lucy') 
 print t1.name , t1.num_of_instance # jack 2
 print t2.name , t2.num_of_instance # lucy 2

class Person:
 name="aaa"
p1=Person()
p2=Person()
p1.name="bbb"
print p1.name # bbb
print p2.name # aaa
print Person.name # aaa

class Person:
 name=[]
p1=Person()
p2=Person()
p1.name.append(1)
print p1.name # [1]
print p2.name # [1]
print Person.name # [1]

5 Python自省

a = [1,2,3]
b = {'a':1,'b':2,'c':3}
c = True
print type(a),type(b),type(c) # <type 'list'> <type 'dict'> <type 'bool'>
print isinstance(a,list) # True

6 字典推导式

d = {key: value for (key, value) in iterable}

7 Python中单下划线和双下划线

>>> class MyClass():
... def __init__(self):
... self.__superprivate = "Hello"
... self._semiprivate = ", world!"
...
>>> mc = MyClass()
>>> print mc.__superprivate
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
AttributeError: myClass instance has no attribute '__superprivate'
>>> print mc._semiprivate
, world!
>>> print mc.__dict__
{'_MyClass__superprivate': 'Hello', '_semiprivate': ', world!'}

8 字符串格式化:%和.format

"hi there %s" % name

"hi there %s" % (name,) # 提供一个单元素的数组而不是一个参数

9 迭代器和生成器

>>> L = [x*x for x in range(10)]
>>> L
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
>>> g = (x*x for x in range(10))
>>> g
<generator object <genexpr> at 0x0000028F8B774200>

10 *args and **kwargs

>>> def print_everything(*args):
 for count, thing in enumerate(args):
... print '{0}. {1}'.format(count, thing)
...
>>> print_everything('apple', 'banana', 'cabbage')
0. apple
1. banana
2. cabbage

>>> def table_things(**kwargs):
... for name, value in kwargs.items():
... print '{0} = {1}'.format(name, value)
...
>>> table_things(apple = 'fruit', cabbage = 'vegetable')
cabbage = vegetable
apple = fruit

def table_things(titlestring, **kwargs)

>>> def print_three_things(a, b, c):
... print 'a = {0}, b = {1}, c = {2}'.format(a,b,c)
...
>>> mylist = ['aardvark', 'baboon', 'cat']
>>> print_three_things(*mylist)
a = aardvark, b = baboon, c = cat

11 面向切面编程AOP和装饰器

12 鸭子类型

13 Python中重载

14 新式类和旧式类

class A():
 def foo1(self):
 print "A"
class B(A):
 def foo2(self):
 pass
class C(A):
 def foo1(self):
 print "C"
class D(B, C):
 pass
d = D()
d.foo1()
# A

15 __new__和__init__的区别

16 单例模式

1 使用__new__方法

class Singleton(object):
 def __new__(cls, *args, **kw):
 if not hasattr(cls, '_instance'):
 orig = super(Singleton, cls)
 cls._instance = orig.__new__(cls, *args, **kw)
 return cls._instance
class MyClass(Singleton):
 a = 1

2 共享属性

class Borg(object):
 _state = {}
 def __new__(cls, *args, **kw):
 ob = super(Borg, cls).__new__(cls, *args, **kw)
 ob.__dict__ = cls._state
 return ob
class MyClass2(Borg):
 a = 1

3 装饰器版本

def singleton(cls, *args, **kw):
 instances = {}
 def getinstance():
 if cls not in instances:
 instances[cls] = cls(*args, **kw)
 return instances[cls]
 return getinstance
@singleton
class MyClass:
 ...

4 import方法

# mysingleton.py
class My_Singleton(object):
 def foo(self):
 pass
my_singleton = My_Singleton()
# to use
from mysingleton import my_singleton
my_singleton.foo()

17 Python中的作用域

18 GIL线程全局锁

19 协程

20 闭包

21 lambda函数

22 Python函数式编程

>>>a = [1,2,3,4,5,6,7]
>>>b = filter(lambda x: x > 5, a)
>>>print b
>>>[6,7]

>>> a = map(lambda x:x*2,[1,2,3])
>>> list(a)
[2, 4, 6]

>>> reduce(lambda x,y:x*y,range(1,4))
6

23 Python里的拷贝

import copy
a = [1, 2, 3, 4, ['a', 'b']] #原始对象
b = a #赋值,传对象的引用
c = copy.copy(a) #对象拷贝,浅拷贝
d = copy.deepcopy(a) #对象拷贝,深拷贝
a.append(5) #修改对象a
a[4].append('c') #修改对象a中的['a', 'b']数组对象
print 'a = ', a
print 'b = ', b
print 'c = ', c
print 'd = ', d
输出结果:
a = [1, 2, 3, 4, ['a', 'b', 'c'], 5]
b = [1, 2, 3, 4, ['a', 'b', 'c'], 5]
c = [1, 2, 3, 4, ['a', 'b', 'c']]
d = [1, 2, 3, 4, ['a', 'b']]

24 Python垃圾回收机制

1 引用计数

2 标记-清除机制

3 分代技术

25 Python的List

26 Python的is

27 read,readline和readlines

28 Python2和3的区别

29 super init

30 range and xrange

31 单线程+异步I/O

32 Django

33 爬虫

编程题

1 台阶问题/斐波那契

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 xrange(n):
 a, b = b, a + b
 return b

2 变态台阶问题

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

3 矩形覆盖

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

4 杨氏矩阵查找

def get_value(l, r, c):
 return l[r][c]
def find(l, x):
 m = len(l) - 1
 n = len(l[0]) - 1
 r = 0
 c = n
 while c >= 0 and r <= m:
 value = get_value(l, r, c)
 if value == x:
 return True
 elif value > x:
 c = c - 1
 elif value < x:
 r = r + 1
 return False

5 去除列表中的重复元素

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 = list(set(l1))
l2.sort(key=l1.index)
print l2

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

6 链表成对调换

class ListNode:
 def __init__(self, x):
 self.val = x
 self.next = None
class Solution:
 # @param a ListNode
 # @return a ListNode
 def swapPairs(self, head):
 if head != None and head.next != None:
 next = head.next
 head.next = self.swapPairs(next.next)
 next.next = head
 return next
 return head

7 创建字典的方法

1 直接创建

dict = {'name':'earth', 'port':'80'}

2 工厂方法

items=[('name','earth'),('port','80')]
dict2=dict(items)
dict1=dict((['name','earth'],['port','80']))

3 fromkeys()方法

dict1={}.fromkeys(('x','y'),-1)
dict={'x':-1,'y':-1}
dict2={}.fromkeys(('x','y'))
dict2={'x':None, 'y':None}

8 合并两个有序列表

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 recursion_merge_sort2(l1, l2):
 return _recursion_merge_sort2(l1, l2, [])

def loop_merge_sort(l1, l2):
 tmp = []
 while len(l1) > 0 and len(l2) > 0:
 if l1[0] < l2[0]:
 tmp.append(l1[0])
 del l1[0]
 else:
 tmp.append(l2[0])
 del l2[0]
 tmp.extend(l1)
 tmp.extend(l2)
 return tmp

a = [1,2,3,7]
b = [3,4,5]
def merge_sortedlist(a,b):
 c = []
 while a and b:
 if a[0] >= b[0]:
 c.append(b.pop(0))
 else:
 c.append(a.pop(0))
 while a:
 c.append(a.pop(0))
 while b:
 c.append(b.pop(0))
 return c
print merge_sortedlist(a,b)
 

9 交叉链表求交点

# 使用a,b两个list来模拟链表,可以看出交叉点是 7这个节点
a = [1,2,3,7,9,1,5]
b = [4,5,7,9,1,5]
for i in range(1,min(len(a),len(b))):
 if i==1 and (a[-1] != b[-1]):
 print "No"
 break
 else:
 if a[-i] != b[-i]:
 print "交叉节点:",a[-i+1]
 break
 else:
 pass

class ListNode:
 def __init__(self, x):
 self.val = x
 self.next = None
def node(l1, l2):
 length1, lenth2 = 0, 0
 # 求两个链表长度
 while l1.next:
 l1 = l1.next
 length1 += 1
 while l2.next:
 l2 = l2.next
 length2 += 1
 # 长的链表先走
 if length1 > lenth2:
 for _ in range(length1 - length2):
 l1 = l1.next
 else:
 for _ in range(length2 - length1):
 l2 = l2.next
 while l1 and l2:
 if l1.next == l2.next:
 return l1.next
 else:
 l1 = l1.next
 l2 = l2.next

#coding:utf-8
class ListNode:
 def __init__(self, x):
 self.val = x
 self.next = None
def node(l1, l2):
 length1, length2 = 0, 0
 # 求两个链表长度
 while l1.next:
 l1 = l1.next#尾节点
 length1 += 1
 while l2.next:
 l2 = l2.next#尾节点
 length2 += 1
 #如果相交
 if l1.next == l2.next:
 # 长的链表先走
 if length1 > length2:
 for _ in range(length1 - length2):
 l1 = l1.next
 return l1#返回交点
 else:
 for _ in range(length2 - length1):
 l2 = l2.next
 return l2#返回交点
 # 如果不相交
 else:
 return

10 二分查找

#coding:utf-8
def binary_search(list,item):
 low = 0
 high = len(list)-1
 while low<=high:
 mid = (low+high)/2
 guess = list[mid]
 if guess>item:
 high = mid-1
 elif guess<item:
 low = mid+1
 else:
 return mid
 return None
mylist = [1,3,5,7,9]
print binary_search(mylist,3)

11 快排

#coding:utf-8
def quicksort(list):
 if len(list)<2:
 return list
 else:
 midpivot = list[0]
 lessbeforemidpivot = [i for i in list[1:] if i<=midpivot]
 biggerafterpivot = [i for i in list[1:] if i > midpivot]
 finallylist = quicksort(lessbeforemidpivot)+[midpivot]+quicksort(biggerafterpivot)
 return finallylist
print quicksort([2,4,6,7,1,2,5])

12 找零问题

#coding:utf-8
#values是硬币的面值values = [ 25, 21, 10, 5, 1]
#valuesCounts 钱币对应的种类数
#money 找出来的总钱数
#coinsUsed 对应于目前钱币总数i所使用的硬币数目
def coinChange(values,valuesCounts,money,coinsUsed):
 #遍历出从1到money所有的钱数可能
 for cents in range(1,money+1):
 minCoins = cents
 #把所有的硬币面值遍历出来和钱数做对比
 for kind in range(0,valuesCounts):
 if (values[kind] <= cents):
 temp = coinsUsed[cents - values[kind]] +1
 if (temp < minCoins):
 minCoins = temp
 coinsUsed[cents] = minCoins
 print ('面值:{0}的最少硬币使用数为:{1}'.format(cents, coinsUsed[cents]))

13 广度遍历和深度遍历二叉树

14 二叉树节点

class Node(object):
 def __init__(self, data, left=None, right=None):
 self.data = data
 self.left = left
 self.right = right
tree = Node(1, Node(3, Node(7, Node(0)), Node(6)), Node(2, Node(5), Node(4)))

15 层次遍历

def lookup(root):
 row = [root]
 while row:
    print(row)
    row = [kid for item in row for kid in (item.left, item.right) if kid]

16 深度遍历

def deep(root):
 if not root:
 return
 print root.data
 deep(root.left)
 deep(root.right)
if __name__ == '__main__':
 lookup(tree)
 deep(tree)

17 前中后序遍历

#coding:utf-8
#二叉树的遍历
#简单的二叉树节点类
class Node(object):
 def __init__(self,value,left,right):
 self.value = value
 self.left = left
 self.right = right
#中序遍历:遍历左子树,访问当前节点,遍历右子树
def mid_travelsal(root):
 if root.left is None:
 mid_travelsal(root.left)
 #访问当前节点
 print(root.value)
 if root.right is not None:
 mid_travelsal(root.right)
#前序遍历:访问当前节点,遍历左子树,遍历右子树
def pre_travelsal(root):
 print (root.value)
 if root.left is not None:
 pre_travelsal(root.left)
 if root.right is not None:
 pre_travelsal(root.right)
#后续遍历:遍历左子树,遍历右子树,访问当前节点
def post_trvelsal(root):
 if root.left is not None:
 post_trvelsal(root.left)
 if root.right is not None:
 post_trvelsal(root.right)
 print (root.value)

18 求最大树深

def maxDepth(root):
 if not root:
 return 0
 return max(maxDepth(root.left), maxDepth(root.right)) + 1

19 求两棵树是否相同

def isSameTree(p, q):
 if p == None and q == None:
 return True
 elif p and q :
 return p.val == q.val and isSameTree(p.left,q.left) and isSameTree(p.right,q.right)
 else :
 return False

20 前序中序求后序

def rebuild(pre, center):
 if not pre:
 return
 cur = Node(pre[0])
 index = center.index(pre[0])
 cur.left = rebuild(pre[1:index + 1], center[:index])
 cur.right = rebuild(pre[index + 1:], center[index + 1:])
 return cur
def deep(root):
 if not root:
 return
 deep(root.left)
 deep(root.right)
 print root.data

21 单链表逆置

class Node(object):
 def __init__(self, data=None, next=None):
 self.data = data
 self.next = next
link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))
def rev(link):
 pre = link
 cur = link.next
 pre.next = None
 while cur:
 tmp = cur.next
 cur.next = pre
 pre = cur
 cur = tmp
 return pre
root = rev(link)
while root:
 print root.data
 root = root.next

22 两个字符串是否是变位词

class Anagram:
 """
 @:param s1: The first string
 @:param s2: The second string
 @:return true or false
 """
 def Solution1(s1,s2):
 alist = list(s2)
 pos1 = 0
 stillOK = True
 while pos1 < len(s1) and stillOK:
 pos2 = 0
 found = False
 while pos2 < len(alist) and not found:
 if s1[pos1] == alist[pos2]:
 found = True
 else:
 pos2 = pos2 + 1
 if found:
 alist[pos2] = None
 else:
 stillOK = False
 pos1 = pos1 + 1
 return stillOK
 print(Solution1('abcd','dcba'))
 def Solution2(s1,s2):
 alist1 = list(s1)
 alist2 = list(s2)
 alist1.sort()
 alist2.sort()
 pos = 0
 matches = True
 while pos < len(s1) and matches:
 if alist1[pos] == alist2[pos]:
 pos = pos + 1
 else:
 matches = False
 return matches
 print(Solution2('abcde','edcbg'))
 def Solution3(s1,s2):
 c1 = [0]*26
 c2 = [0]*26
 for i in range(len(s1)):
 pos = ord(s1[i])-ord('a')
 c1[pos] = c1[pos] + 1
 for i in range(len(s2)):
 pos = ord(s2[i])-ord('a')
 c2[pos] = c2[pos] + 1
 j = 0
 stillOK = True
 while j<26 and stillOK:
 if c1[j] == c2[j]:
 j = j + 1
 else:
 stillOK = False
 return stillOK
 print(Solution3('apple','pleap'))

23 动态规划问题

24 单例模式

class SingleTon(object):
 def __new__(cls,*args,**kwargs):
 if not hasattr(cls,'_instance'):
 cls._instance = object.__new__(cls,*args,**kwargs)
 return cls._instance
class TestClass(SingleTon):
 a = 1
test1 = TestClass()
test2 = TestClass()
print (test1.a,test2.a)
test1.a=2
print (test1.a,test2.a)
print (id(test1),id(test2))

def SingleTon(cls,*args,**kwargs):
 instances = {}
 print (instances)
 def _singleton():
 if cls not in instances:
 instances[cls] = cls(*args,**kwargs)
 print (instances)
 return instances[cls]
 return _singleton
@SingleTon
class LastClass(object):
 a = 1
test1 = LastClass()
print (test1.a)
test2 = LastClass()
print (test2.a)

class SignalTon(type):
 def __init__(cls,name,bases,dict):
 super(SignalTon, cls).__init__(name,bases,dict)
 cls._instance = None
 def __call__(cls, *args, **kwargs):
 if cls._instance is None:
 cls._instance = super(SignalTon,cls).__call__(*args,**kwargs)
 return cls._instance
class TestClass(object):
 __metaclass__ = SignalTon
test1 = TestClass()
test2 = TestClass()
test1.a = 2
print (test1.a,test2.a)
print (id(test1),id(test2))

class SingleTon(object):
 _state = {}
 def __new__(cls, *args, **kwargs):
 obj = object.__new__(cls,*args,**kwargs)
 obj.__dict__ = cls._state
 return obj
class TestClass(SingleTon):
 a = 1
test1 = TestClass()
test2 = TestClass()
print (test1.a,test2.a)
test1.a = 2
print (test1.a,test2.a)
print (id(test1),id(test2))

class My_Singleton(object):
 def foo(self):
 pass
my_singleton = My_Singleton()
#写在要使用这个实例的py文件里面,在不同的引用的地方都引用相同的实例,以此实现单例模式
from mysingleton import my_singleton
my_singleton.foo()

25 super函数的原理

#阅读下面的代码,它的输出结果是什么?
class A(object):
 def __init__(self):
 print ("enter A")
 super(A, self).__init__() # new
 print ("leave A")
class B(object):
 def __init__(self):
 print ("enter B")
 super(B, self).__init__() # new
 print ("leave B")
class C(A):
 def __init__(self):
 print ("enter C")
 super(C, self).__init__()
 print ("leave C")
class D(A):
 def __init__(self):
 print ("enter D")
 super(D, self).__init__()
 print ("leave D")
class E(B, C):
 def __init__(self):
 print ("enter E")
 super(E, self).__init__() # change
 print ("leave E")
class F(E, D):
 def __init__(self):
 print ("enter F")
 super(F, self).__init__() # change
 print ("leave F")
#输出
enter F
enter E
enter B
enter C
enter D
enter A
leave A
leave D
leave C
leave B
leave E
leave F