程式設計師必備的50道數據結構和演算法面試題

• 2019 年 10 月 31 日
• 筆記

在本文中，將分享一些常見的編程面試問題，這些問題來自於不同經驗水平的程式設計師，囊括從剛大學畢業的人到具有一到兩年經驗的程式設計師。

編碼面試主要包括數據結構和基於演算法的問題，以及一些諸如如何在不使用臨時變數的情況下交換兩個整數這樣的邏輯問題？

我認為將編程面試問題劃分到不同的主題區域是很有幫助的。我在面試中經常看到的主題區域是數組、鏈表、字元串、二叉樹，以及源於演算法的問題（例如字元串演算法，排序演算法，如 quicksort 或基數排序，以及其他雜項），這就是你能在這篇文章中找到主要內容。

我們無法保證你會被問及這些編程或數據結構和演算法問題，但它們會讓你充分了解在實際編程工作面試中可預期的各類問題。

一旦你知道了這些問題，你應該有足夠的信心參加任何電話或面對面的面試。順便說一句，如果你對基本的數據結構和演算法沒有足夠了解，或者你多年未接觸相關知識，那麼嘗試這些問題毫無意義。

閑言少敘，下面就是我給出的程式類面試中最常問到的問題清單：

數組問題

數組是最常用的基礎數據結構，它將元素保存在連續的記憶體中。它也是面試最喜歡的問題之一，在程式碼面試中你會經常聽到很多關於數組的問題，例如，數組的反轉、數組的排序或者查找數組中的一個元素。

數組結構的一個關鍵優點是在知道索引的情況能夠以 O(1) 的複雜度找到一個元素。但是增加或者刪除一個元素是很慢的，因為一旦創建了一個數組，你就不能改變它的大小了。

為了創建一個更長或者更短的數組，你需要創建一個新的數組，然後將所有元素從舊數組中複製到新數組中。

解決數組問題的關鍵是，你要對數組這種數據結構有一個深刻的認識，同時還要了解基本的程式流程如循環、遞歸以及基本的操作符。

下面是一些經常問到和數組相關的面試題，你可以拿來練習：

1、在一個給定的從1到100的整型數組中，如何快速找到缺失的數字？

2、如何找到一個給定的整型數組中的重複數字？

3、在一個未排序的整型數組中，如何找到最大和最小的數字？

4、在一個整型數組中，如何找到一個所有成對的數字，滿足它們的和等於一個給定的數字？

5、如果一個數組包含多個重複元素，如何找到這些重複的數字？

6、用 Java 實現從一個給定數組中刪除重複元素？

7、如何利用快速排序對一個整型數組進行排序？

8、如何從一個數組中刪除重複元素？

9、用 Java 實現數組反轉？

10、如何不藉助庫實現從數組中刪除重複元素？

鏈表問題

鏈表是另外一個常見的數據結構，對數組結構是一個補充。和數組類似，它也是一個線性的數據結構，以線性方式存儲元素。

不過和數組不同的是，鏈表的元素不是存儲在連續位置中，而是分散在各個記憶體中的各個位置，通過節點鏈接起來。一個鏈表就是一個包含了下個節點記憶體地址的節點列表。

基於這種結構，可以很容易實現鏈表中元素的添加和刪除，因為只需要改變節點的指向而無需創建一個新的數組。不過鏈表中的查找是相對困難的，在一個單向鏈表中需要花費 O(n) 的時間代價來查找一個元素。

鏈表有幾種不同的形式。首先是單向鏈表，在這個結構你只能向一個方向遍歷（向前或者反轉）；其次是雙向鏈表，你可以雙向遍歷（向前或者向後）；最後是環形鏈表，組成一個環的形式。

要解決鏈表問題，你就必須了解遞歸的相關知識，因為鏈表是一種遞歸的數據結構。如果你從鏈表中去掉一個節點, 剩下的數據結構仍然是鏈表，因此, 許多鏈表問題有比遍歷更簡單的遞歸解決方案.

下面是一些最常見和流行的鏈表面試問題

