同學，你會手寫二叉樹嗎?近來正值秋招季節(jié)，很多編程面試都要求手寫數(shù)據(jù)結(jié)構(gòu)手推機器學習算法。各位同學為了面試也會刷各種編程題，其中數(shù)據(jù)結(jié)構(gòu)與排序搜索算法又是最為基礎(chǔ)的內(nèi)容。在本文中，我們?yōu)楦魑蛔x者準備了 48 道基礎(chǔ)面試題，它可以幫助我們更深地理解數(shù)據(jù)結(jié)構(gòu)。本文所有面試題都提供了 Java 解決方案，并介紹了比較流行的 GitHub 面試題項目。

很多計算機科學專業(yè)畢業(yè)生和程序員都會去 Uber、今日頭條這樣的獨角獸公司，或者亞馬遜、微軟和谷歌這樣的科技巨頭申請編程和軟件開發(fā)職位。你在申請這些工作時，肯定很想知道面試官會問到哪些問題。

在本文中，作者會分享一些常見的編程面試問題，這些問題來自于針對不同經(jīng)驗層次的程序員的面試——從應屆畢業(yè)生到具有一兩年經(jīng)驗的程序員。

編程面試題通常包含數(shù)據(jù)結(jié)構(gòu)和基于算法的問題，以及一些邏輯問題，例如：如何在不使用臨時變量的情況下交換兩個整數(shù)?

為了清晰，編程面試題需要劃分為不同主題。我們在面試中經(jīng)常看到的領(lǐng)域是數(shù)組、鏈表、字符串、二叉樹以及有關(guān)算法的問題(例如字符串算法、快速排序或基數(shù)排序等排序算法)，本文將介紹這些內(nèi)容。

雖然本文無法覆蓋你在面試中將要面臨的所有問題，但是它可以給你提供足夠的思路，讓你在面試時對于各種挑戰(zhàn)有所準備。

一旦解決了這些問題，你就可以有信心面對任何電話面試或現(xiàn)場面試了。

當然，如果你對于基本數(shù)據(jù)結(jié)構(gòu)和算法沒有足夠的知識儲備，那么直接接觸以下問題將對你沒有幫助。

算法和編程面試題 TOP 48

廢話少說，這里有一份「編程面試最常見的問題列表」：

1. 數(shù)組編程面試問題

數(shù)組是最基本的數(shù)據(jù)結(jié)構(gòu)，它將元素儲存在連續(xù)的內(nèi)存空間中。數(shù)組也是面試官最喜歡問的主題之一，在任何編程面試中都能聽到非常多關(guān)于數(shù)組的問題，例如反轉(zhuǎn)數(shù)組、排序數(shù)組或搜索數(shù)組元素等。

數(shù)組這種數(shù)據(jù)結(jié)構(gòu)的主要優(yōu)點在于如果給定索引，那么它會提供 O(1) 復雜度的搜索，這種搜索速度非常迅速。但是從數(shù)組中添加或移除元素會比較慢，因為一旦創(chuàng)建了數(shù)組，我們就很難再更改它的大小。如果需要更長或更短的數(shù)組，我們就需要重新創(chuàng)建新數(shù)組，并將老數(shù)組的所有元素復制到新數(shù)組中。

解決數(shù)組問題的關(guān)鍵是對數(shù)組數(shù)據(jù)結(jié)構(gòu)有比較深的理解，同時還需要了解循環(huán)、遞歸和基本運算子等常見的編程結(jié)構(gòu)。以下是一些常見的數(shù)組編程面試問題：

(1) 在一個元素為 1 到 100 的整數(shù)數(shù)組中，如何搜索缺失元素?

• 解決方案：http://javarevisited.blogspot.com/2014/11/how-to-find-missing-number-on-integer-array-java.html

(2) 給定一個數(shù)組，如何搜索重復元素?

• 解決方案：http://javarevisited.blogspot.com/2014/01/how-to-remove-duplicates-from-array-java-without-collection-API.html

