本書是一本講解程序員面試筆試算法的書,代碼采用Python語言編寫,書中除了講解如何解答算法問題以外,還引入了例子輔以說明,讓讀者更容易理解。
本書幾乎將程序員面試筆試過程中算法類真題一網(wǎng)打盡,在題目的廣度上,通過各種渠道,搜集了近3年來幾乎所有IT企業(yè)面試筆試算法的高頻題目,所選擇題目均為企業(yè)招聘使用題目。在題目的深度上,本書由淺入深,庖丁解牛式地分析每一個題目,并提煉歸納。同時,引入例子與源代碼、時間復(fù)雜度與空間復(fù)雜度的分析,這些內(nèi)容是其他同類書籍所沒有的。本書根據(jù)真題所屬知識點進(jìn)行分門別類,結(jié)構(gòu)合理,條理清晰,對于讀者進(jìn)行學(xué)習(xí)與檢索意義重大。
本書可作為計算機相關(guān)專業(yè)畢業(yè)生面試筆試的求職用書,也可以作為本科生、研究生學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的輔導(dǎo)書籍,同時適合期望在計算機軟硬件行業(yè)大顯身手的計算機愛好者閱讀。
在這里,有面試筆試常見技巧的提煉與總結(jié);
在這里,有面試筆試高頻算法知識點的整理與剖析;
在這里,有面試筆試歷年算法真題的解答與拓展。
計算機技術(shù)博大精深、日新月異,Hadoop、GPU計算、移動互聯(lián)網(wǎng)、模式匹配、圖像識別、神經(jīng)網(wǎng)絡(luò)、蟻群算法、大數(shù)據(jù)、機器學(xué)習(xí)、人工智能、深度學(xué)習(xí)等新技術(shù)讓人眼花繚亂,稍有不慎,就會被時代所拋棄。于是,很多IT從業(yè)者就開始困惑了,不知道從何學(xué)起,到底什么才是計算機技術(shù)的基石。其實,究其本質(zhì)與基礎(chǔ),還是最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)與算法知識:Hash、動態(tài)規(guī)劃、分治、排序、查找等。所以,無論是世界級的大型企業(yè),還是幾個人的小公司,在面試求職者的時候,往往會考察這些最基礎(chǔ)的知識,無論你的研究方向是什么,這些基礎(chǔ)知識還是應(yīng)該熟練掌握的。
本書在寫作風(fēng)格上,推陳出新,對于算法的講解,不僅有文字描述,更以示例佐證,能夠更好地讓讀者讀懂。為了能夠?qū)懗鼍窌,我們對每一個技術(shù)問題都反復(fù)推敲,與算法大牛一起反復(fù)論證可行性,對于文字,我們咬文嚼字,字斟句酌,所有這些付出,只為讓讀者能夠?qū)械募夹g(shù)點放心,文字描述舒心。
市面上同類型書籍很多,也都寫得不錯,但是,我們相信,我們能夠?qū)懗龈m合讀者需求的高質(zhì)量精品書籍。為了能夠在有限的篇幅里面盡可能地羅列出干貨,我們在選擇題目上也是下了巨大的功夫:首先,我們通過搜集近3年以來幾乎所有IT企業(yè)的面試筆試算法真題,包括已經(jīng)出版的其他著作、技術(shù)博客、在線編碼平臺、刷題網(wǎng)站等,保證所選樣本足夠大。其次,我們選擇題目的時候盡可能不選擇那種一眼就能知道結(jié)果的簡單題,也不選擇那種怪題、偏題、難題,我們的選題原則是選擇難度適中或者看上去簡單但實際容易出錯的題目。通過我們的努力,力求遴選出來的算法真題能夠最大限度地幫助讀者。在真題的解析上,我們采用層層遞進(jìn)的方法,先易后難,層層深入,將問題抽絲剝繭,使得讀者能夠跟隨我們的思路,一步步找到問題的最優(yōu)解。
寫作的過程是一個自我提高、自我認(rèn)識的過程,很多知識,只有你深入理解與剖析后,才能領(lǐng)悟其中的精髓,掌握其中的技巧,程序員求職算法也不例外。本書不僅具備了其他書籍分析透徹、代碼清晰合理等優(yōu)點,還具備以下幾個方面的優(yōu)勢:
第一,算法書籍分多種語言版本實現(xiàn):C/C 、Java、C#、Python等,這樣,不管讀者側(cè)重于哪一種語言,都能夠有適合自己的書。后續(xù)可能還有PHP等其他語言描述的圖書出現(xiàn)。本書中如果沒有特別強調(diào),代碼實現(xiàn)均默認(rèn)使用Python語言。
第二,每個題目除了循序漸進(jìn)的分析以外,還對方法進(jìn)行了詳細(xì)闡述,針對不同方法的時間復(fù)雜度與空間復(fù)雜度,進(jìn)行了詳細(xì)的分析。除此之外,為了更具說服力,每一種方法幾乎都對應(yīng)有示例講解,對方法是一種更好的輔助。
第三,代碼較為規(guī)范,完全參照華為編程規(guī)范、Google編程規(guī)范規(guī)范編碼。小作坊編碼的時代早已過去,程序員要想在一個團(tuán)隊中大展拳腳,就離不開合作,而合作的基礎(chǔ)就是共同遵循統(tǒng)一的編碼規(guī)范。不僅如此,規(guī)范化的編碼往往有助于讀者理解代碼。
第四,除了題目講解,還有部分觸類旁通的題目供讀者練習(xí)。本書不可能囊括所有的程序員求職類的數(shù)據(jù)結(jié)構(gòu)與算法類題目,但是,本書會盡可能地將一些常見的求職類算法題和具有代表性的算法題重點講解,將其他一些題目以練習(xí)題的形式展現(xiàn)在讀者面前,供讀者思考與學(xué)習(xí)。
我是一個很樂觀的人,人生在世,就是在發(fā)現(xiàn)問題,解決問題中度過,我總能夠以最飽滿的精神狀態(tài)完成創(chuàng)作。在此,感謝我的父母、姐姐、親朋好友一直以來對我的關(guān)心與照顧,感謝我的大學(xué)老師劉堅教授、張立勇副教授、王獻(xiàn)青副教授、霍秋艷副教授等對我的無私的知識傳授,將我?guī)нM(jìn)了計算機的殿堂,在我對學(xué)習(xí)感到困惑的時候,點亮我人生的燈塔。感謝同學(xué)與師兄弟們的兄弟情義,感謝同事們工作的支持以及業(yè)余一起打籃球、踢足球、談人生、談理想。感謝那些對我生活、工作給予巨大關(guān)心的人,是你們一路陪伴,讓我孤獨的心充滿溫暖與愛。正是有了你們,我的生活才更加豐富多彩。每每想到這些,我都對生活充滿了無限的期待。
數(shù)據(jù)結(jié)構(gòu)與算法知識博大精深,非一本或是幾本書就能夠?qū)⑵渲v解透徹,但不能因為這樣就不去做這件事了。盡管本書竭盡所能希望將所有程序員求職過程中出現(xiàn)的面試筆試題一網(wǎng)打盡,試圖做到知識覆蓋面廣,內(nèi)容知識全,但仍然無法做到面面俱到,百分之百的讀者滿意率是本書以及后續(xù)改版奮斗與追求的目標(biāo),希望讀者能夠體諒。有興趣的讀者可以閱讀《算法導(dǎo)論》《編程珠璣》等國外知名專家編寫的專著進(jìn)行知識的擴展與延伸。
其實,本書不僅可以作為程序員求職的應(yīng)試類書籍,還可以作為數(shù)據(jù)結(jié)構(gòu)與算法的教輔書籍。書中的很多思想、方法對于提高對數(shù)據(jù)結(jié)構(gòu)與算法的理解是大有裨益的,不管你是本科生還是研究生,不管你是低年級學(xué)生還是高年級學(xué)生,不管你對計算機底層知識還是當(dāng)前的計算機前沿知識是否了解,都不影響你學(xué)好本書。
本書是作者歷經(jīng)四年時間打造的技術(shù)精品,盡管我們用盡心思、絞盡腦汁地希望做到百分之百的準(zhǔn)確性,但書中不足之處在所難免,在懇請讀者原諒的同時,也希望讀者能夠?qū)⑦@些問題反饋到我們這里,以便于未來繼續(xù)改進(jìn)與提高,為讀者提供更加優(yōu)秀的作品。
本書中有部分思想來源于網(wǎng)絡(luò),無法追蹤到出處,在此對這些幕后英雄致以最崇高的敬意。沒有學(xué)不好的學(xué)生,只有教不好的老師,我們希望無論是什么層次的學(xué)生,都能毫無障礙地看懂書中所講內(nèi)容。如果讀者存在求職困惑或是對本書中的內(nèi)容存在異議,都可以通過yuancoder@foxmail.com聯(lián)系作者。
猿媛之家
于西安
前言
面試筆試經(jīng)驗技巧篇
經(jīng)驗技巧1 如何巧妙地回答面試官的問題2
經(jīng)驗技巧2 如何回答技術(shù)性的問題3
經(jīng)驗技巧3 如何回答非技術(shù)性問題4
經(jīng)驗技巧4 如何回答快速估算類問題5
經(jīng)驗技巧5 如何回答算法設(shè)計問題6
經(jīng)驗技巧6 如何回答系統(tǒng)設(shè)計題9
經(jīng)驗技巧7 如何解決求職中的時間沖突問題11
經(jīng)驗技巧8 如果面試問題曾經(jīng)遇見過,是否要告知面試官12
經(jīng)驗技巧9 被企業(yè)拒絕后是否可以再申請12
經(jīng)驗技巧10 如何應(yīng)對自己不會回答的問題13
經(jīng)驗技巧11 如何應(yīng)對面試官的激將法語言14
經(jīng)驗技巧12 如何處理與面試官持不同觀點這個問題15
經(jīng)驗技巧13 關(guān)注職場暗語15
面試筆試真題解析篇
第1章 鏈表21
1.1 如何實現(xiàn)鏈表的逆序22
1.2 如何從無序鏈表中移除重復(fù)項26
1.3 如何計算兩個單鏈表所代表的數(shù)之和29
1.4 如何對鏈表進(jìn)行重新排序32
1.5 如何找出單鏈表中的倒數(shù)第k個元素35
1.6 如何檢測一個較大的單鏈表是否有環(huán)39
1.7 如何把鏈表相鄰元素翻轉(zhuǎn)41
1.8 如何把鏈表以K個結(jié)點為一組進(jìn)行翻轉(zhuǎn)43
1.9 如何合并兩個有序鏈表46
1.10 如何在只給定單鏈表中某個結(jié)點的指針的情況下刪除該結(jié)點49
1.11 如何判斷兩個單鏈表(無環(huán))是否交叉51
1.12 如何展開鏈接列表54
第2章 棧、隊列與哈希57
2.1 如何實現(xiàn)棧57
2.2 如何實現(xiàn)隊列60
2.3 如何翻轉(zhuǎn)棧的所有元素64
2.4 如何根據(jù)入棧序列判斷可能的出棧序列68
2.5 如何用O(1)的時間復(fù)雜度求棧中最小元素71
2.6 如何用兩個棧模擬隊列操作73
2.7 如何設(shè)計一個排序系統(tǒng)74
2.8 如何實現(xiàn)LRU緩存方案76
2.9 如何從給定的車票中找出旅程77
2.10 如何從數(shù)組中找出滿足a b=c d的兩個數(shù)對79
第3章 二叉樹81
3.1 二叉樹基礎(chǔ)知識81
3.2 如何把一個有序整數(shù)數(shù)組放到二叉樹中83
3.3 如何從頂部開始逐層打印二叉樹結(jié)點數(shù)據(jù)84
3.4 如何求一棵二叉樹的最大子樹和87
3.5 如何判斷兩棵二叉樹是否相等89
3.6 如何把二叉樹轉(zhuǎn)換為雙向鏈表90
3.7 如何判斷一個數(shù)組是否是二元查找樹后序遍歷的序列93
3.8 如何找出排序二叉樹上任意兩個結(jié)點的最近共同父結(jié)點94
3.9 如何復(fù)制二叉樹101
3.10 如何在二叉樹中找出與輸入整數(shù)相等的所有路徑102
3.11 如何對二叉樹進(jìn)行鏡像反轉(zhuǎn)104
3.12 如何在二叉排序樹中找出第一個大于中間值的結(jié)點106
3.13 如何在二叉樹中找出路徑最大的和107
3.14 如何實現(xiàn)反向DNS查找緩存109
第4章 數(shù)組112
4.1 如何找出數(shù)組中唯一的重復(fù)元素112
4.2 如何查找數(shù)組中元素的最大值和最小值118
4.3 如何找出旋轉(zhuǎn)數(shù)組的最小元素121
4.4 如何找出數(shù)組中丟失的數(shù)124
4.5 如何找出數(shù)組中出現(xiàn)奇數(shù)次的數(shù)126
4.6 如何找出數(shù)組中第k小的數(shù)128
4.7 如何求數(shù)組中兩個元素的最小距離131
4.8 如何求解最小三元組距離134
4.9 如何求數(shù)組中絕對值最小的數(shù)138
4.10 如何求數(shù)組連續(xù)最大和141
4.11 如何找出數(shù)組中出現(xiàn)1次的數(shù)145
4.12 如何對數(shù)組旋轉(zhuǎn)147
4.13 如何在不排序的情況下求數(shù)組中的中位數(shù)148
4.14 如何求集合的所有子集150
4.15 如何對數(shù)組進(jìn)行循環(huán)移位152
4.16 如何在有規(guī)律的二維數(shù)組中進(jìn)行高效的數(shù)據(jù)查找155
4.17 如何尋找最多的覆蓋點157
4.18 如何判斷請求能否在給定的存儲條件下完成158
4.19 如何按要求構(gòu)造新的數(shù)組160
4.20 如何獲取最好的矩陣鏈相乘方法161
4.21 如何求解迷宮問題163
4.22 如何從三個有序數(shù)組中找出它們的公共元素165
4.23 如何求兩個有序集合的交集167
4.24 如何對有大量重復(fù)的數(shù)字的數(shù)組排序171
4.25 如何對任務(wù)進(jìn)行調(diào)度174
4.26 如何對磁盤分區(qū)176
第5章 字符串178
5.1 如何求一個字符串的所有排列178
5.2 如何求兩個字符串的最長公共子串183
5.3 如何對字符串進(jìn)行反轉(zhuǎn)187
5.4 如何判斷兩個字符串是否為換位字符串189
5.5 如何判斷兩個字符串的包含關(guān)系191
5.6 如何對由大小寫字母組成的字符數(shù)組排序193
5.7 如何消除字符串的內(nèi)嵌括號194
5.8 如何判斷字符串是否是整數(shù)196
5.9 如何實現(xiàn)字符串的匹配199
5.10 如何求字符串里的最長回文子串202
5.11 如何按照給定的字母序列對字符數(shù)組排序208
5.12 如何判斷一個字符串是否包含重復(fù)字符210
5.13 如何找到由其他單詞組成的最長單詞212
5.14 如何統(tǒng)計字符串中連續(xù)的重復(fù)字符個數(shù)214
5.15 如何求最長遞增子序列的長度215
5.16 求一個串中出現(xiàn)的第一個最長重復(fù)子串216
5.17 如何求解字符串中字典序最大的子序列218
5.18 如何判斷一個字符串是否由另外一個字符串旋轉(zhuǎn)得到220
5.19 如何求字符串的編輯距離222
5.20 如何在二維數(shù)組中尋找最短路線224
5.21 如何截取包含中文的字符串227
5.22 如何求相對路徑228
5.23 如何查找到達(dá)目標(biāo)詞的最短鏈長度229
第6章 基本數(shù)字運算232
6.1 如何判斷一個自然數(shù)是否是某個數(shù)的平方232
6.2 如何判斷一個數(shù)是否為2的n次方234
6.3 如何不使用除法操作符實現(xiàn)兩個正整數(shù)的除法236
6.4 如何只使用 = 操作符實現(xiàn)加減乘除運算240
6.5 如何根據(jù)已知