1、在一次遍歷中，怎樣發現單個鏈表的中間元素?

2、怎樣驗證給定的鏈表是環形的? 怎樣發現這個環的起始節點?

3、怎樣翻轉鏈表?

4、不使用遞歸，怎樣反轉單個鏈表?

5、在未排序鏈表中，怎樣移除重複的節點?

6、怎樣找出單個鏈表的長度?

7、從單個鏈表的結尾處，怎樣找出鏈表的第三個節點?

8、怎樣使用棧計算兩個鏈表的和?

字元串相關問題

與數組和鏈表數據結構一起，字元串是編程工作面試中的另一個熱門話題。我從未參加過沒有問過基於字元串相關問題的編碼面試。

字元串的一個優勢在於，如果你了解數組，你可以很容易地解決基於字元串的問題，因為字元串僅僅是一個字元數組。

因此，在解決基於數組的編程問題中所學到的所有技術也可用於解決字元串編程問題。

以下是編程求職面試中常見的字元串編程問題：

1、如何輸出字元串中的重複字元？

2、如何判斷兩個字元串是否互為迴文？

3、如何從字元串中輸出第一個不重複字元？

4、如何使用遞歸實現字元串反轉?

5、如何檢查字元僅包含數字字元？

6、如何在字元串中找到重複字元？

7、如何對給定字元串中的母音及輔音進行計數？

8、如何計算給定字元傳中特定字元出現的次數？

9、如何找到一個字元串的全排列？

10、在不使用任何庫方法的情況下如何反轉給定語句中的單詞？

11、如何判斷兩個字元串是否互為旋轉？

12、如何判斷給定字元串是否是迴文？

二叉樹問題

到目前為止，我們只研究了線性數據結構，但現實世界中的所有資訊無法全部使用線性方式表示，而這正是樹數據結構所擅長的地方。

樹是一種支援以分層方式存儲數據的數據結構。根據你存儲數據的方式，有不同類型的樹，例如二叉樹，其中每個節點最多有兩個子節點。

與它的近親二叉搜索樹一起，它們也是最流行的樹數據結構之一。因此，你會發現很多基於它們的問題，例如如何遍歷它們、計算節點數、查找深度，以及檢查它們是否平衡。

解決二叉樹問題的一個關鍵點是對其理論的深刻理解，例如：什麼是二叉樹的大小或深度，什麼是葉節點，什麼是節點，以及對流行的遍歷演算法的理解，例如前序、後序和中序遍歷。

下面是一些經常問到的基於二叉樹的面試題，你可以拿來練習：

1、二叉搜索樹是如何實現的？

2、如何在給定二叉樹上實現前序遍歷？

3、不使用遞歸如何按照前序遍歷給定二叉樹？

4、如何在給定二叉樹上實現中序遍歷？

5、不使用遞歸情況下如何使用中序遍歷輸出給定二叉樹所有節點？

6、如何實現後序遍歷演算法？

7、如何不使用遞歸實現二叉樹的後續遍歷？

8、如何輸出二叉搜索樹的所有葉節點？

9、如何在給定二叉樹中計算葉節點數目？

10、如何在給定數組中執行二分搜索？

編程面試問題之雜項

除了基於數據結構的問題之外，大多數編程工作面試還會詢問演算法、設計、位操作和基於邏輯的常規問題，我將在本節中對其進行介紹。

練習這些概念很重要，因為有時在實際面試中解決這些概念很棘手。提前練習它們不僅能讓你熟悉它們，而且還讓你更自信地向面試官解釋其解決方案。

1、冒泡排序是如何實現的?

2、迭代式快排演算法是如何實現的？

3、你如何實現插入排序演算法？

4、合併排序演算法是如何實現的？

5、桶排序演算法是如何實現的？

6、計數排序演算法是如何實現的？

7、基數排序演算法是如何實現的？

8、在不使用第三個變數的前提下如何交換兩個數？

9、如何檢查兩個矩形是否重疊？

10、如何設計一個自動售貨機？

以上這些是數據結構和演算法之外的一些最常見的面試問題，可以幫助你在面試中做得很好。