(3) 給定一個亂序數(shù)組，如何搜索***和最小元素?

• 解決方案：http://java67.blogspot.com/2014/02/how-to-find-largest-and-smallest-number-array-in-java.html

(4) 給定一個數(shù)值，如何搜索整數(shù)數(shù)組中加和為該數(shù)值的成對元素?

• 解決方案：http://javarevisited.blogspot.com/2014/08/how-to-find-all-pairs-in-array-of-integers-whose-sum-equal-given-number-java.html

(5) 如果數(shù)組包含多個重復值，如何搜索所有重復值?

• 解決方案：http://javarevisited.blogspot.com/2014/03/3-ways-to-find-first-non-repeated-character-String-programming-problem.html

(6) 給定一個數(shù)組，如何用 Java 刪除重復元素?如何在不使用庫的情況下移除數(shù)組中的重復元素?

• 解決方案：http://javarevisited.blogspot.com/2014/01/how-to-remove-duplicates-from-array-java-without-collection-API.html

(7) 如何使用快速排序算法對整數(shù)數(shù)組進行排序?

• 解決方案：http://javarevisited.blogspot.com/2014/08/quicksort-sorting-algorithm-in-java-in-place-example.html

(8) 如何使用 Java 反轉(zhuǎn)一個數(shù)組?

• 解決方案：http://javarevisited.blogspot.com/2013/03/how-to-reverse-array-in-java-int-String-array-example.html

這些問題不僅能幫助我們提高解決問題的能力，同時也能提升我們關(guān)于數(shù)組數(shù)據(jù)結(jié)構(gòu)的理解。

如果你需要了解更多基于數(shù)組的深度問題，你可以在 GitHub 或 Coursera 上多找找關(guān)于數(shù)據(jù)結(jié)構(gòu)的課程與資料，例如在 GitHub 中，就有非常多關(guān)于數(shù)組的學習資料，下面我們介紹了一份中文版的谷歌的面試資料，它在 GitHub 上有 6 萬多的收藏量。

項目地址：

https://github.com/jwasham/coding-interview-university/blob/master/translations/README-cn.md

2. 鏈表編程面試問題

鏈表是補充數(shù)組數(shù)據(jù)結(jié)構(gòu)的另一種常見數(shù)據(jù)結(jié)構(gòu)。與數(shù)組類似，它也是線性數(shù)據(jù)結(jié)構(gòu)，以線性方式存儲元素。

然而，與數(shù)組不同的是，它不會將元素存儲在連續(xù)的位置;相反，它會將其分散存儲在內(nèi)存中，彼此通過節(jié)點相互連接。鏈表是節(jié)點列表，其中每個節(jié)點包含存儲的值和下一個節(jié)點的地址。

由于這種結(jié)構(gòu)，在鏈表中添加或刪除元素變得很簡單，因為你只需要改變鏈接而不是創(chuàng)建數(shù)組，但是這樣會使搜索變得困難，并且經(jīng)常需要 O(n) 的時間復雜度才能在單個鏈表中找到某個元素。

這篇文章

