最近面试了几家公司,各行各业的都有,涨了很多见识也发现了自己的技术盲点。这里来一个汇总简单纪录。

行列转换

1
2
3
4
5
6
7
8
9
10
11
已知有一个二维列表(每一行的元素个数相同),写出函数对其行列转换并输出,比如:
a = [[1,1,1,1],
[2,2,2,2]]
输出:
[
[1,2],
[1,2],
[1,2],
[1,2]
]

这里建议笔试时候尽量使用简单清晰的写法,让面试官一眼就能看出答案对错:

1
2
3
4
5
6
7
8
def convert(alist):
result = []
for x in range(len(alist[0])):
tmp = []
for y in range(len(alist)):
tmp.append(alist[y][x])
result.append(tmp)
print result

写一个支持参数的装饰器

这个比较基础了,带参数的就是在不带参数的基础上多写一层函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 下面这个是不带参数的
def mywrapper(func):
def tmp(*args,**kwargs):
print "in wrapper"
return func(*args,**kwargs)
return tmp
# 下面这个带参数
def mywrapper2(wrapper_arg):
def mywrapper(func):
def tmp(*args,**kwargs):
print "in wrapper"
return func(*args,**kwargs)
return tmp
return mywrapper

编码实现range函数

这个问题第一眼看起来不难,但有几个细节:比如range()函数有1个必填参数以及2个默认参数,当只传入一个参数时,这个值为结束值;传入2个参数时候,第一个为起始值而第二个为结束值。再比如,如果传递的不是数值类型如何处理(包括字符串或者浮点型)?再比如当起始值大于结束值时怎么处理?这种情况下如果步长为负数时又如何等等……

很惭愧,之前有用过这个函数时候从来没这么深入思考这些细节问题,这也是自己技术遇到瓶颈的一个重要因素吧!以下都是python2代码。

先看看关于参数类型原range()函数是怎么处理的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
In [2]: range('5')
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-2-b471aa280369> in <module>()
----> 1 range('5')
TypeError: range() integer end argument expected, got str.
In [3]: range(9.4)
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-3-693e2fab7965> in <module>()
----> 1 range(9.4)
TypeError: range() integer end argument expected, got float.
In [4]: range(3,9,-0.1)
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-5-9022f4774d41> in <module>()
----> 1 range(3,9,-0.1)
TypeError: range() integer step argument expected, got float.

可以看出原生函数仅仅支持整数。

再看看关于参数为整数时候边界问题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
In [7]: range(0)
Out[7]: []
In [8]: range(-1)
Out[8]: []
In [9]: range(5,1)
Out[9]: []
In [10]: range(5,1,-1)
Out[10]: [5, 4, 3, 2]
In [11]: range(-3,-1,-1)
Out[11]: []
In [12]: range(5,1,0)
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-11-5aa6e25c62fc> in <module>()
----> 1 range(5,1,0)
ValueError: range() step argument must not be zero

当只传递一个参数时候,这个参数必须大于0,否则返回空;当起始值大于结束值时,如果步长大于0则返回空;步长不能为0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def myrange(s, e=None, l=1):
if not isinstance(s, int):
raise TypeError("integer end argument expected, got %s" % type(s))
if e is not None and not isinstance(e, int):
raise TypeError("integer end argument expected, got %s" % type(e))
if not isinstance(l, int):
raise TypeError("integer step argument expected, got %s" % type(l))
if l == 0:
raise ValueError("step argument must not be zero")
result = []
if e is None:
flag = 0
while flag < s:
result.append(flag)
flag += l
return result
else:
flag = s
if (s > e and l > 0) or (s < e and l < 0):
return result
elif s > e and l < 0:
while flag > e:
result.append(flag)
flag += l
elif s < e and l > 0:
while flag < e:
result.append(flag)
flag += l
return result
if __name__ == "__main__":
print myrange(5)
print myrange(0)
print myrange(-1)
print myrange(1, 9)
print myrange(-9, 4)
print myrange(-9, -1, 1)
print myrange(-9, -1, -1)
print myrange(9, 1, -1)
print myrange(9, 1, 1)

如果想更进一步,可以实现参数为浮点型甚至字符串(我的思路是把字符转换为ascii码),有兴趣的可以试试。

约瑟夫圆环

现在有13个人围成一个环,从1开始报数,数到3的人离开,写出程序计算最后剩下的是谁。

看到这个题的时候依稀记得应该有一个名词对应这种情况的,后来回家后才想起来是约瑟夫环问题,真是对不起大学老师啊!第一反应就是使用循环链表这个数据结构,但Python中并没有提供这个数据结构,当然可以使用类自己构造循环链表,但使用列表也可以实现循环队列功能。这里不考虑时空复杂度的问题

1
2
3
4
5
6
7
8
9
10
11
def func(alist, k):
if len(alist) == 2:
return alist[-1]
else:
temp = alist[k:] + alist[:k - 1]
return func3(temp, k)
t = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
print func(t, 3)
x = [x for x in range(5)]
print func3(t, 3)

这个函数由于使用了递归,有一个隐患就是当传入的列表过大时,会造成RuntimeError: maximum recursion depth exceeded错误。

为了解决上面的隐患,我们不使用递归:

1
2
3
4
5
6
7
8
9
10
11
12
def func2(alist,k):
i = 1
while 1:
if i != k:
alist.append(alist.pop(0))
i += 1
else:
alist.pop(0)
i = 1
if len(alist) == 1:
break
return alist[0]

