【python面试指北】2.数据结构和算法

1. collections模块

collections模块提供了一些内置数据结构的扩展

namedtuple：让tuple属性可读
deque：可以方便实现deque/stack
counter：需要计数器的地方使用
orderedDict：key的顺序是第一次插入的顺序
defaultDict：带有默认值的字典

2. dict底层结构

dict底层使用的哈希表

• 为了支持快速查找使用了哈希表作为底层结构
• 哈希表平均查找时间复杂度O(1)
• cpython解释器使用二次探查解决哈希冲突问题

3. list/tuple区别

• 都是线性结构，支持下标访问
• list是可变对象，tuple保存的引用不可变
• list没法作为字典的key，tuple可以（可变对象不可hash）

4. 什么是LRUCache？

least-recently-used替换掉最近最少的对象

字典用来缓存，循环双端列表用来记录访问顺序

5. 排序+查找，重中之重

• 常考排序算法：冒泡排序、快速排序、归并排序、堆排序
• 线性查找、二分查找等
• 能独立实现代码（手写），能够分析时间空间复杂度

常用排序算法的时空复杂度

6. python数据结构常考题

• 常见的数据结构，链表、队列、栈、二叉树、堆
• 使用内置结构实现高级数据结构，比如内置的list/deque实现栈
• leetcode或者剑指offer上的常见题

链表

• 如何使用python来表示链表结构
• 实现链表常见的操作，比如插入节点，反转链表，合并多个链表等

206 leetcode，反转链表

队列

队列是先进先出结构

• 使用python的list或者collections.deque实现队列

栈

• 使用python的list或者collections.deque实现队列

如何用两个栈实现队列
实现获取最小值的栈

字典与集合

• 哈希表的实现原理，底层其实就是一个数组
• 根据哈希函数快速定位一个元素，平均查找O(1)，非常快
• 不断加入元素会引起哈希表重新开辟空间，拷贝之前元素到新数组

二叉树

前序：根左右
中序：左根右
后序：左右根

递归处理三种遍历

二叉树的镜像
层序遍历二叉树

堆

堆：可以看做是完全二叉树的数组对象

heapq标准库，堆排序

topK问题

链表

• 熟悉链表的定义和常见操作
• 237 删除一个链表节点
• 21 合并两个有序的链表

7. 白板编程

• 刷题
• 真正理解掌握
• 打好基础
• 常见排序算法和数据结构能手写
• 多写多练
• 一般可能一次很难写对
• 尝试自己先思考，先按照自己的方式编写代码，提交后发现问题
• 如果实在没有思路可以搜题解