(https://javarevisited.blogspot.com/2013/07/difference-between-array-and-linked-list-java.html)提供了更多關(guān)于數(shù)組和鏈表數(shù)據(jù)結(jié)構(gòu)之間差異的信息。

鏈表還有多種變體，如單鏈表，即允許在一個方向(正向或反向)上遍歷;雙鏈表則允許你在兩個方向(向前或向后)遍歷;***是循環(huán)鏈表，它形成一個循環(huán)。

要解決關(guān)于鏈表的問題，掌握遞歸知識很重要，因為鏈表是遞歸數(shù)據(jù)結(jié)構(gòu)。

如果你從鏈表中取出一個節(jié)點，剩下的數(shù)據(jù)結(jié)構(gòu)仍然是鏈表，因此，許多鏈表問題的遞歸解比迭代解更簡單。

以下是關(guān)于鏈表的一些常見問題和解決方案：

(9) 如何在一次傳遞中找到單鏈表的中間元素?

• 解決方案：http://javarevisited.blogspot.sg/2012/12/how-to-find-middle-element-of-linked-list-one-pass.html

(10) 如何檢查給定的鏈表是否包含循環(huán)?如何找到循環(huán)的起始節(jié)點?

• 解決方案：http://javarevisited.blogspot.sg/2013/05/find-if-linked-list-contains-loops-cycle-cyclic-circular-check.html

(11) 如何反轉(zhuǎn)鏈表?

• 解決方案：http://www.java67.com/2016/07/how-to-reverse-singly-linked-list-in-java-example.html

(12) 在沒有遞歸的情況下如何反轉(zhuǎn)單鏈表?

• 解決方案：http://javarevisited.blogspot.sg/2017/03/how-to-reverse-linked-list-in-java-using-iteration-and-recursion.html

(13) 如何刪除亂序鏈表中的重復節(jié)點?

• 解決方案：https://www.geeksforgeeks.org/remove-duplicates-from-an-unsorted-linked-list/

(14) 如何測量單鏈表的長度?

• 解決方案：http://javarevisited.blogspot.sg/2016/05/how-do-you-find-length-of-singly-linked.html

(15) 如何從單鏈表的末端找出第三個節(jié)點?

• 解決方案：http://javarevisited.blogspot.sg/2016/07/how-to-find-3rd-element-from-end-in-linked-list-java.html

(16) 如何使用堆棧算出兩個鏈表的總和?

• 解決方案：https://www.geeksforgeeks.org/sum-of-two-linked-lists/

這些問題有助于你發(fā)展解決問題的技能，并提升你對鏈表數(shù)據(jù)結(jié)構(gòu)的了解。目前有非常多的資源可以幫助我們理解鏈表，例如在 GitHub 上一個交互式的編碼實踐中，它使用 Jupyter Notebook 提供了數(shù)據(jù)結(jié)構(gòu)與算法的各種練習，其中就包括了很多鏈表問題及實踐。

項目地址：https://github.com/donnemartin/interactive-coding-challenges

[[245042]]

3. 字符串編碼面試問題

除了數(shù)組和鏈表數(shù)據(jù)結(jié)構(gòu)，字符串也是編程工作面試中的另一熱點話題。我參加過的編碼面試基本都問過關(guān)于字符串的問題。

如果你了解數(shù)組，那么你就能輕易地解決基于字符串的問題，因為字符串就是字符數(shù)組。因此，你通過解決數(shù)組編程問題學到的所有技巧，也能用來解決字符串編程問題。

以下是編程工作面試中常問的字符串編程問題列表：

(17) 如何打印字符串中重復的字符?

• 解決方案：http://java67.blogspot.sg/2014/03/how-to-find-duplicate-characters-in-String-Java-program.html

(18) 如何檢查兩個字符串是否互為逆序?

• 解決方案：http://javarevisited.blogspot.sg/2013/03/Anagram-how-to-check-if-two-string-are-anagrams-example-tutorial.html

(19) 如何打印字符串中***非重復字符?

• 解決方案：http://javarevisited.blogspot.sg/2014/03/3-ways-to-find-first-non-repeated-character-String-programming-problem.html

(20) 如何使用遞歸反轉(zhuǎn)給定字符串?

• 解決方案：http://javarevisited.blogspot.sg/2012/01/how-to-reverse-string-in-java-using.html

(21) 如何檢查一個字符串是否僅包含數(shù)字?

• 解決方案：http://javarevisited.blogspot.sg/2012/10/regular-expression-example-in-java-to-check-String-number.html

(22) 如何搜索字符串中的重復字符?

• 解決方案：http://java67.blogspot.sg/2014/03/how-to-find-duplicate-characters-in-String-Java-program.html

(23) 給定一個字符串，如何統(tǒng)計元音數(shù)和輔音數(shù)?

• 解決方案：http://java67.blogspot.sg/2013/11/how-to-count-vowels-and-consonants-in-Java-String-word.html

(24) 給定一個字符，如同計算它在字符串中出現(xiàn)的次數(shù)?

• 解決方案：http://javarevisited.blogspot.sg/2012/12/how-to-count-occurrence-of-character-in-String.html

(25) 如何搜索一個字符串的所有排列情況?

• 解決方案：http://javarevisited.blogspot.com/2015/08/how-to-find-all-permutations-of-string-java-example.html

(26) 在不使用任何庫的情況下，如何反轉(zhuǎn)給定句子中的單詞?

• 解決方案：http://java67.blogspot.com/2015/06/how-to-reverse-words-in-string-java.html

(27) 如何檢查兩個字符串是不是互為旋轉(zhuǎn)(rotation)?

• 解決方案：http://www.java67.com/2017/07/string-rotation-in-java-write-program.html

(28) 給定一個字符串，如何檢查它是不是回文結(jié)構(gòu)?

• 解決方案：http://java67.blogspot.com/2015/06/how-to-check-is-string-is-palindrome-in.html

這些問題可以提升你對字符串數(shù)據(jù)結(jié)構(gòu)的了解。如果你能獨立解決所有這些字符串問題，說明你的狀態(tài)很好。

如果想深入了解一些更復雜的問題，我推薦你去看 Steven Skiena 的《The Algorithm Design Manual》，這本書里有最難的算法問題。

網(wǎng)上也有該書的 PDF 版，下載地址：

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.471.4772&rep=rep1&type=pdf

如果你需要更多的練習，這里還有另外 20 個關(guān)于字符串編程的問題：

http://javarevisited.blogspot.sg/2015/01/top-20-string-coding-interview-question-programming-interview.html

4. 二叉樹編程面試問題

現(xiàn)在我們只了解了線性數(shù)據(jù)結(jié)構(gòu)方面的問題，但是真實世界中的所有信息不可能全是線性的，這就需要樹數(shù)據(jù)結(jié)構(gòu)了。

樹數(shù)據(jù)結(jié)構(gòu)允許以層級形式存儲數(shù)據(jù)。根據(jù)存儲數(shù)據(jù)的方式，有多種樹類型，如二叉樹。

和它的近親二叉搜索樹一樣，它也是***的樹數(shù)據(jù)結(jié)構(gòu)之一。因此，你會看到很多相關(guān)的有趣問題。例如，如何遍歷樹、計算節(jié)點數(shù)量、找出深度，以及檢查是否平衡。

解決二叉樹問題的關(guān)鍵在于深厚的理論知識，如二叉樹的大小或深度、什么是葉節(jié)點、什么是節(jié)點，以及了解流行的遍歷算法。

以下是軟件工程師或開發(fā)工作面試中常見的二叉樹相關(guān)編程問題：

(29) 如何實現(xiàn)二叉搜索樹?

• 解決方案：http://javarevisited.blogspot.sg/2015/10/how-to-implement-binary-search-tree-in-java-example.html#axzz4wnEtnNB3

(30) 如何對給定二叉樹執(zhí)行前序遍歷?

• 解決方案：http://javarevisited.blogspot.sg/2016/07/binary-tree-preorder-traversal-in-java-using-recursion-iteration-example.html#axzz***rdIFI7y

(31) 如何在沒有遞歸的情況下對給定二叉樹執(zhí)行前序遍歷?

• 解決方案：http://www.java67.com/2016/07/binary-tree-preorder-traversal-in-java-without-recursion.html

(32) 如何對給定二叉樹執(zhí)行中序遍歷?

• 解決方案：http://www.java67.com/2016/08/binary-tree-inorder-traversal-in-java.html

(33) 如何在沒有遞歸的情況下通過對給定二叉樹執(zhí)行中序遍歷來打印所有節(jié)點?

• 解決方案：http://www.java67.com/2016/08/binary-tree-inorder-traversal-in-java.html

(34) 如何實現(xiàn)后序遍歷算法?

• 解決方案：http://www.java67.com/2016/10/binary-tree-post-order-traversal-in.html

(35) 如何在沒有遞歸的情況下對給定二叉樹執(zhí)行后序遍歷?

• 解決方案：http://www.java67.com/2017/05/binary-tree-post-order-traversal-in-java-without-recursion.html

(36) 如何打印二叉搜索樹的所有葉節(jié)點?

• 解決方案：http://www.java67.com/2016/09/how-to-print-all-leaf-nodes-of-binary-tree-in-java.html

(37) 如何計算給定二叉樹中葉節(jié)點的數(shù)量?

• 解決方案：http://javarevisited.blogspot.sg/2016/12/how-to-count-number-of-leaf-nodes-in-java-recursive-iterative-algorithm.html

(38) 如何在給定數(shù)組中執(zhí)行二元搜索?

• 解決方案：http://javarevisited.blogspot.sg/2015/10/how-to-implement-binary-search-tree-in-java-example.html#axzz4wnEtnNB3

如果你認為自己對二叉樹編程的了解不足，無法解決這些問題，我建議你先熟練掌握數(shù)據(jù)結(jié)構(gòu)和算法知識，比如你可以上這門課《From 0 to 1: Data Structures & Algorithms in Java》。同樣，你也可以查閱準備 Google 面試的一套完整手冊，這套 GitHub 手冊前面已經(jīng)介紹了，但它在二叉樹等數(shù)據(jù)結(jié)構(gòu)上真的有非常多的案例與教程。

項目地址：https://github.com/jwasham/coding-interview-university

[[245043]]

如果你需要更多推薦，可以參考：

• http://javarevisited.blogspot.sg/2015/07/5-data-structure-and-algorithm-books-best-must-read.html
• http://javarevisited.blogspot.sg/2018/01/top-5-free-data-structure-and-algorithm-courses-java—c-programmers.html

5. 其它編程面試問題

除了數(shù)據(jù)結(jié)構(gòu)方面的問題，大部分編程工作面試也會問關(guān)于算法、設(shè)計、位運算和通用的邏輯問題。

針對性練習很重要，因為有時在實際面試中它們會有點難解。事先練習不僅能夠讓你熟悉這些問題，還能讓你在向面試官解釋答案時更加自信。

(39) 如何實現(xiàn)冒泡排序算法(bubble sort algorithm)?

• 解決方案：http://javarevisited.blogspot.sg/2014/08/bubble-sort-algorithm-in-java-with.html#axzz***rdIFI7y

(40) 如何實現(xiàn)迭代快速排序算法(iterative quicksort algorithm)?

• 解決方案：http://javarevisited.blogspot.sg/2016/09/iterative-quicksort-example-in-java-without-recursion.html#axzz***rdIFI7y

(41) 如何實現(xiàn)插入排序算法(insertion sort algorithm)?

• 解決方案：http://www.java67.com/2014/09/insertion-sort-in-java-with-example.html

(42) 如何實現(xiàn)歸并排序算法(merge sort algorithm)?

• 解決方案：http://www.java67.com/2018/03/mergesort-in-java-algorithm-example-and.html

(43) 如何實現(xiàn)桶排序算法(bucket sort algorithm)?

• 解決方案：http://javarevisited.blogspot.sg/2017/01/bucket-sort-in-java-with-example.html

(44) 如何實現(xiàn)計數(shù)排序算法(counting sort algorithm)?

• 解決方案：http://www.java67.com/2017/06/counting-sort-in-java-example.html

(45) 如何實現(xiàn)基數(shù)排序算法(radix sort algorithm)?

• 解決方案：http://www.java67.com/2018/03/how-to-implement-radix-sort-in-java.html

(46) 如何在不使用第三個變量的前提下交換兩個數(shù)字?

• 解決方案：http://www.java67.com/2015/08/how-to-swap-two-integers-without-using.html

(47) 如何確認兩個矩形是否重疊?

• 解決方案：http://javarevisited.blogspot.sg/2016/10/how-to-check-if-two-rectangle-overlap-in-java-algorithm.html

(48) 如何設(shè)計自動販賣機?

• 解決方案：http://javarevisited.blogspot.sg/2016/06/design-vending-machine-in-java.html

如果你想查看更多此類編程問題，可以閱讀這本書《Cracking the Coding Interview: 189 Programming Questions and Solutions》，適合短時間內(nèi)準備編程工作面試。

下載地址：http://lib1.org/_ads/fcb49f53d5e943ce8acdc4469f63dc5d

你練習的問題越多，準備就越充分。因此，如果你認為 48 道題不夠的話，可以查看：

• https://javarevisited.blogspot.com/2015/02/50-programmer-phone-interview-questions-answers.html
• http://javarevisited.blogspot.sg/2016/06/top-5-books-for-programming-coding-interviews-best.html
• http://javarevisited.blogspot.sg/2018/02/10-courses-to-prepare-for-programming-job-interviews.html

現(xiàn)在你已經(jīng)準備好面試了

這部分將介紹一些數(shù)據(jù)結(jié)構(gòu)和算法之外的常見問題，可以幫助你在面試中取得更好的表現(xiàn)。

我的博客中還有很多此類問題，詳見：http://www.java67.com/

這些常見的編程、數(shù)據(jù)結(jié)構(gòu)和算法問題是你去任何一家公司面試都必須知道的，不管是大公司還是小公司，不管面試的職位高或低。

如果你正在尋找編程或軟件開發(fā)工作，那么你可以先使用這些編程問題開始準備。該列表提供了一些不錯的面試準備話題，能夠幫助你評估自己的面試準備工作是否充分。

熟練掌握數(shù)據(jù)結(jié)構(gòu)和算法知識是編程工作面試成功的關(guān)鍵，你應該更多地關(guān)注這些問題。

擴展閱讀：

• Data Structures and Algorithms: Deep Dive Using Java：https://click.linksynergy.com/fs-bin/click?id=JVFxdTr9V80&subid=0&offerid=323058.1&type=10&tmpid=14538&RD_PARM1=https%3A%2F%2Fwww.udemy.com%2Fdata-structures-and-algorithms-deep-dive-using-java%2F
• 10 Books to Prepare Technical Programming/Coding Job Interviews：http://www.java67.com/2017/06/10-books-to-prepare-technical-coding-job-interviews.html
• 10 Algorithm Books Every Programmer Should Read：http://www.java67.com/2015/09/top-10-algorithm-books-every-programmer-read-learn.html
• Top 5 Data Structure and Algorithm Books for Java Developers：http://javarevisited.blogspot.sg/2016/05/5-free-data-structure-and-algorithm-books-in-java.html#axzz4uXETWjmV
• From 0 to 1: Data Structures & Algorithms in Java：https://click.linksynergy.com/fs-bin/click?id=JVFxdTr9V80&subid=0&offerid=323058.1&type=10&tmpid=14538&RD_PARM1=https%3A%2F%2Fwww.udemy.com%2Ffrom-0-to-1-data-structures%2F
• Data Structure and Algorithms Analysis—Job Interview：https://click.linksynergy.com/fs-bin/click?id=JVFxdTr9V80&subid=0&offerid=323058.1&type=10&tmpid=14538&RD_PARM1=https%3A%2F%2Fwww.udemy.com%2Fdata-structure-and-algorithms-analysis%2F

原文鏈接：

https://hackernoon.com/50-data-structure-and-algorithms-interview-questions-for-programmers-b4b1ac61f5b0

【本文是51CTO專欄機構(gòu)“機器之心”的原創(chuàng)譯文，微信公眾號“機器之心( id: almosthuman2014)”】

戳這里，看該作者更多好文