【程式猿必備】資料結構與演算法精選面試題
有很多計算機科學技術專業的畢業生和程式員申請在Uber和Netflix這樣的初創公司、谷歌和阿里巴巴這樣的大公司以及Infosys或Luxsoft等以服務為基礎的公司從事程式設計、編碼和軟體開發工作,但他們中的許多人都不知道,當你申請這些公司的職位時,你會遇到什麼樣的程式設計面試問題。
在這篇文章中,我將分享一些常見的來自不同經驗水平程式設計師的程式設計面試問題,他們是從剛大學畢業的人到有一到兩年經驗的程式設計師。
程式設計面試主要由 ofollow,noindex" target="_blank"> 資料結構問題和演算法問題 以及一些邏輯問題組成,比如,如何在不使用臨時變數的情況下交換兩個整數?
我認為把程式設計面試問題分成不同的主題領域是有幫助的。我在訪談中經常看到的主題領域是陣列、連結串列、字串、二叉樹,以及來自演算法的問題(例如字串演算法、 快速排序 或 基數排序 等排序演算法),這就是你將在本文中找到的內容。
這些面試題不能保證你會被問到這些程式設計、資料結構和演算法問題,但它們會讓你對在真正的程式設計工作面試中可能遇到的問題有足夠的瞭解。
一旦你完成這些問題,你就應該有足夠的信心參加任何電話或面對面的面試。
順便說一句,如果你對基本的資料結構和演算法沒有充分的知識,或者從沒有接觸過它們,那麼嘗試這些問題就沒有意義了。
在這種情況下,你應該學習一門很好的課程,比如 Robert Horvick 的演算法和資料結構第 1 部分和第 2 部分 ,以更新你的DS和演算法技能。
前50大演算法和編碼面試問題
下面是我列出的一些最常見的程式設計面試問題:
1.陣列編碼面試問題
陣列是最基本的資料結構,它將元素儲存在一個連續的記憶體位置。這也是面試官們熱衷的話題之一,在任何一次 程式設計面試 中,你都會聽到很多關於陣列的問題,比如將陣列中元素位置顛倒,對陣列進行排序,或者搜尋陣列上的元素。
陣列資料結構的主要優點是,如果知道索引,它可以提供快速的O(1)搜尋,但是從陣列中新增和刪除元素是很慢的,因為一旦建立了陣列,就無法更改陣列的大小。
為了建立更小或更大的陣列,需要建立一個新陣列並將所有元素從舊陣列拷貝到新陣列。
解決基於陣列的問題的關鍵是對 陣列資料結構 以及基本的程式設計建構函式(如迴圈、遞迴和基本運算子)要有很好的瞭解。
以下是一些熱門的基於陣列的程式設計面試問題:
1. 如何在一個1到100的整數陣列中找到丟失的數字? ( 方法 )
2. 如何在給定的整數陣列中找到重複的數字? API.html" rel="nofollow,noindex" target="_blank"> ( 方法 )
3. 如何在未排序整數陣列中找到最大值和最小值? ( 方法 )
4. 如何找到陣列所有和等於一個給定數的數對? ( 方法 )
5. 如果一個數組包含多重複制,那麼如何找到重複的數字? ( 方法 )
6. 在Java中如何從給定陣列中刪除多重複制? ( 方法 )
7. 如何使用快速排序演算法對整數陣列進行排序? ( 方法 )
8. 如何從陣列中刪除多重複制? ( 方法 )
9. 如何在Java中對陣列進行反向操作? ( 方法 )
10. 如何在不使用任何庫的情況下從陣列中刪除多重複制? ( 方法 )
這些問題不僅可以幫助你提高解決問題的能力,還可以提高你對陣列資料結構的認識。
如果你需要更高階的基於陣列的問題,那麼你還可以看到 V80-gTri19Cvgu5J_dth09utRg&LSNPUBID=JVFxdTr9V80" rel="nofollow,noindex" target="_blank"> 程式設計面試訓練營 : 演算法 + 資料結構 ,一個專門為面試準備的關於演算法的Bootcamp風格課程,以獲得一個技術巨頭公司的工作,如谷歌,微軟,蘋果,Facebook等。
如果你覺得10個問題不夠用來訓練,或者你需要更多的訓練,你可以看一下這 30 題 。
2.連結串列程式設計面試問題
連結串列 是補充陣列資料結構的另一種常見的資料結構。與陣列類似,它也是一個線性資料結構,以線性方式儲存元素。
然而,與陣列不同的是,它不會將它們儲存在連續的位置;相反,它們分散在記憶體中各處,記憶體使用節點相互連線。
連結串列就是節點列表,每個節點包含儲存的值和下一個節點的地址。
由於這種結構,在連結串列中新增和刪除元素很容易,因為只需要更改連結而不是建立陣列,但是查詢是困難的,並且通常需要O(n)來查詢單個連結串列中的元素。
本文 提供了更多關於陣列和連結串列資料結構之間區別的資訊。
連結串列也有多種形式,比如單鏈表,它允許你沿著一個方向(向前或向後)移動遍歷;雙鏈表,允許在兩個方向(向前和向後)遍歷;最後,迴圈連結串列則形成一個環。
為了解決基於連結串列的問題,對遞迴知識進行了解是很重要的,因為連結串列是遞迴資料結構。
如果從連結串列中取出一個節點,剩下的資料結構仍然是連結串列,因此,許多連結串列問題的遞迴解決方案比迭代解決方案更簡單。
以下是一些最常見和最流行的面試問題及解決方法:
1. 如何在一次遍歷中找到單個連結串列的中值? ( 方法 )
2. 如何證明給定的連結串列是否包含迴圈?如何找到迴圈的頭節點? ( 方法 )
3. 如何使連結串列反向? ( 方法 )
4. 如何在不使用遞迴的情況下逆轉單鏈表? ( 方法 )
5. 如何刪除未排序連結串列中的重複節點? ( 方法 )
7. 如何在單鏈表中從尾部找到第三個節點? ( 方法 )
8. 如何使用堆疊得到兩個連結串列的和? ( 方法 )
這些問題將幫助你發展解決問題的技能,以及提高你對連結串列資料結構的知識。
如果你在解決這些連結串列程式設計問題時遇到困難,那麼我建議你通過瀏覽資料結構和演算法來重新整理 資料結構和演算法技能 : 使用 Java 課程 進行深入研究。
你可以看這 30 題 獲得更多的練習。
3.字串程式設計面試問題
除了陣列和連結串列資料結構外,字串也是程式設計面試中的另一個熱門話題。我參加過的面試,都有以 字串為基礎的問題 。
字串的一個好處是,如果你瞭解陣列,你可以很容易地解決基於字串的問題,因為字串是一個字元陣列。
因此,通過解決基於陣列的程式設計問題所學習的所有技術也可以用於解決字串程式設計問題。
下面是程式設計面試中經常被問到的字串編碼問題:
1. 如何從字串列印重複字元? ( 方法 )
2. 如何檢查兩個字串是否互相顛倒? ( 方法 )
3. 如何從字串中列印第一個非重複字元? ( 方法 )
4. 如何使用遞迴反轉給定的字串? ( 方法 )
5. 如何檢查字串是否只包含數字? ( 方法 )
6. 如何在字串中找到重複的字元? ( 方法 )
7. 在給定的字串中,如何計算母音和子音的數量? ( 方法 )
8. 如何計算字串中給定字元的出現次數? ( 方法 )
9. 如何找到一個字串的所有排列? ( 方法 )
10. 如何在不使用任何庫方法的情況下逆轉一個句子中的單詞? ( 方法 )
11. 如何檢查兩個字串是否互相旋轉? ( 方法 )
12. 如何檢查給定的字串是否迴文? ( 方法 )
這些問題有助於提高對字串資料結構的認識。如果你能在沒有任何幫助的情況下解決所有這些問題,那麼你應該不錯。
對於更高階的問題,我建議解決 Steven Skiena 的演算法設計手冊 中給出的問題,這本書中有最棘手的演算法問題。
如果你需要更多的練習,這裡有另外一個 20 個字串編碼問題 的列表。
4二叉樹編碼面試問題
到目前為止,我們只研究了線性資料結構,但是現實世界中的所有信息都不能以線性方式表示,這就是樹資料結構的作用所在。
樹資料結構是一種允許以分層方式儲存資料的資料結構。根據儲存資料的方式的不同,樹的型別不同,例如二叉樹,其中每個節點最多有兩個子節點。
除了近親二叉搜尋樹,它也是最流行的樹資料結構之一。因此,會有許多基於它們的問題,例如如何遍歷它們、計算節點、查詢深度以及檢查它們是否為平衡二叉樹。
解決二叉樹問題的一個關鍵是要有很強的理論知識,例如二叉樹的大小或深度是什麼,什麼是葉子節點,什麼是節點,以及理解流行的遍歷演算法,例如先序遍歷、後序遍歷和順序遍歷。
下面是一些軟體工程師或開發人員面試中常見的基於二進位制樹的編碼問題:
1. 如何實現二叉搜尋樹? ( 方法 )
2. 如何在給定的二叉樹中執行先序遍歷? ( 方法 )
3. 如何在不使用遞迴的情況下按順序遍歷給定的二叉樹? ( 方法 )
4. 如何在給定的二叉樹中執行順序遍歷? ( 方法 )
5. 如何在不使用遞迴的情況下,使用順序遍歷列印給定二叉樹的所有節點? ( 方法 )
6. 如何實現後序遍歷演算法? ( 方法 )
7. 如何在不使用遞迴的情況下遍歷後序遍歷中的二叉樹? ( 方法 )
8. 如何列印二叉搜尋樹的所有葉子? ( 方法 )
9. 如何計算給定二叉樹中的葉節點數? ( 方法 )
10. 如何在給定陣列中執行二分法搜尋? ( 方法 )
如果你覺得對二叉樹編碼的理解不夠充分,而且你不能自己解決這些問題,我建議你回去選擇一個好的資料結構和演算法課程,比如 從 0 到 1:Java 中的資料結構和演算法。
如果你需要更多的推薦,這裡是我的 資料結構演算法書籍 和 課程列表 。
5.其他編碼面試問題
除了基於資料結構的問題,大多數程式設計工作面試也會問演算法、設計、位操作和基於邏輯的問題,我將在本節中描述這些問題。
練習這些概念是很重要的,因為有時候這些概念在實際面試中很難解決。之前的練習不僅讓你熟悉它們,也讓你在向面試官解釋解決方案時更有信心。
1. 如何實現氣泡排序演算法? ( 方法 )
2. 如何實現迭代快速排序演算法? ( 方法 )
4. 如何實現歸併排序演算法? ( 方法 )
5. 如何實現桶排序演算法? ( 方法 )
6. 如何實現計數排序演算法? ( 方法 )
7. 如何實現基數排序演算法? ( 方法 )
8. 如何在不使用第三個變數的情況下交換兩個數字? ( 方法 )
9. 如何檢查兩個矩形是否重疊? ( 方法 )
10. 如何設計自動售貨機? ( 方法 )
如果你需要更多這樣的程式設計問題,你可以從Gayle Laakmann McDowell的著作 《破解程式碼面試》 中得到幫助,該書提出了189個以上的程式設計問題和解決方案。一本可以在短時間內為程式設計面試做準備的好書。
順便說一下,你在實踐中解決的問題越多,你準備的就越好。所以,如果你認為50題還不夠,你還需要更多,那麼你可以看看這些額外的 50 題 電話 面試的程式設計問題,以及這些 書籍 和 課程 ,以便更徹底的準備。
現在你已經為編碼面試做好了準備
這些是資料結構和演算法之外的一些最常見的問題,可以幫助你在面試中表現出色。這些常見的編碼、資料結構和演算法問題是在任何級別的程式設計工作中成功面試任何公司(無論大小)所需要知道的。
如果你想在2018年找一份程式設計或軟體開發的工作,你可以從這些編碼問題開始準備。
這份清單提供了很好的準備主題,也有助於評估你的準備工作,找出你的優勢和劣勢。良好的資料結構和演算法知識對於編碼面試的成功是很重要的,這也是你應該集中注意力的地方。
本文由 阿里云云棲社群 組織翻譯。
文章原標題《50-data-structure-and-algorithms-interview-questions-for-programmers》
作者: javinpaul 譯者:虎說八道,審校:。
文章為簡譯,更為詳細的內容,請檢視 原文 。