導(dǎo)讀國外IT教育學(xué)院Educative.io創(chuàng)始人FahimulHaq寫過一篇過萬贊的文章《Thetopdatastructuresyoushouldknowf....

國外 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)知識(shí)。

Fahim ul Haq 曾在 Facebook 和微軟任職，面試過不少程序員，所以這篇文章還是值得參考的。以下內(nèi)容編譯自他的這篇《準(zhǔn)備下次編程面試前你應(yīng)該知道的數(shù)據(jù)結(jié)構(gòu)》：

準(zhǔn)備下次編程面試前你應(yīng)該知道的數(shù)據(jù)結(jié)構(gòu)

瑞典計(jì)算機(jī)科學(xué)家 Niklaus Wirth 在 1976 年寫了一本書，叫作《Algorithms Data Structures = Programs》（算法 數(shù)據(jù)結(jié)構(gòu)=程序）。

即便在 40 年后的今天，這條等式仍然成立。這也是為何程序員求職者應(yīng)該向面試官展示出已經(jīng)透徹理解了數(shù)據(jù)結(jié)構(gòu)知識(shí)。

幾乎所有的面試問題都要求求職者表現(xiàn)出已經(jīng)熟練掌握數(shù)據(jù)結(jié)構(gòu)，不管你是剛畢業(yè)的應(yīng)屆生還是工作了多年的老手，都是這樣。

有時(shí)，面試問題會(huì)明確提到數(shù)據(jù)結(jié)構(gòu)，比如“給定一個(gè)二叉樹”；有時(shí)則比較含蓄，比如“我們想追蹤和每位作者相關(guān)的書籍?dāng)?shù)量。”

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)知識(shí)很有必要，哪怕你只是想找份比現(xiàn)在的工作更好的一份差事。我們首先了解數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)。

什么是數(shù)據(jù)結(jié)構(gòu)？

簡(jiǎn)單說，數(shù)據(jù)結(jié)構(gòu)就是一個(gè)容器，以某種特定的布局存儲(chǔ)數(shù)據(jù)。這個(gè)“布局”使得數(shù)據(jù)結(jié)構(gòu)在某些操作上非常高效，在另一些操作上則不那么高效。你的目標(biāo)就是理解數(shù)據(jù)結(jié)構(gòu)，這樣就能為手頭的問題選擇最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。

為什么我們需要數(shù)據(jù)結(jié)構(gòu)？

由于數(shù)據(jù)結(jié)構(gòu)用來以有組織的形式存儲(chǔ)數(shù)據(jù)，而且數(shù)據(jù)是計(jì)算機(jī)科學(xué)中最重要的實(shí)體，因此數(shù)據(jù)結(jié)構(gòu)的真正價(jià)值顯而易見。

無論你解決什么問題，你都必須以這種或那種方式處理數(shù)據(jù)比如員工的工資，股票價(jià)格，購物清單，甚至簡(jiǎn)單的電話簿等等。

根據(jù)不同的場(chǎng)景，數(shù)據(jù)需要以特定格式存儲(chǔ)。目前有一些數(shù)據(jù)結(jié)構(gòu)可以滿足我們以不同格式存儲(chǔ)數(shù)據(jù)的需求。

常用的數(shù)據(jù)結(jié)構(gòu)

我們首先列出最常用的數(shù)據(jù)結(jié)構(gòu)，然后再挨個(gè)講解：

• 數(shù)組
• 堆棧
• 隊(duì)列
• 鏈表
• 樹
• 圖
• 字典樹
• 哈希表

數(shù)組

數(shù)組是一種最簡(jiǎn)單和最廣泛使用的數(shù)據(jù)結(jié)構(gòu)，其它數(shù)據(jù)結(jié)構(gòu)比如堆棧和隊(duì)列都源自數(shù)組。

下圖是一個(gè)大小為 4 的簡(jiǎn)單數(shù)組，包含幾個(gè)元素（ 1 , 2 , 3，4）。

數(shù)組

每個(gè)數(shù)據(jù)元素會(huì)被分配一個(gè)正的數(shù)值，叫作“索引”，它對(duì)應(yīng)該元素在數(shù)組中的位置。大部分編程語言都將初始索引定義為 0.

以下是兩種數(shù)組：

• 一維數(shù)組（如上所示）
• 多維數(shù)組（數(shù)組的數(shù)組）

數(shù)組的基本操作：

• Insert——在給定索引位置插入一個(gè)元素
• Get——返回給定索引位置的元素
• Delete——?jiǎng)h除給定索引位置的元素
• Size——獲取數(shù)組內(nèi)所有元素的總數(shù)

常問的數(shù)組面試問題：

