國外 IT 教育學(xué)院 Educative.io 創(chuàng)始人 Fahim ul Haq 寫過一篇過萬贊的文章《The top data structures you should know for your next coding interview》,總結(jié)了程序員面試中需要掌握的 8 種數(shù)據(jù)結(jié)構(gòu)知識。
Fahim ul Haq 曾在 Facebook 和微軟任職，面試過不少程序員蛔糯，所以這篇文章還是值得參考的。以下內(nèi)容編譯自他的這篇《準備下次編程面試前你應(yīng)該知道的數(shù)據(jù)結(jié)構(gòu)》：
瑞典計算機科學(xué)家 Niklaus Wirth 在 1976 年寫了一本書墓拜，叫作《Algorithms + Data Structures = Programs》（算法+數(shù)據(jù)結(jié)構(gòu)=程序）。
即便在 40 年后的今天请契，這條等式仍然成立咳榜。這也是為何程序員求職者應(yīng)該向面試官展示出已經(jīng)透徹理解了數(shù)據(jù)結(jié)構(gòu)知識。
幾乎所有的面試問題都要求求職者表現(xiàn)出已經(jīng)熟練掌握數(shù)據(jù)結(jié)構(gòu)爽锥，不管你是剛畢業(yè)的應(yīng)屆生還是工作了多年的老手涌韩，都是這樣。
有時氯夷，面試問題會明確提到數(shù)據(jù)結(jié)構(gòu)臣樱，比如“給定一個二叉樹”；有時則比較含蓄腮考，比如“我們想追蹤和每位作者相關(guān)的書籍數(shù)量雇毫。”
學(xué)習數(shù)據(jù)結(jié)構(gòu)知識很有必要踩蔚，哪怕你只是想找份比現(xiàn)在的工作更好的一份差事棚放。我們首先了解數(shù)據(jù)結(jié)構(gòu)的基本知識。
什么是數(shù)據(jù)結(jié)構(gòu)馅闽？
簡單說飘蚯，數(shù)據(jù)結(jié)構(gòu)就是一個容器，以某種特定的布局存儲數(shù)據(jù)捞蛋。這個“布局”使得數(shù)據(jù)結(jié)構(gòu)在某些操作上非常高效，在另一些操作上則不那么高效柬姚。你的目標就是理解數(shù)據(jù)結(jié)構(gòu)拟杉，這樣就能為手頭的問題選擇最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。
為什么我們需要數(shù)據(jù)結(jié)構(gòu)量承？
由于數(shù)據(jù)結(jié)構(gòu)用來以有組織的形式存儲數(shù)據(jù)搬设，而且數(shù)據(jù)是計算機科學(xué)中最重要的實體，因此數(shù)據(jù)結(jié)構(gòu)的真正價值顯而易見撕捍。
無論你解決什么問題拿穴，你都必須以這種或那種方式處理數(shù)據(jù)比如員工的工資，股票價格忧风，購物清單默色，甚至簡單的電話簿等等。
根據(jù)不同的場景狮腿，數(shù)據(jù)需要以特定格式存儲腿宰。目前有一些數(shù)據(jù)結(jié)構(gòu)可以滿足我們以不同格式存儲數(shù)據(jù)的需求呕诉。
常用的數(shù)據(jù)結(jié)構(gòu)
我們首先列出最常用的數(shù)據(jù)結(jié)構(gòu)，然后再挨個講解：
- 數(shù)組
- 堆棧
- 隊列
- 鏈表
- 樹
- 圖
- 字典樹
- 哈希表
數(shù)組
數(shù)組是一種最簡單和最廣泛使用的數(shù)據(jù)結(jié)構(gòu)吃度，其它數(shù)據(jù)結(jié)構(gòu)比如堆棧和隊列都源自數(shù)組甩挫。
下圖是一個大小為 4 的簡單數(shù)組，包含幾個元素（ 1 , 2 , 3椿每，4）伊者。
每個數(shù)據(jù)元素會被分配一個正的數(shù)值，叫作“索引”间护，它對應(yīng)該元素在數(shù)組中的位置亦渗。大部分編程語言都將初始索引定義為 0.
以下是兩種數(shù)組：
- 一維數(shù)組（如上所示）
- 多維數(shù)組（數(shù)組的數(shù)組）
數(shù)組的基本操作：
- Insert——在給定索引位置插入一個元素
- Get——返回給定索引位置的元素
- Delete——刪除給定索引位置的元素
- Size——獲取數(shù)組內(nèi)所有元素的總數(shù)
常問的數(shù)組面試問題：
- 找到數(shù)組中第二小的元素
- 找到數(shù)組中第一個沒有重復(fù)的整數(shù)
- 合并兩個分類數(shù)組
- 重新排列數(shù)組中的正值和負值
堆棧
我們都熟悉很有名的撤銷（Undo）選項，它幾乎存在每個應(yīng)用程序中兑牡。有沒有想過它是如何工作的央碟？其思路就是，按照最后的狀態(tài)排列在先的順序?qū)⒐ぷ鞯南惹盃顟B(tài)（限于特定數(shù)字）存儲在內(nèi)存中均函。這只用數(shù)組是無法實現(xiàn)的亿虽，因此堆棧就有了用武之地。
可以把堆棸玻看作一堆垂直排列的書籍洛勉。為了獲得位于中間位置的書，你需要拿掉放在它上面的所有書籍如迟。這就是 LIFO（后進先出）方法的工作原理收毫。
這是一個包含三個數(shù)據(jù)元素（1,2 和 3）的堆棧圖像，其中3位于頂部殷勘，首先把它刪除：
堆棧的基本操作：
- Push——在頂部插入元素
- Pop—— 從堆棧中刪除后返回頂部元素
- isEmpty——如果堆棧為空此再，則返回 true
- Top ——返回頂部元素，但不從堆棧中刪除
常見的堆棧面試問題：
- 使用堆棧計算后綴表達式
- 對堆棧中的值進行排序
- 檢查表達式中的括號是否平衡
隊列
與堆棧類似玲销，隊列是另一種線性數(shù)據(jù)結(jié)構(gòu)输拇，以順序方式存儲元素。堆棧和隊列之間唯一的顯著區(qū)別是贤斜，隊列不是使用 LIFO 方法策吠，而是應(yīng)用 FIFO 方法，這是 First in First Out（先入先出）的縮寫瘩绒。
隊列的完美現(xiàn)實例子：一列人在售票亭等候猴抹。如果有新人來，他們是從末尾加入隊列锁荔，而不是在開頭——站在前面的人將先買到票然后離開隊列蟀给。
下圖是一個包含四個數(shù)據(jù)元素（1,2,3 和 4）的隊列，其中 1 位于頂部，首先把它刪除：
隊列的基本操作：
- Enqueue() —— 向隊列末尾插入元素
- Dequeue() —— 從隊列頭部移除元素
- isEmpty() —— 如果隊列為空坤溃，則返回 true
- Top() —— 返回隊列的第一個元素
常問的隊列面試問題：
- 使用隊列來實現(xiàn)堆棧
- 顛倒隊列中前 k 個元素的順序
- 使用隊列生成從 1 到 n 的二進制數(shù)
鏈表
鏈表是另一個重要的線性數(shù)據(jù)結(jié)構(gòu)拍霜，剛一看可能看起來像數(shù)組，但在內(nèi)存分配薪介，內(nèi)部結(jié)構(gòu)以及如何執(zhí)行插入和刪除的基本操作方面有所不同祠饺。
鏈表就像一個節(jié)點鏈，其中每個節(jié)點包含數(shù)據(jù)和指向鏈中后續(xù)節(jié)點的指針等信息汁政。有一個頭指針道偷，指向鏈表的第一個元素，如果列表是空的记劈，那么它只指向 null 或不指向任何內(nèi)容勺鸦。
鏈表用于實現(xiàn)文件系統(tǒng)，哈希表和鄰接表目木。下圖是鏈表內(nèi)部結(jié)構(gòu)的直觀展示：
下面是幾種類型的鏈表：
- 單鏈表（單向）
- 雙鏈表（雙向）
鏈表的基本操作：
- InsertAtEnd —— 在鏈表末尾插入指定元素
- InsertAtHead —— 在鏈表頭部插入指定元素
- Delete —— 從鏈表中刪除指定元素
- DeleteAtHead —— 刪除鏈表的第一個元素
- Search —— 返回鏈表中的指定元素
- isEmpty —— 如果鏈表為空换途，返回 true
常問的鏈表面試問題：
- 翻轉(zhuǎn)列表
- 檢測鏈表中的循環(huán)
- 返回鏈表中倒數(shù)第 n 個節(jié)點
- 移除鏈表中的重復(fù)值
圖
圖就是一組節(jié)點，以網(wǎng)絡(luò)的形式互相連接刽射。節(jié)點也被稱為頂點（vertices）军拟。一對（x,y）就叫做一個邊，表示頂點 x 和頂點 y 相連誓禁。一個邊可能包含權(quán)重/成本懈息，顯示從頂點 x 到 y 所需的成本。
圖的類型：
- 無向圖
- 有向圖
在編程語言中摹恰，圖可以表示為兩種形式：
- 鄰接矩陣
- 鄰接列表
常見的圖遍歷算法：
- 廣度優(yōu)先搜索
- 深度優(yōu)先搜索
常問的圖面試問題：
- 實現(xiàn)廣度優(yōu)先搜索和深度優(yōu)先搜索
- 檢查一個圖是否為樹
- 計算一張圖中的邊的數(shù)量
- 找到兩個頂點之間的最短路徑
樹
樹是一種層級數(shù)據(jù)結(jié)構(gòu)辫继，包含了連接它們的頂點（節(jié)點）和邊。樹和圖很相似俗慈，但二者有個很大的不同點姑宽，即樹中沒有循環(huán)。
樹廣泛應(yīng)用在人工智能和復(fù)雜的算法中闺阱，為解決各種問題提供高效的存儲機制炮车。
下圖是一個簡單的樹，以及在樹型數(shù)據(jù)結(jié)構(gòu)中所用的基本術(shù)語：
下面是幾種類型的樹：
- N 叉樹
- 平衡樹
- 二叉樹
- 二叉搜索樹
- 平衡二叉樹
- 紅黑樹
- 2-3 樹
其中馏颂，二叉樹和二叉搜索樹是最常用的樹示血。
常問的樹面試問題：
- 找到一個二叉樹的高度
- 找到一個二叉搜索樹中第 k 個最大值
- 找到距離根部“k”個距離的節(jié)點
- 找到一個二叉樹中給定節(jié)點的祖先（ancestors）
字典樹
字典樹棋傍，也叫“前綴樹”救拉，是一種樹形結(jié)構(gòu)，在解決字符串相關(guān)問題中非常高效瘫拣。其提供非骋谛酰快速的檢索功能，常用于搜索字典中的單詞，為搜索引擎提供自動搜索建議派昧，甚至能用于IP路由選擇黔姜。
下面展示了“top”“thus”和“their”這三個詞是如何存儲在字典樹中的：
這些單詞以從上到下的方式存儲，其中綠色節(jié)點“p”蒂萎，“s”和“r”分別表示“top”秆吵，“thus”和“their”的末尾。
常見的字典樹面試問題：
- 計算字典樹中的總字數(shù)
- 打印存儲在字典樹中的所有單詞
- 使用字典樹對數(shù)組的元素進行排序
- 使用字典樹從字典中形成單詞
- 構(gòu)建一個T9字典
哈希表
散列是一個用于唯一標識對象并在一些預(yù)先計算的唯一索引（稱為“密鑰”）存儲每個對象的過程五慈。因此纳寂，對象以“鍵值”對的形式存儲，這些項的集合被稱為“字典”泻拦”形撸可以使用該鍵值搜索每個對象。有多種不同的基于哈希的數(shù)據(jù)結(jié)構(gòu)争拐，但最常用的數(shù)據(jù)結(jié)構(gòu)是哈希表腋粥。
哈希表通常使用數(shù)組實現(xiàn)。
哈希數(shù)據(jù)結(jié)構(gòu)的性能取決于以下三個因素：
- 哈希函數(shù)
- 哈希表的大小
- 碰撞處理方法
下圖展示了如何在數(shù)組中映射哈希架曹。該數(shù)組的索引是通過哈希函數(shù)計算的隘冲。
常問的哈希面試問題：
- 找到數(shù)組中的對稱對
- 追蹤遍歷的完整路徑
- 查看一個數(shù)組是否為另一個數(shù)組的子集
- 檢查給定數(shù)組是否不相交
以上就是你在準備編程面試前需要掌握的8種數(shù)據(jù)結(jié)構(gòu)。
在上面的 8 種數(shù)據(jù)結(jié)構(gòu)中音瓷，每種結(jié)構(gòu)都有對應(yīng)的面試問題对嚼，接下來的一段時間我會將這三十一道問題依舊使用動畫的形式解析清楚。
