准备下次编程面试前你应该知道的数据结构
国外 IT 教育学院 Educative.io 创始人 Fahim ul Haq 写过一篇过万赞的文章《The top data structures you should know for your next coding interview》,总结了程序员面试中需要掌握的 8 种数据结构知识。
Fahim ul Haq 曾在 Facebook 和微软任职，面试过不少程序员，所以这篇文章还是值得参考的。以下内容编译自他的这篇《准备下次编程面试前你应该知道的数据结构》：
image
瑞典计算机科学家 Niklaus Wirth 在 1976 年写了一本书，叫作《Algorithms + Data Structures = Programs》（算法+数据结构=程序）。
即便在 40 年后的今天，这条等式仍然成立。这也是为何程序员求职者应该向面试官展示出已经透彻理解了数据结构知识。
几乎所有的面试问题都要求求职者表现出已经熟练掌握数据结构，不管你是刚毕业的应届生还是工作了多年的老手，都是这样。
有时，面试问题会明确提到数据结构，比如“给定一个二叉树”；有时则比较含蓄，比如“我们想追踪和每位作者相关的书籍数量。”
学习数据结构知识很有必要，哪怕你只是想找份比现在的工作更好的一份差事。我们首先了解数据结构的基本知识。
什么是数据结构？
简单说，数据结构就是一个容器，以某种特定的布局存储数据。这个“布局”使得数据结构在某些操作上非常高效，在另一些操作上则不那么高效。你的目标就是理解数据结构，这样就能为手头的问题选择最优的数据结构。
为什么我们需要数据结构？
由于数据结构用来以有组织的形式存储数据，而且数据是计算机科学中最重要的实体，因此数据结构的真正价值显而易见。
无论你解决什么问题，你都必须以这种或那种方式处理数据比如员工的工资，股票价格，购物清单，甚至简单的电话簿等等。
根据不同的场景，数据需要以特定格式存储。目前有一些数据结构可以满足我们以不同格式存储数据的需求。
常用的数据结构
我们首先列出最常用的数据结构，然后再挨个讲解：
- 数组
- 堆栈
- 队列
- 链表
- 树
- 图
- 字典树
- 哈希表
数组
数组是一种最简单和最广泛使用的数据结构，其它数据结构比如堆栈和队列都源自数组。
下图是一个大小为 4 的简单数组，包含几个元素（ 1 , 2 , 3，4）。
image
每个数据元素会被分配一个正的数值，叫作“索引”，它对应该元素在数组中的位置。大部分编程语言都将初始索引定义为 0.
以下是两种数组：
- 一维数组（如上所示）
- 多维数组（数组的数组）
数组的基本操作：
- Insert——在给定索引位置插入一个元素
- Get——返回给定索引位置的元素
- Delete——删除给定索引位置的元素
- Size——获取数组内所有元素的总数
常问的数组面试问题：
- 找到数组中第二小的元素
- 找到数组中第一个没有重复的整数
- 合并两个分类数组
- 重新排列数组中的正值和负值
堆栈
我们都熟悉很有名的撤销（Undo）选项，它几乎存在每个应用程序中。有没有想过它是如何工作的？其思路就是，按照最后的状态排列在先的顺序将工作的先前状态（限于特定数字）存储在内存中。这只用数组是无法实现的，因此堆栈就有了用武之地。
可以把堆栈看作一堆垂直排列的书籍。为了获得位于中间位置的书，你需要拿掉放在它上面的所有书籍。这就是 LIFO（后进先出）方法的工作原理。
这是一个包含三个数据元素（1,2 和 3）的堆栈图像，其中3位于顶部，首先把它删除：
image
堆栈的基本操作：
- Push——在顶部插入元素
- Pop—— 从堆栈中删除后返回顶部元素
- isEmpty——如果堆栈为空，则返回 true
- Top ——返回顶部元素，但不从堆栈中删除
常见的堆栈面试问题：
- 使用堆栈计算后缀表达式
- 对堆栈中的值进行排序
- 检查表达式中的括号是否平衡
队列
与堆栈类似，队列是另一种线性数据结构，以顺序方式存储元素。堆栈和队列之间唯一的显着区别是，队列不是使用 LIFO 方法，而是应用 FIFO 方法，这是 First in First Out（先入先出）的缩写。
队列的完美现实例子：一列人在售票亭等候。如果有新人来，他们是从末尾加入队列，而不是在开头——站在前面的人将先买到票然后离开队列。
下图是一个包含四个数据元素（1,2,3 和 4）的队列，其中 1 位于顶部，首先把它删除：
image
队列的基本操作：
- Enqueue() —— 向队列末尾插入元素
- Dequeue() —— 从队列头部移除元素
- isEmpty() —— 如果队列为空，则返回 true
- Top() —— 返回队列的第一个元素
常问的队列面试问题：
- 使用队列来实现堆栈
- 颠倒队列中前 k 个元素的顺序
- 使用队列生成从 1 到 n 的二进制数
链表
链表是另一个重要的线性数据结构，刚一看可能看起来像数组，但在内存分配，内部结构以及如何执行插入和删除的基本操作方面有所不同。
链表就像一个节点链，其中每个节点包含数据和指向链中后续节点的指针等信息。有一个头指针，指向链表的第一个元素，如果列表是空的，那么它只指向 null 或不指向任何内容。
链表用于实现文件系统，哈希表和邻接表。下图是链表内部结构的直观展示：
image
下面是几种类型的链表：
- 单链表（单向）
- 双链表（双向）
链表的基本操作：
- InsertAtEnd —— 在链表末尾插入指定元素
- InsertAtHead —— 在链表头部插入指定元素
- Delete —— 从链表中删除指定元素
- DeleteAtHead —— 删除链表的第一个元素
- Search —— 返回链表中的指定元素
- isEmpty —— 如果链表为空，返回 true
常问的链表面试问题：
- 翻转列表
- 检测链表中的循环
- 返回链表中倒数第 n 个节点
- 移除链表中的重复值
图
图就是一组节点，以网络的形式互相连接。节点也被称为顶点（vertices）。一对（x,y）就叫做一个边，表示顶点 x 和顶点 y 相连。一个边可能包含权重/成本，显示从顶点 x 到 y 所需的成本。
image
图的类型：
- 无向图
- 有向图
在编程语言中，图可以表示为两种形式：
- 邻接矩阵
- 邻接列表
常见的图遍历算法：
- 广度优先搜索
- 深度优先搜索
常问的图面试问题：
- 实现广度优先搜索和深度优先搜索
- 检查一个图是否为树
- 计算一张图中的边的数量
- 找到两个顶点之间的最短路径
树
树是一种层级数据结构，包含了连接它们的顶点（节点）和边。树和图很相似，但二者有个很大的不同点，即树中没有循环。
树广泛应用在人工智能和复杂的算法中，为解决各种问题提供高效的存储机制。
下图是一个简单的树，以及在树型数据结构中所用的基本术语：
image
下面是几种类型的树：
- N 叉树
- 平衡树
- 二叉树
- 二叉搜索树
- 平衡二叉树
- 红黑树
- 2-3 树
其中，二叉树和二叉搜索树是最常用的树。
常问的树面试问题：
- 找到一个二叉树的高度
- 找到一个二叉搜索树中第 k 个最大值
- 找到距离根部“k”个距离的节点
- 找到一个二叉树中给定节点的祖先（ancestors）
字典树
字典树，也叫“前缀树”，是一种树形结构，在解决字符串相关问题中非常高效。其提供非常快速的检索功能，常用于搜索字典中的单词，为搜索引擎提供自动搜索建议，甚至能用于IP路由选择。
下面展示了“top”“thus”和“their”这三个词是如何存储在字典树中的：
image
这些单词以从上到下的方式存储，其中绿色节点“p”，“s”和“r”分别表示“top”，“thus”和“their”的末尾。
常见的字典树面试问题：
- 计算字典树中的总字数
- 打印存储在字典树中的所有单词
- 使用字典树对数组的元素进行排序
- 使用字典树从字典中形成单词
- 构建一个T9字典
哈希表
散列是一个用于唯一标识对象并在一些预先计算的唯一索引（称为“密钥”）存储每个对象的过程。因此，对象以“键值”对的形式存储，这些项的集合被称为“字典”。可以使用该键值搜索每个对象。有多种不同的基于哈希的数据结构，但最常用的数据结构是哈希表。
哈希表通常使用数组实现。
哈希数据结构的性能取决于以下三个因素：
- 哈希函数
- 哈希表的大小
- 碰撞处理方法
下图展示了如何在数组中映射哈希。该数组的索引是通过哈希函数计算的。
image
常问的哈希面试问题：
- 找到数组中的对称对
- 追踪遍历的完整路径
- 查看一个数组是否为另一个数组的子集
- 检查给定数组是否不相交
以上就是你在准备编程面试前需要掌握的8种数据结构。
在上面的 8 种数据结构中，每种结构都有对应的面试问题，接下来的一段时间我会将这三十一道问题依旧使用动画的形式解析清楚。
