原文鏈接：https://hackernoon.com/50-data-structure-and-algorithms-interview-questions-for-programmers-b4b1ac61f5b0

譯文原文：http://pengtuo.tech/algorithms/2018/10/02/data-structure-50/

本文的描述語(yǔ)言為 Java

image

有許多計(jì)算機(jī)科學(xué)專(zhuān)業(yè)畢業(yè)生或者程序猿會(huì)申請(qǐng)研發(fā)職位，在這個(gè)行業(yè)里有很多待遇比較好的大公司吧碾，例如國(guó)內(nèi)的BAT凰盔，頭條，美團(tuán)等倦春，國(guó)外也有亞馬遜户敬，谷歌以及 Facebook 等大型公司，但他們中的許多人都不知道當(dāng)你在這些公司申請(qǐng)工作時(shí)會(huì)遇到什么樣的編程面試問(wèn)題睁本。

在本文中尿庐，我將與不同經(jīng)驗(yàn)水平的程序猿分享一些常見(jiàn)的編程面試問(wèn)題，涉及從剛從大學(xué)畢業(yè)的人到具有一到兩年經(jīng)驗(yàn)的程序員呢堰。

研發(fā)面試主要由 數(shù)據(jù)結(jié)構(gòu)和基于算法的問(wèn)題 組成抄瑟，也會(huì)有一些邏輯性的面試問(wèn)題，例如 如何在不使用臨時(shí)變量的情況下交換兩個(gè)整數(shù)暮胧？

我認(rèn)為將算法問(wèn)題劃分到不同的領(lǐng)域是非常有幫助的锐借。我在面試中經(jīng)常遇見(jiàn)的領(lǐng)域有數(shù)組、鏈表往衷、字符串钞翔、二叉樹(shù)，還有算法問(wèn)題（例如字符串算法問(wèn)題席舍、排序算法問(wèn)題布轿，或者其他），并且這些都會(huì)在本文中提及。

我不能保證本文中的數(shù)據(jù)結(jié)構(gòu)問(wèn)題或者算法問(wèn)題肯定會(huì)被問(wèn)及汰扭，但是這些會(huì)讓你充分了解實(shí)際面試中的遇到的各種問(wèn)題以及解題思路稠肘。

一旦充分學(xué)習(xí)了這些問(wèn)題，你應(yīng)該有足夠的信心參加任何電話(huà)面試或者線(xiàn)下面試萝毛。

順便說(shuō)一下项阴，如果你沒(méi)有認(rèn)真學(xué)習(xí)過(guò)基本的數(shù)據(jù)結(jié)構(gòu)和算法，或者你沒(méi)有多年觸及它們笆包，那么還是建議你先去補(bǔ)充一下基礎(chǔ)知識(shí)环揽，再來(lái)研究本文的問(wèn)題。

Top 50 算法和編程面試問(wèn)題

話(huà)不多說(shuō)庵佣，這里列出我在研發(fā)工作以及面試中一些最常見(jiàn)的算法面試問(wèn)題列表：

1. 數(shù)組類(lèi)面試問(wèn)題

數(shù)組是最基本的數(shù)據(jù)結(jié)構(gòu)歉胶，它將元素存儲(chǔ)在連續(xù)的內(nèi)存位置。這也是面試官很喜歡面試的方向巴粪，你會(huì)在任何算法面試中聽(tīng)到很多關(guān)于數(shù)組的問(wèn)題通今，例如：反轉(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ù)組類(lèi)的算法問(wèn)題的關(guān)鍵是要充分了解數(shù)組數(shù)據(jù)結(jié)構(gòu)以及基本的編程技能一也，例如循環(huán)、遞歸等喉脖。

以下列出非常受歡迎的基于數(shù)組類(lèi)的算法面試問(wèn)題供你練習(xí)：

1. 如何在一個(gè)給定的椰苟，范圍是 1 到 100 的亂序整數(shù)數(shù)組中找到缺失的值？solution
2. 如何在一個(gè)給定的整數(shù)數(shù)組中找到重復(fù)的數(shù)字树叽？solution
3. 如何在一個(gè)亂序的整數(shù)數(shù)組中找到最大值與最小值舆蝴？solution
4. 如何找到所有的整數(shù)對(duì)，其總和等于給定的數(shù)字题诵？solution
5. 如何在包含多個(gè)重復(fù)項(xiàng)的數(shù)組中找到重復(fù)的數(shù)字洁仗？solution
6. 如何用 Java 語(yǔ)言在一個(gè)給定的數(shù)組中移除重復(fù)項(xiàng)？solution
7. 請(qǐng)利用快速排序?qū)σ粋€(gè)數(shù)組進(jìn)行原地排序性锭。solution
8. 如何用 Java 在原地反轉(zhuǎn)一個(gè)數(shù)組赠潦？solution
9. 請(qǐng)了解數(shù)組問(wèn)題中的對(duì)撞指針和滑動(dòng)窗口技巧

這些問(wèn)題不僅能夠幫助你提高解決問(wèn)題的能力，還能更好的幫助你理解數(shù)組這個(gè)數(shù)據(jù)結(jié)構(gòu)草冈。如果你覺(jué)得這幾道題不夠聯(lián)系她奥，則可以查看 30 array question瓮增，也可以在 Leetcode或者Lintcode上的數(shù)組標(biāo)簽下找題目。

2. 鏈表類(lèi)面試題

鏈表是另一種非常常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)哩俭。與數(shù)組結(jié)構(gòu)類(lèi)似绷跑，鏈表也是線(xiàn)性數(shù)據(jù)結(jié)構(gòu)并且以線(xiàn)性的方式存儲(chǔ)。

然而凡资，和數(shù)組數(shù)據(jù)結(jié)構(gòu)不同的是砸捏，在內(nèi)存物理位置上數(shù)據(jù)元素并不是相鄰的，相反讳苦，數(shù)據(jù)是分散存儲(chǔ)在內(nèi)存中带膜，通過(guò)節(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í)間來(lái)查找元素蝗肪。

鏈表還有其他的變種，例如雙向鏈表蠕趁，允許在鏈表上兩個(gè)方向（向前或向后）游走薛闪；還有循環(huán)鏈表，鏈表的首尾相連組合成一個(gè)圈俺陋。

為了解決基于鏈表的問(wèn)題豁延，需要對(duì)遞歸很了解，因?yàn)殒湵硎?a target="_blank" rel="nofollow">遞歸數(shù)據(jù)結(jié)構(gòu)腊状。如果從鏈表中獲取一個(gè)節(jié)點(diǎn)诱咏，則剩余的數(shù)據(jù)結(jié)構(gòu)仍然是鏈表，因此缴挖，許多鏈表問(wèn)題具有比迭代解決方案更簡(jiǎn)單的遞歸解決方案袋狞。

以下列出一些常見(jiàn)的受歡迎的鏈表的面試問(wèn)題：

1. 如何遍歷一次就找到鏈表的中間節(jié)點(diǎn)？solution
2. 如何判斷一個(gè)鏈表是否有環(huán)映屋？如何找到這個(gè)環(huán)的起始節(jié)點(diǎn)苟鸯？solution
3. 如何反轉(zhuǎn)一個(gè)鏈表？solution
4. 如何不使用遞歸的情況下反轉(zhuǎn)鏈表棚点？solution
5. 如何從未排序的鏈表中移除重復(fù)節(jié)點(diǎn)早处？solution
6. 請(qǐng)求出一個(gè)單鏈表的長(zhǎng)度。solution
7. 如何找出單鏈表的倒數(shù)第三個(gè)節(jié)點(diǎn)乙濒？solution
8. 請(qǐng)對(duì)兩個(gè)鏈表表示的整數(shù)求和陕赃，并返回鏈表卵蛉。solution

這些問(wèn)題將幫助您提高解決問(wèn)題的能力，并提高您對(duì)鏈表數(shù)據(jù)結(jié)構(gòu)的了解么库。如果對(duì)于以上這些問(wèn)題感覺(jué)比較吃力傻丝，建議先補(bǔ)充鏈表的基礎(chǔ)知識(shí)。你也可以聯(lián)系30 linked list interview questions

3. 字符串類(lèi)面試問(wèn)題

與數(shù)組和鏈表數(shù)據(jù)結(jié)構(gòu)同樣诉儒，字符串類(lèi)型是面試中的另一個(gè)熱門(mén)話(huà)題葡缰。關(guān)于字符串問(wèn)題的好消息是，如果你懂?dāng)?shù)組忱反，你可以很容易地解決基于字符串的問(wèn)題泛释，因?yàn)樽址皇且粋€(gè)字符數(shù)組。

所以所有你的基于數(shù)組類(lèi)問(wèn)題的解題思路與技巧都可以用來(lái)解決字符串類(lèi)型的問(wèn)題温算。

以下是我列出的在工作面試中會(huì)被頻繁問(wèn)及的字符串類(lèi)型問(wèn)題：

1. 如何將字符串中重復(fù)的字符打印出來(lái)怜校？solution
2. 如何判斷兩個(gè)亂序的字符串中的字母都相同？solution
3. 請(qǐng)將字符串中第一個(gè)未重復(fù)的字符打印出來(lái)注竿。solution
4. 如何利用遞歸翻轉(zhuǎn)一個(gè)字符串茄茁？solution
5. 如何判斷一個(gè)字符串中只包含數(shù)字字符？solution
6. 請(qǐng)統(tǒng)計(jì)一個(gè)字符串中的元音和輔音的個(gè)數(shù)巩割。solution
7. 如何計(jì)算字符串中給定字符的出現(xiàn)次數(shù)裙顽？solution
8. 請(qǐng)輸出給定字符串的所有排列組合。solution
9. 如何翻轉(zhuǎn)給定句子中的單詞宣谈？solution
10. 如何判斷兩個(gè)字符串互為旋轉(zhuǎn)愈犹？solution
11. 如何判斷一個(gè)字符是回文字符？solution

這些問(wèn)題有助于提高您對(duì)字符串作為數(shù)據(jù)結(jié)構(gòu)的了解闻丑。 如果你可以在沒(méi)有任何幫助的情況下解決所有這些String問(wèn)題漩怎，那么你很棒棒。

如果你需要更多的練習(xí)梆掸，可以看這里

4. 二叉樹(shù)面試問(wèn)題

到目前為止扬卷，我們只研究了線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，但現(xiàn)實(shí)世界中的所有信息都無(wú)法以線(xiàn)性方式表示酸钦，而這正是樹(shù)數(shù)據(jù)結(jié)構(gòu)所幫助的地方怪得。

樹(shù)數(shù)據(jù)結(jié)構(gòu)是一種數(shù)據(jù)結(jié)構(gòu)，允許以分層方式存儲(chǔ)數(shù)據(jù)卑硫。 根據(jù)存儲(chǔ)數(shù)據(jù)的方式徒恋，有不同類(lèi)型的樹(shù)，例如二叉樹(shù)欢伏，其每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)入挣。以及其近親，二叉搜索樹(shù)硝拧，這個(gè)是最受歡迎的樹(shù)形數(shù)據(jù)結(jié)構(gòu)了径筏。因此你會(huì)發(fā)現(xiàn)有很多的面試問(wèn)題都是基于二叉樹(shù)和二叉搜索樹(shù)葛假，例如 如何遍歷，計(jì)算節(jié)點(diǎn)個(gè)數(shù)滋恬，找到樹(shù)深度或者判斷其是否為平衡樹(shù)等聊训。

解決二叉樹(shù)問(wèn)題的一個(gè)關(guān)鍵點(diǎn)是需要很扎實(shí)的理論基礎(chǔ)，例如： 什么是二叉樹(shù)的大小或深度恢氯，什么是葉子带斑，什么是節(jié)點(diǎn)，以及對(duì)流行的遍歷算法的理解勋拟，例如前中后序遍歷勋磕。

以下是流行的基于二叉樹(shù)的面試問(wèn)題列表：

1. 如何實(shí)現(xiàn)二叉搜索樹(shù)？solution
2. 請(qǐng)前序遍歷一顆二叉樹(shù)敢靡。solution
3. 請(qǐng)不使用遞歸的情況下前序遍歷一顆二叉樹(shù)挂滓。solution
4. 請(qǐng)中序遍歷一顆二叉樹(shù)。solution
5. 請(qǐng)?jiān)诓皇褂眠f歸的情況下中序遍歷一顆二叉樹(shù)并輸出啸胧。solution
6. 如何實(shí)現(xiàn)后序遍歷算法杂彭？solution
7. 請(qǐng)?jiān)诓皇褂眠f歸的情況下后序遍歷一顆二叉樹(shù)。solution
8. 如何輸出一顆二叉搜索樹(shù)的所有葉子結(jié)點(diǎn)吓揪？solution
9. 如何統(tǒng)計(jì)一顆二叉樹(shù)的所有葉子節(jié)點(diǎn)的個(gè)數(shù)。solution
10. 如何在一個(gè)數(shù)組中執(zhí)行二分搜索所计。solution

5. 各式面試問(wèn)題

除了基于數(shù)據(jù)結(jié)構(gòu)的問(wèn)題之外柠辞，大多數(shù)面試中還會(huì)詢(xún)問(wèn)算法，設(shè)計(jì)主胧，位操作和基于邏輯的一般問(wèn)題叭首，我將在本節(jié)中對(duì)其進(jìn)行描述。

1. 如何實(shí)現(xiàn)冒泡排序踪栋？solution
2. 如何實(shí)現(xiàn)迭代快速排序算法焙格？solution
3. 如何實(shí)現(xiàn)插入排序算法？solution
4. 如何實(shí)現(xiàn)歸并排序算法夷都？solution
5. 如何實(shí)現(xiàn)桶排序算法眷唉？solution
6. 如何實(shí)現(xiàn)計(jì)數(shù)排序算法？solution
7. 如何實(shí)現(xiàn)基數(shù)排序算法囤官？solution
8. 如何在不使用第三個(gè)變量的情況下交換兩個(gè)數(shù)字冬阳？solution
9. 如何判斷兩個(gè)矩形是否互相重疊？solution
10. 如何設(shè)計(jì)自動(dòng)售貨機(jī)党饮？solution

順便說(shuō)一下肝陪，你在實(shí)踐中解決的問(wèn)題越多，你的準(zhǔn)備就越好刑顺。 因此氯窍，如果您認(rèn)為 50 還不夠而且您需要更多饲常，那么請(qǐng)查看這些額外的50個(gè)編程問(wèn)題，以便進(jìn)行更全面的準(zhǔn)備狼讨。

現(xiàn)在贝淤，你應(yīng)該準(zhǔn)備好了

這些是數(shù)據(jù)結(jié)構(gòu)和算法之外的一些最常見(jiàn)的問(wèn)題，可以幫助您在面試中做得很好熊楼。這些常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)和算法問(wèn)題是您在任何級(jí)別的技術(shù)面試都需要了解的問(wèn)題霹娄。

如果您正在尋找開(kāi)發(fā)工作，您可以使用此這些問(wèn)題列表開(kāi)始準(zhǔn)備鲫骗。此列表提供了準(zhǔn)備的好主題犬耻，也有助于評(píng)估您的準(zhǔn)備工作，以找出您的優(yōu)勢(shì)和劣勢(shì)領(lǐng)域执泰。熟悉數(shù)據(jù)結(jié)構(gòu)和算法對(duì)于面試成功非常重要枕磁。

譯者：歡迎大家訪(fǎng)問(wèn)我的個(gè)人博客與留言 http://pengtuo.tech