准备下次编程面试前你应该知道的数据结构
国外 IT 教育学院 Educative.io 创始人 Fahim ul Haq 写过一篇过万赞的文章《The top data structures you should know for your next coding interview》,总结了程序员面试中需要掌握的 8 种数据结构知识。
Fahim ul Haq 曾在 Facebook 和微软任职,面试过不少程序员,所以这篇文章还是值得参考的。以下内容编译自他的这篇《准备下次编程面试前你应该知道的数据结构》:
瑞典计算机科学家 Niklaus Wirth 在 1976 年写了一本书,叫作《Algorithms + Data Structures = Programs》(算法+数据结构=程序)。
即便在 40 年后的今天,这条等式仍然成立。这也是为何程序员求职者应该向面试官展示出已经透彻理解了数据结构知识。
几乎所有的面试问题都要求求职者表现出已经熟练掌握数据结构,不管你是刚毕业的应届生还是工作了多年的老手,都是这样。
有时,面试问题会明确提到数据结构,比如“给定一个二叉树”;有时则比较含蓄,比如“我们想追踪和每位作者相关的书籍数量。”
学习数据结构知识很有必要,哪怕你只是想找份比现在的工作更好的一份差事。我们首先了解数据结构的基本知识。
什么是数据结构?
简单说,数据结构就是一个容器,以某种特定的布局存储数据。这个“布局”使得数据结构在某些操作上非常高效,在另一些操作上则不那么高效。你的目标就是理解数据结构,这样就能为手头的问题选择最优的数据结构。
为什么我们需要数据结构?
由于数据结构用来以有组织的形式存储数据,而且数据是计算机科学中最重要的实体,因此数据结构的真正价值显而易见。
无论你解决什么问题,你都必须以这种或那种方式处理数据比如员工的工资,股票价格,购物清单,甚至简单的电话簿等等。
根据不同的场景,数据需要以特定格式存储。目前有一些数据结构可以满足我们以不同格式存储数据的需求。
常用的数据结构
我们首先列出最常用的数据结构,然后再挨个讲解:
- 数组
- 堆栈
- 队列
- 链表
- 树
- 图
- 字典树
- 哈希表
数组
数组是一种最简单和最广泛使用的数据结构,其它数据结构比如堆栈和队列都源自数组。
下图是一个大小为 4 的简单数组,包含几个元素( 1 , 2 , 3,4)。
每个数据元素会被分配一个正的数值,叫作“索引”,它对应该元素在数组中的位置。大部分编程语言都将初始索引定义为 0.
以下是两种数组:
- 一维数组(如上所示)
- 多维数组(数组的数组)
数组的基本操作:
- Insert——在给定索引位置插入一个元素
- Get——返回给定索引位置的元素
- Delete——删除给定索引位置的元素
- Size——获取数组内所有元素的总数
常问的数组面试问题:
- 找到数组中第二小的元素
- 找到数组中第一个没有重复的整数
- 合并两个分类数组
- 重新排列数组中的正值和负值
堆栈
我们都熟悉很有名的撤销(Undo)选项,它几乎存在每个应用程序中。有没有想过它是如何工作的?其思路就是,按照最后的状态排列在先的顺序将工作的先前状态(限于特定数字)存储在内存中。这只用数组是无法实现的,因此堆栈就有了用武之地。
可以把堆栈看作一堆垂直排列的书籍。为了获得位于中间位置的书,你需要拿掉放在它上面的所有书籍。这就是 LIFO(后进先出)方法的工作原理。
这是一个包含三个数据元素(1,2 和 3)的堆栈图像,其中3位于顶部,首先把它删除:
堆栈的基本操作:
- Push——在顶部插入元素
- Pop—— 从堆栈中删除后返回顶部元素
- isEmpty——如果堆栈为空,则返回 true
- Top ——返回顶部元素,但不从堆栈中删除
常见的堆栈面试问题:
- 使用堆栈计算后缀表达式
- 对堆栈中的值进行排序
- 检查表达式中的括号是否平衡
队列
与堆栈类似,队列是另一种线性数据结构,以顺序方式存储元素。堆栈和队列之间唯一的显着区别是,队列不是使用 LIFO 方法,而是应用 FIFO 方法,这是 First in First Out(先入先出)的缩写。
队列的完美现实例子:一列人在售票亭等候。如果有新人来,他们是从末尾加入队列,而不是在开头——站在前面的人将先买到票然后离开队列。
下图是一个包含四个数据元素(1,2,3 和 4)的队列,其中 1 位于顶部,首先把它删除:
队列的基本操作:
- Enqueue() —— 向队列末尾插入元素
- Dequeue() —— 从队列头部移除元素
- isEmpty() —— 如果队列为空,则返回 true
- Top() —— 返回队列的第一个元素
常问的队列面试问题:
- 使用队列来实现堆栈
- 颠倒队列中前 k 个元素的顺序
- 使用队列生成从 1 到 n 的二进制数
链表
链表是另一个重要的线性数据结构,刚一看可能看起来像数组,但在内存分配,内部结构以及如何执行插入和删除的基本操作方面有所不同。
链表就像一个