Python面试题2

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

行列转换


已知有一个二维列表(每一行的元素个数相同)写出函数对其行列转换并输出比如
a = [[1,1,1,1],
     [2,2,2,2]]
输出
[
[1,2],
[1,2],
[1,2],
[1,2]
]

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

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

写一个支持参数的装饰器

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

# 下面这个是不带参数的
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()函数是怎么处理的:

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.

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

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

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.

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中并没有提供这个数据结构,当然可以使用类自己构造循环链表,但使用列表也可以实现循环队列功能。这里不考虑时空复杂度的问题

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错误。

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

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时候都把当前元素弹出并放到队列尾部,从而模拟循环链表结构。进一步优化,由于列表弹出第一个元素的复杂度较高,可以使用双端队列来进行优化:

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__方法时候一定要小心,否则可能造成内存泄露!

类方法和静态方法的区别

以下面代码为例:

# 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__重载来实现:

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    

其次还可以使用装饰器:

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也有热加载功能啊!代码文件在这里,判断核心和我猜的差不多:

……
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中的有序字典