• 找到數(shù)組中第二小的元素
• 找到數(shù)組中第一個(gè)沒有重復(fù)的整數(shù)
• 合并兩個(gè)分類數(shù)組
• 重新排列數(shù)組中的正值和負(fù)值

堆棧

我們都熟悉很有名的撤銷（Undo）選項(xiàng)，它幾乎存在每個(gè)應(yīng)用程序中。有沒有想過它是如何工作的？其思路就是，按照最后的狀態(tài)排列在先的順序?qū)⒐ぷ鞯南惹盃顟B(tài)（限于特定數(shù)字）存儲(chǔ)在內(nèi)存中。這只用數(shù)組是無法實(shí)現(xiàn)的，因此堆棧就有了用武之地。

可以把堆棧看作一堆垂直排列的書籍。為了獲得位于中間位置的書，你需要拿掉放在它上面的所有書籍。這就是 LIFO（后進(jìn)先出）方法的工作原理。

這是一個(gè)包含三個(gè)數(shù)據(jù)元素（1,2 和 3）的堆棧圖像，其中3位于頂部，首先把它刪除：

堆棧

堆棧的基本操作：

• Push——在頂部插入元素
• Pop—— 從堆棧中刪除后返回頂部元素
• isEmpty——如果堆棧為空，則返回 true
• Top ——返回頂部元素，但不從堆棧中刪除

常見的堆棧面試問題：

• 使用堆棧計(jì)算后綴表達(dá)式
• 對(duì)堆棧中的值進(jìn)行排序
• 檢查表達(dá)式中的括號(hào)是否平衡

隊(duì)列

與堆棧類似，隊(duì)列是另一種線性數(shù)據(jù)結(jié)構(gòu)，以順序方式存儲(chǔ)元素。堆棧和隊(duì)列之間唯一的顯著區(qū)別是，隊(duì)列不是使用 LIFO 方法，而是應(yīng)用 FIFO 方法，這是 First in First Out（先入先出）的縮寫。

隊(duì)列的完美現(xiàn)實(shí)例子：一列人在售票亭等候。如果有新人來，他們是從末尾加入隊(duì)列，而不是在開頭——站在前面的人將先買到票然后離開隊(duì)列。

下圖是一個(gè)包含四個(gè)數(shù)據(jù)元素（1,2,3 和 4）的隊(duì)列，其中 1 位于頂部，首先把它刪除：

隊(duì)列

隊(duì)列的基本操作：

• Enqueue() —— 向隊(duì)列末尾插入元素
• Dequeue() —— 從隊(duì)列頭部移除元素
• isEmpty() —— 如果隊(duì)列為空，則返回 true
• Top() —— 返回隊(duì)列的第一個(gè)元素

常問的隊(duì)列面試問題：

• 使用隊(duì)列來實(shí)現(xiàn)堆棧
• 顛倒隊(duì)列中前 k 個(gè)元素的順序
• 使用隊(duì)列生成從 1 到 n 的二進(jìn)制數(shù)

鏈表

鏈表是另一個(gè)重要的線性數(shù)據(jù)結(jié)構(gòu)，剛一看可能看起來像數(shù)組，但在內(nèi)存分配，內(nèi)部結(jié)構(gòu)以及如何執(zhí)行插入和刪除的基本操作方面有所不同。

鏈表就像一個(gè)節(jié)點(diǎn)鏈，其中每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向鏈中后續(xù)節(jié)點(diǎn)的指針等信息。有一個(gè)頭指針，指向鏈表的第一個(gè)元素，如果列表是空的，那么它只指向 null 或不指向任何內(nèi)容。

鏈表用于實(shí)現(xiàn)文件系統(tǒng)，哈希表和鄰接表。下圖是鏈表內(nèi)部結(jié)構(gòu)的直觀展示：

鏈表

下面是幾種類型的鏈表：

• 單鏈表（單向）
• 雙鏈表（雙向）

鏈表的基本操作：

• InsertAtEnd —— 在鏈表末尾插入指定元素
• InsertAtHead —— 在鏈表頭部插入指定元素
• Delete —— 從鏈表中刪除指定元素
• DeleteAtHead —— 刪除鏈表的第一個(gè)元素
• Search —— 返回鏈表中的指定元素
• isEmpty —— 如果鏈表為空，返回 true

常問的鏈表面試問題：

• 翻轉(zhuǎn)列表
• 檢測(cè)鏈表中的循環(huán)
• 返回鏈表中倒數(shù)第 n 個(gè)節(jié)點(diǎn)
• 移除鏈表中的重復(fù)值

圖

圖就是一組節(jié)點(diǎn)，以網(wǎng)絡(luò)的形式互相連接。節(jié)點(diǎn)也被稱為頂點(diǎn)（vertices）。一對(duì)（x,y）就叫做一個(gè)邊，表示頂點(diǎn) x 和頂點(diǎn) y 相連。一個(gè)邊可能包含權(quán)重/成本，顯示從頂點(diǎn) x 到 y 所需的成本。

