和面试官畅谈内建对象背后的算法思想

书山有路勤为径,学海无涯苦作舟。

—— 唐·韩愈

笔者曾多年负责 Python 开发工程师的面试工作,与 Python 相关的面试内容一般这样开始:

日常开发中用过 Python 内置容器对象吗?都在哪些场景,用过哪些容器,解决什么问题?

这几个问题先从 Python 内建对象基本用法入手,考察候选人对 Python 基础知识的熟悉程度。如果一个以 Python 为主要工具的候选人,经过引导后仍然无法准确描述 listdict 等对象的用法,基本就可以放弃了。

如果候选人表示对 list 对象比较了解,则会进一步讨论 list 的关键操作以及时间复杂度:

list 对象都支持哪些操作?时间复杂度分别是多少?可以在头部插入吗?头部插入有什么需要注意的地方?

这时候选人需要准确回答 list 对象,相应的 时间复杂度 以及其中缘由:

  • append,从尾部追加,直接将元素添加到动态数组尾部,时间复杂度为 $O(1)$ ,必要时 Python 负责扩容;
  • insert ,在指定位置插入,由于需要挪动插入位置以后的所有元素,时间复杂度为 $O(N)$ ;
  • etc

如果候选人无法准确回答 append 等关键操作的 时间复杂度 ,面试官心里可能就会犯嘀咕:对方多半是一位 API 调用侠吧?还没搞清楚一个操作的前因后果就写代码,无异于瞎写!指不定这样的代码里藏有多少不知名炸弹!

不少 初级工程师 觉得开发中很少用到数据结构和算法,因此没有学习动力。这种想法是非常不可取的。在实际工程中我们完全可以站在别人的肩膀上,但原理掌握与否决定了我们到底能不能站稳,能不能用好。

与资深工程师相比,初级工程师更像是将需求 翻译 成代码,而且是直译,这种代码质量可想而知。因此,作为通往高级工程师进阶之路上必不可少的台阶,数据结构和算法等基础知识不应该被忽视。

如果候选人回答还算顺利,接着将讨论 list 如何进行容量管理以及扩缩容策略等高级知识点:

list 如何做到容量自适应?Python 在什么情况下会对底层数组进行扩缩容?

如果候选人能够准确回答《 list 源码解析:动态数组精讲》中介绍的内容,面试官应该就很满意了。再接着,面试官可能会尝试将问题发散,考察候选人的知识面以及对知识点触类旁通的能力:

有个场景需要在尾部追加,在头部删除,用 list 对象合适吗?不合适的话有什么替代品?

这个场景需要特别注意 list 对象头部操作,不管插入还是删除,时间复杂度都是 $O(N)$ ,非常不理想。这时,标准库 collections 模块中的双端队列 deque 更好,头部操作时间复杂度跟尾部操作一样,都是 $O(1)$。如果候选人能够一路打怪升级走到这里,基本上就可以拿到通过面试的门票了。

一般面试过程都是这样,从基础的使用方法开始,逐步深入底层原理,再进一步发散、触类旁通。通过阶梯式面试过程,面试官可以快速评估候选人的能力水平,并据此决定取舍。

退一步讲,就算为了在面试中走得更远,候选人也必须有深入底层的意识,而源码学习是夯实基础的最好途径之一。

list

❓list 对象常用操作有哪些?时间复杂度分别是多少?

操作 示例 时间复杂度
尾部追加 l.append(x) O(1)
尾部删除 x = l.pop() O(1)
头部插入 l.insert(0, x) O(N)
头部删除 x = l.pop(0) O(N)
指定位置插入 l.insert(i, x) O(N)
指定位置删除 x = l.pop(i) O(N)
清空列表 l.clear() O(N)
浅拷贝 l.copy() O(N)
元素计数 l.count(x) O(N)
列表扩展 l.extend(l2) O(N)
元素查找 l.index(x) O(N)
元素删除 l.remove(x) O(N)
列表反转 l.reverse() O(N)
列表排序 l.sort() O(logN)

常用操作以及对应的时间复杂度是最低门槛,描述必须做到准确无误。如被问及诸如为什么 尾部插入效率比头部高 之类的原理性问题,则需要结合列表对象内部 动态数组 结构进行回答。

❓list 为什么可以做到容量自适应?什么时机需要扩容、缩容?

list 对象底层由动态数组实现,对象头部保存数组 容量 以及当前已用 长度

当我们往列表添加新数据时,长度会不断增长。当长度达到容量后, Python 会对底层数组进行扩容,分配一个更大的数组,并将元素从旧数组中拷贝过去。为避免频繁扩容,Python 每次扩容时都额外分配至少 $\frac{1}{8}$ 的空闲空间。

当我们从列表中删除元素时,动态数组慢慢出现很多空闲空间。这时 Python 对底层数组进行缩容,以降低内存开销。缩容操作与扩容类似,需要重新分配底层数组,更多细节请复习《 list 源码解析:动态数组精讲》一节。

更多面试真题

❓通过 copy 方法复制 list ,修改新列表会影响旧列表吗?

❓Python 中有“栈”容器吗?如何快速得到一个栈?

❓频繁从 list 头部删除元素会导致什么问题?如何解决?

❓dict 对象常用操作有哪些?时间复杂度分别是多少?

❓空 dict 对象是否占用内存?占用多少内存?为什么?

❓dict 内部的哈希表为何分为两个数组来实现?

上述的问题,你是否都能对答如流呢?点击 阅读原文,获取详细题解!

【Python源码剖析】系列文章首发于公众号【小菜学编程】,敬请关注:

【Python源码剖析】系列文章首发于公众号【小菜学编程】,敬请关注: