譯文原文：http://pengtuo.tech/algorithms/2018/10/02/data-structure-50/
本文的描述語言為 Java
有許多計(jì)算機(jī)科學(xué)專業(yè)畢業(yè)生或者程序猿會(huì)申請(qǐng)研發(fā)職位，在這個(gè)行業(yè)里有很多待遇比較好的大公司，例如國內(nèi)的BAT，頭條，美團(tuán)等，國外也有亞馬遜，谷歌以及 Facebook 等大型公司，但他們中的許多人都不知道當(dāng)你在這些公司申請(qǐng)工作時(shí)會(huì)遇到什么樣的編程面試問題。
在本文中，我將與不同經(jīng)驗(yàn)水平的程序猿分享一些常見的編程面試問題，涉及從剛從大學(xué)畢業(yè)的人到具有一到兩年經(jīng)驗(yàn)的程序員。
研發(fā)面試主要由 數(shù)據(jù)結(jié)構(gòu)和基于算法的問題 組成，也會(huì)有一些邏輯性的面試問題，例如 如何在不使用臨時(shí)變量的情況下交換兩個(gè)整數(shù)？
我認(rèn)為將算法問題劃分到不同的領(lǐng)域是非常有幫助的。我在面試中經(jīng)常遇見的領(lǐng)域有數(shù)組、鏈表、字符串、二叉樹，還有算法問題（例如字符串算法問題、排序算法問題，或者其他），并且這些都會(huì)在本文中提及。
我不能保證本文中的數(shù)據(jù)結(jié)構(gòu)問題或者算法問題肯定會(huì)被問及，但是這些會(huì)讓你充分了解實(shí)際面試中的遇到的各種問題以及解題思路。
一旦充分學(xué)習(xí)了這些問題，你應(yīng)該有足夠的信心參加任何電話面試或者線下面試。
順便說一下，如果你沒有認(rèn)真學(xué)習(xí)過基本的數(shù)據(jù)結(jié)構(gòu)和算法，或者你沒有多年觸及它們，那么還是建議你先去補(bǔ)充一下基礎(chǔ)知識(shí)，再來研究本文的問題。
Top 50 算法和編程面試問題
話不多說，這里列出我在研發(fā)工作以及面試中一些最常見的算法面試問題列表：
1. 數(shù)組類面試問題
數(shù)組是最基本的數(shù)據(jù)結(jié)構(gòu)，它將元素存儲(chǔ)在連續(xù)的內(nèi)存位置。這也是面試官很喜歡面試的方向，你會(huì)在任何算法面試中聽到很多關(guān)于數(shù)組的問題，例如：反轉(zhuǎn)數(shù)組，排序數(shù)組或搜索數(shù)組上的元素。
數(shù)組數(shù)據(jù)結(jié)構(gòu)最大的優(yōu)點(diǎn)是當(dāng)知道索引時(shí)能夠在 O(1) 的時(shí)間復(fù)雜度內(nèi)搜索，但是向數(shù)組數(shù)據(jù)結(jié)構(gòu)里添加和移除元素時(shí)會(huì)非常慢，因?yàn)閿?shù)組一旦創(chuàng)建就不能更改其規(guī)格。當(dāng)需要更改數(shù)組的大小時(shí)，則需要?jiǎng)?chuàng)建一個(gè)新的數(shù)組，然后從原先的數(shù)組中將元素拷貝到新的數(shù)組中。
解決基于數(shù)組類的算法問題的關(guān)鍵是要充分了解數(shù)組數(shù)據(jù)結(jié)構(gòu)以及基本的編程技能，例如循環(huán)、遞歸等。
以下列出非常受歡迎的基于數(shù)組類的算法面試問題供你練習(xí)：
- 如何在一個(gè)給定的，范圍是 1 到 100 的亂序整數(shù)數(shù)組中找到缺失的值？solution
- 如何在一個(gè)給定的整數(shù)數(shù)組中找到重復(fù)的數(shù)字？solution
- 如何在一個(gè)亂序的整數(shù)數(shù)組中找到最大值與最小值？solution
- 如何找到所有的整數(shù)對(duì)，其總和等于給定的數(shù)字？solution
- 如何在包含多個(gè)重復(fù)項(xiàng)的數(shù)組中找到重復(fù)的數(shù)字？solution
- 如何用 Java 語言在一個(gè)給定的數(shù)組中移除重復(fù)項(xiàng)？solution
- 請(qǐng)利用快速排序?qū)σ粋€(gè)數(shù)組進(jìn)行原地排序。solution
- 如何用 Java 在原地反轉(zhuǎn)一個(gè)數(shù)組？solution
- 請(qǐng)了解數(shù)組問題中的對(duì)撞指針和滑動(dòng)窗口技巧
這些問題不僅能夠幫助你提高解決問題的能力，還能更好的幫助你理解數(shù)組這個(gè)數(shù)據(jù)結(jié)構(gòu)。如果你覺得這幾道題不夠聯(lián)系，則可以查看 30 array question，也可以在 Leetcode或者Lintcode上的數(shù)組標(biāo)簽下找題目。
2. 鏈表類面試題
鏈表是另一種非常常見的數(shù)據(jù)結(jié)構(gòu)。與數(shù)組結(jié)構(gòu)類似，鏈表也是線性數(shù)據(jù)結(jié)構(gòu)并且以線性的方式存儲(chǔ)。
然而，和數(shù)組數(shù)據(jù)結(jié)構(gòu)不同的是，在內(nèi)存物理位置上數(shù)據(jù)元素并不是相鄰的，相反，數(shù)據(jù)是分散存儲(chǔ)在內(nèi)存中，通過節(jié)點(diǎn)與其他數(shù)據(jù)相連。鏈表就是一系列的節(jié)點(diǎn)，其中每個(gè)節(jié)點(diǎn)存儲(chǔ)著數(shù)據(jù)值和下一個(gè)節(jié)點(diǎn)的地址。
由于這種結(jié)構(gòu)，在鏈表中添加和刪除元素很容易，因?yàn)槟恍枰逆溄佣皇莿?chuàng)建數(shù)組，但搜索很困難，在單鏈表中通常需要花費(fèi) O(n) 時(shí)間來查找元素。
鏈表還有其他的變種，例如雙向鏈表，允許在鏈表上兩個(gè)方向（向前或向后）游走；還有循環(huán)鏈表，鏈表的首尾相連組合成一個(gè)圈。
為了解決基于鏈表的問題，需要對(duì)遞歸很了解，因?yàn)殒湵硎?a target="_blank" rel="nofollow">遞歸數(shù)據(jù)結(jié)構(gòu)。如果從鏈表中獲取一個(gè)節(jié)點(diǎn)，則剩余的數(shù)據(jù)結(jié)構(gòu)仍然是鏈表，因此，許多鏈表問題具有比迭代解決方案更簡單的遞歸解決方案。
以下列出一些常見的受歡迎的鏈表的面試問題：
- 如何遍歷一次就找到鏈表的中間節(jié)點(diǎn)？solution
- 如何判斷一個(gè)鏈表是否有環(huán)？如何找到這個(gè)環(huán)的起始節(jié)點(diǎn)？solution
- 如何反轉(zhuǎn)一個(gè)鏈表？solution
- 如何不使用遞歸的情況下反轉(zhuǎn)鏈表？solution
- 如何從未排序的鏈表中移除重復(fù)節(jié)點(diǎn)？solution
- 請(qǐng)求出一個(gè)單鏈表的長度。solution
- 如何找出單鏈表的倒數(shù)第三個(gè)節(jié)點(diǎn)？solution
- 請(qǐng)對(duì)兩個(gè)鏈表表示的整數(shù)求和，并返回鏈表。solution
這些問題將幫助您提高解決問題的能力，并提高您對(duì)鏈表數(shù)據(jù)結(jié)構(gòu)的了解。如果對(duì)于以上這些問題感覺比較吃力，建議先補(bǔ)充鏈表的基礎(chǔ)知識(shí)。你也可以聯(lián)系30 linked list interview questions
3. 字符串類面試問題
與數(shù)組和鏈表數(shù)據(jù)結(jié)構(gòu)同樣，字符串類型是面試中的另一個(gè)熱門話題。關(guān)于字符串問題的好消息是，如果你懂?dāng)?shù)組，你可以很容易地解決基于字符串的問題，因?yàn)樽址皇且粋€(gè)字符數(shù)組。
所以所有你的基于數(shù)組類問題的解題思路與技巧都可以用來解決字符串類型的問題。
以下是我列出的在工作面試中會(huì)被頻繁問及的字符串類型問題：
- 如何將字符串中重復(fù)的字符打印出來？solution
- 如何判斷兩個(gè)亂序的字符串中的字母都相同？solution
- 請(qǐng)將字符串中第一個(gè)未重復(fù)的字符打印出來。solution
- 如何利用遞歸翻轉(zhuǎn)一個(gè)字符串？solution
- 如何判斷一個(gè)字符串中只包含數(shù)字字符？solution
- 請(qǐng)統(tǒng)計(jì)一個(gè)字符串中的元音和輔音的個(gè)數(shù)。solution
- 如何計(jì)算字符串中給定字符的出現(xiàn)次數(shù)？solution
- 請(qǐng)輸出給定字符串的所有排列組合。solution
- 如何翻轉(zhuǎn)給定句子中的單詞？solution
- 如何判斷兩個(gè)字符串互為旋轉(zhuǎn)？solution
- 如何判斷一個(gè)字符是回文字符？solution
這些問題有助于提高您對(duì)字符串作為數(shù)據(jù)結(jié)構(gòu)的了解。 如果你可以在沒有任何幫助的情況下解決所有這些String問題，那么你很棒棒。
如果你需要更多的練習(xí)，可以看這里
4. 二叉樹面試問題
到目前為止，我們只研究了線性數(shù)據(jù)結(jié)構(gòu)，但現(xiàn)實(shí)世界中的所有信息都無法以線性方式表示，而這正是樹數(shù)據(jù)結(jié)構(gòu)所幫助的地方。
樹數(shù)據(jù)結(jié)構(gòu)是一種數(shù)據(jù)結(jié)構(gòu)，允許以分層方式存儲(chǔ)數(shù)據(jù)。 根據(jù)存儲(chǔ)數(shù)據(jù)的方式，有不同類型的樹，例如二叉樹，其每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。以及其近親，二叉搜索樹，這個(gè)是最受歡迎的樹形數(shù)據(jù)結(jié)構(gòu)了。因此你會(huì)發(fā)現(xiàn)有很多的面試問題都是基于二叉樹和二叉搜索樹，例如 如何遍歷，計(jì)算節(jié)點(diǎn)個(gè)數(shù)，找到樹深度或者判斷其是否為平衡樹等。
解決二叉樹問題的一個(gè)關(guān)鍵點(diǎn)是需要很扎實(shí)的理論基礎(chǔ)，例如： 什么是二叉樹的大小或深度，什么是葉子，什么是節(jié)點(diǎn)，以及對(duì)流行的遍歷算法的理解，例如前中后序遍歷。
以下是流行的基于二叉樹的面試問題列表：
- 如何實(shí)現(xiàn)二叉搜索樹？solution
- 請(qǐng)前序遍歷一顆二叉樹。solution
- 請(qǐng)不使用遞歸的情況下前序遍歷一顆二叉樹。solution
- 請(qǐng)中序遍歷一顆二叉樹。solution
- 請(qǐng)?jiān)诓皇褂眠f歸的情況下中序遍歷一顆二叉樹并輸出。solution
- 如何實(shí)現(xiàn)后序遍歷算法？solution
- 請(qǐng)?jiān)诓皇褂眠f歸的情況下后序遍歷一顆二叉樹。solution
- 如何輸出一顆二叉搜索樹的所有葉子結(jié)點(diǎn)？solution
- 如何統(tǒng)計(jì)一顆二叉樹的所有葉子節(jié)點(diǎn)的個(gè)數(shù)。solution
- 如何在一個(gè)數(shù)組中執(zhí)行二分搜索。solution
5. 各式面試問題
除了基于數(shù)據(jù)結(jié)構(gòu)的問題之外，大多數(shù)面試中還會(huì)詢問算法，設(shè)計(jì)，位操作和基于邏輯的一般問題，我將在本節(jié)中對(duì)其進(jìn)行描述。
- 如何實(shí)現(xiàn)冒泡排序？solution
- 如何實(shí)現(xiàn)迭代快速排序算法？solution
- 如何實(shí)現(xiàn)插入排序算法？solution
- 如何實(shí)現(xiàn)歸并排序算法？solution
- 如何實(shí)現(xiàn)桶排序算法？solution
- 如何實(shí)現(xiàn)計(jì)數(shù)排序算法？solution
- 如何實(shí)現(xiàn)基數(shù)排序算法？solution
- 如何在不使用第三個(gè)變量的情況下交換兩個(gè)數(shù)字？solution
- 如何判斷兩個(gè)矩形是否互相重疊？solution
- 如何設(shè)計(jì)自動(dòng)售貨機(jī)？solution
順便說一下，你在實(shí)踐中解決的問題越多，你的準(zhǔn)備就越好。 因此，如果您認(rèn)為 50 還不夠而且您需要更多，那么請(qǐng)查看這些額外的50個(gè)編程問題，以便進(jìn)行更全面的準(zhǔn)備。
現(xiàn)在，你應(yīng)該準(zhǔn)備好了
這些是數(shù)據(jù)結(jié)構(gòu)和算法之外的一些最常見的問題，可以幫助您在面試中做得很好。這些常見的數(shù)據(jù)結(jié)構(gòu)和算法問題是您在任何級(jí)別的技術(shù)面試都需要了解的問題。
如果您正在尋找開發(fā)工作，您可以使用此這些問題列表開始準(zhǔn)備。此列表提供了準(zhǔn)備的好主題，也有助于評(píng)估您的準(zhǔn)備工作，以找出您的優(yōu)勢和劣勢領(lǐng)域。熟悉數(shù)據(jù)結(jié)構(gòu)和算法對(duì)于面試成功非常重要。
譯者：歡迎大家訪問我的個(gè)人博客與留言 http://pengtuo.tech