圖

圖的類型：

• 無向圖
• 有向圖

在編程語言中，圖可以表示為兩種形式：

• 鄰接矩陣
• 鄰接列表

常見的圖遍歷算法：

• 廣度優(yōu)先搜索
• 深度優(yōu)先搜索

常問的圖面試問題：

• 實(shí)現(xiàn)廣度優(yōu)先搜索和深度優(yōu)先搜索
• 檢查一個(gè)圖是否為樹
• 計(jì)算一張圖中的邊的數(shù)量
• 找到兩個(gè)頂點(diǎn)之間的最短路徑

樹

樹是一種層級(jí)數(shù)據(jù)結(jié)構(gòu)，包含了連接它們的頂點(diǎn)（節(jié)點(diǎn)）和邊。樹和圖很相似，但二者有個(gè)很大的不同點(diǎn)，即樹中沒有循環(huán)。

樹廣泛應(yīng)用在人工智能和復(fù)雜的算法中，為解決各種問題提供高效的存儲(chǔ)機(jī)制。

下圖是一個(gè)簡(jiǎn)單的樹，以及在樹型數(shù)據(jù)結(jié)構(gòu)中所用的基本術(shù)語：

樹

下面是幾種類型的樹：

• N 叉樹
• 平衡樹
• 二叉樹
• 二叉搜索樹
• 平衡二叉樹
• 紅黑樹
• 2-3 樹

其中，二叉樹和二叉搜索樹是最常用的樹。

常問的樹面試問題：

• 找到一個(gè)二叉樹的高度
• 找到一個(gè)二叉搜索樹中第 k 個(gè)最大值
• 找到距離根部“k”個(gè)距離的節(jié)點(diǎn)
• 找到一個(gè)二叉樹中給定節(jié)點(diǎn)的祖先（ancestors）

字典樹

字典樹，也叫“前綴樹”，是一種樹形結(jié)構(gòu)，在解決字符串相關(guān)問題中非常高效。其提供非常快速的檢索功能，常用于搜索字典中的單詞，為搜索引擎提供自動(dòng)搜索建議，甚至能用于IP路由選擇。

下面展示了“top”“thus”和“their”這三個(gè)詞是如何存儲(chǔ)在字典樹中的：

字典樹

這些單詞以從上到下的方式存儲(chǔ)，其中綠色節(jié)點(diǎn)“p”，“s”和“r”分別表示“top”，“thus”和“their”的末尾。

常見的字典樹面試問題：

• 計(jì)算字典樹中的總字?jǐn)?shù)
• 打印存儲(chǔ)在字典樹中的所有單詞
• 使用字典樹對(duì)數(shù)組的元素進(jìn)行排序
• 使用字典樹從字典中形成單詞
• 構(gòu)建一個(gè)T9字典

哈希表

散列是一個(gè)用于唯一標(biāo)識(shí)對(duì)象并在一些預(yù)先計(jì)算的唯一索引（稱為“密鑰”）存儲(chǔ)每個(gè)對(duì)象的過程。因此，對(duì)象以“鍵值”對(duì)的形式存儲(chǔ)，這些項(xiàng)的集合被稱為“字典”。可以使用該鍵值搜索每個(gè)對(duì)象。有多種不同的基于哈希的數(shù)據(jù)結(jié)構(gòu)，但最常用的數(shù)據(jù)結(jié)構(gòu)是哈希表。

哈希表通常使用數(shù)組實(shí)現(xiàn)。

哈希數(shù)據(jù)結(jié)構(gòu)的性能取決于以下三個(gè)因素：

• 哈希函數(shù)
• 哈希表的大小
• 碰撞處理方法

下圖展示了如何在數(shù)組中映射哈希。該數(shù)組的索引是通過哈希函數(shù)計(jì)算的。

哈希表

常問的哈希面試問題：

• 找到數(shù)組中的對(duì)稱對(duì)
• 追蹤遍歷的完整路徑
• 查看一個(gè)數(shù)組是否為另一個(gè)數(shù)組的子集
• 檢查給定數(shù)組是否不相交

以上就是你在準(zhǔn)備編程面試前需要掌握的8種數(shù)據(jù)結(jié)構(gòu)。

在上面的 8 種數(shù)據(jù)結(jié)構(gòu)中，每種結(jié)構(gòu)都有對(duì)應(yīng)的面試問題，接下來的一段時(shí)間我會(huì)將這三十一道問題依舊使用動(dòng)畫的形式解析清楚。

這三十一篇文章會(huì)發(fā)布在我的付費(fèi)小專欄平臺(tái)。歡迎訂閱查看。