这里摒弃了递归,每次步长不为k时候都把当前元素弹出并放到队列尾部,从而模拟循环链表结构。进一步优化,由于列表弹出第一个元素的复杂度较高,可以使用双端队列来进行优化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from collections import deque
def func3(adq,k):
i = 1
while 1:
if i != k:
adq.append(adq.popleft())
i += 1
else:
adq.popleft()
i = 1
if len(adq) == 1:
break
return adq[0]
t = ['a', 'b', 'c', 'd', 'e','f','g','h']
x =
adq = deque(t)
print func3(adq,3)
adq = deque([x for x in range(50000)])
print func3(adq,3)

python中的垃圾回收机制

这个问题是在面试中经常被问到的,在之前的文章中提了这么一句,大多数公司回答上“引用计数、标记-清除、分代-收集”并说出引用计数这种方式的优缺点(简单,但无法解决循环引用问题)就可以了,但有一家继续深入问了“标记-清除”的原理,当时我回答的并不好。

有一个文章整理的很好,简而言之“标记-清除”的原理就是python维护了一个叫做Root Object根对象的数据结构,上面存储了全局变量或者栈、寄存器上的变量,对象之间通过引用(指针)链接,从根对象出发,如果沿着引用能到达某个对象,则把它标记为可到达(reachable)的,否则则是不可达(unreachable)。以上过程就是“标记”,而清除则是根据算法把所有不可达的对象内存释放。

这种方法作为辅助手段来解决循环引用问题,缺点是:清除不可达的对象前它必须顺序扫描整个堆内存,哪怕只剩下小部分活动对象也要扫描所有对象。

另外多说一句,导致引用计数+1的情况:

  1. 对象被创建,例如a=23
  2. 对象被引用,例如b=a
  3. 对象被作为参数,传入到一个函数中,例如func(a)
  4. 对象作为一个元素,存储在容器中,例如list1=[a,a]

导致引用计数-1的情况:

  1. 对象的别名被显式销毁,例如del a
  2. 对象的别名被赋予新的对象,例如a=24
  3. 一个对象离开它的作用域,例如f函数执行完毕时,func函数中的局部变量(全局变量不会)
  4. 对象所在的容器被销毁,或从容器中删除对象

最后注意一点,代码中尽量别使用循环引用,而且定义类的时候如果要重写__del__方法时候一定要小心,否则可能造成内存泄露!

类方法和静态方法的区别

以下面代码为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# coding=utf-8
class MyClass(object):
data = "This is class data"
def instance_method(self):
print("实例方法,只能被实例对象调用,可以访问实例属性%s" % self.data)
@staticmethod
def static_method():
print("是静态方法,不能访问类属性或者实例属性")
@classmethod
def class_method(cls):
print("是类方法,可以访问类属性%s" % cls.data)
m = MyClass()
m.data = "this is m"
m.instance_method()
m.static_method()
m.class_method()
print "------"
MyClass.static_method()
print "------"
MyClass.class_method()
print "------"
MyClass.instance_method()

最明显的,类方法需要一个cls参数,并且可以访问类属性,但静态方法不可以。换言之,静态方法用于那些和类有关但又不使用类或实例相关属性的情况,所以置于类的外面不写成静态方法也是可以的。

写出实现单例模式的2种方法

最简单的,python中的模块是天然的单例模式。

然后可以使用__new__重载来实现:

1
2
3
4
5
6
7
class MyClass(object):
"""重载__new__方法实现单例"""
_ins = None
def __new__(cls,*args,**kwargs):
if not cls._ins:
cls._ins = super(MyClass,cls).__new__(cls,*args,**kwargs)
return cls._ins

其次还可以使用装饰器:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from functools import wraps
def singleton(cls):
instances = {}
@wraps(cls)
def getinstance(*args, **kwargs):
if cls not in instances:
instances[cls] = cls(*args, **kwargs)
return instances[cls]
return getinstance
@singleton
class MyClass(object):
a = 1

Flask框架中的热加载是如何实现的?

面试时没回答上这个问题,但后来猜测这一类问题核心应该都是有个守护进程/线程在不停的遍历文件,判断最后修改时间。如果修改时间和上次记录的不同则重启程序。

后来看Flask代码,追踪到werkzeug代码,又追踪到watchdog代码,结果还是愚钝的没理解最后到底怎么实现的。

但是,Django也有热加载功能啊!代码文件在这里,判断核心和我猜的差不多:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
……
FILE_MODIFIED = 1
I18N_MODIFIED = 2
……
def code_changed():
global _mtimes, _win
for filename in gen_filenames():
stat = os.stat(filename)
mtime = stat.st_mtime
if _win:
mtime -= stat.st_ctime
if filename not in _mtimes:
_mtimes[filename] = mtime
continue
if mtime != _mtimes[filename]:
_mtimes = {}
try:
del _error_files[_error_files.index(filename)]
except ValueError:
pass
return I18N_MODIFIED if filename.endswith('.mo') else FILE_MODIFIED
return False

程序将每个文件修改时间以文件名作为key,修改时间为value存储在了一个全局字典中,判读最后修改时间不同则返回True。虽然不是watchdog的代码,但估计原理都是一样的。

另外关于热加载这篇文章说的不错。

Flask框架中request是如何保证线程隔离的?

这篇文章解释的很好。

简单来说,通过代理模式将每一个线程/协程的ID存储在werkzeug框架中的Local()对象中,每一个线程/协程都有自己的栈空间保证了隔离性。

如何禁止JS读取Cookie

设置httponly=true

其他

以下几个问题被问到时候我就一脸懵B了,之后觉得每一个问题都可以单独写一篇,这篇文章就不进行扩展了,各位小伙伴可以试试:

  1. Innodb中的行级锁机制(如何实现的)
  2. 简述什么是悲观锁和乐观锁,以及实现方式
  3. Nginx服务器实现多个域名绑定同一ip情况下的转发机制
  4. 如何在Docker实例中启动别的Docker实例
  5. HTTP协议中关于缓存部分的处理
  6. 编码实现Python中的有序字典