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

笔者曾多年负责 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)\)。 如果候选人能够一路打怪升级走到这里,基本上就可以拿到通过面试的门票了。

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

../../_images/a0eafd3108e87cd03e301811b9619e5b.svg

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

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 开发水平,向更高一级的岗位迈进? 如果你有这些问题或者疑惑,请订阅我们的专栏,阅读更多章节:

https://cdn.fasionchan.com/python-source-course-qrcode.png

附录

订阅更新,获取更多学习资料,请关注我们的 微信公众号

微信搜索:小菜学编程

创作不易,如果觉得我们写得还行,就请我们喝杯咖啡吧😋

微信搜索:小菜学编程