小菜学编程
笔者曾多年负责 Python 开发工程师的面试工作，与 Python 相关的面试内容一般这样开始：
日常开发中用过 Python 内置容器对象吗？都在哪些场景，用过哪些容器，解决什么问题？
这几个问题先从 Python 内建对象基本用法入手，考察候选人对 Python 基础知识的熟悉程度。如果一个以 Python 为主要工具的候选人，经过引导后仍然无法准确描述 list 、 dict 等对象的用法，基本就可以放弃了。
如果候选人表示对 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源码剖析】系列文章首发于公众号【小菜学编程】，敬请关注：
