Scala程序員面試算法寶典

前言

面試、筆試經(jīng)驗(yàn)技巧篇
經(jīng)驗(yàn)技巧1 如何巧妙地回答面試官的問題2
經(jīng)驗(yàn)技巧2 如何回答技術(shù)性的問題3
經(jīng)驗(yàn)技巧3 如何回答非技術(shù)性問題4
經(jīng)驗(yàn)技巧4 如何回答快速估算類問題5
經(jīng)驗(yàn)技巧5 如何回答算法設(shè)計(jì)問題6
經(jīng)驗(yàn)技巧6 如何回答系統(tǒng)設(shè)計(jì)題8
經(jīng)驗(yàn)技巧7 如何解決求職中的時(shí)間沖突問題11
經(jīng)驗(yàn)技巧8 如果面試問題曾經(jīng)遇見過，是否要告知面試官12
經(jīng)驗(yàn)技巧9 在被企業(yè)拒絕后是否可以再申請(qǐng)12
經(jīng)驗(yàn)技巧10 如何應(yīng)對(duì)自己不會(huì)回答的問題13
經(jīng)驗(yàn)技巧11 如何應(yīng)對(duì)面試官的“激將法”語言13
經(jīng)驗(yàn)技巧12 如何處理與面試官持不同觀點(diǎn)問題14
經(jīng)驗(yàn)技巧13 什么是職場(chǎng)暗語14
面試、筆試真題解析篇
第1章 鏈表19
1.1 如何實(shí)現(xiàn)鏈表的逆序20
1.2 如何從無序鏈表中移除重復(fù)項(xiàng)24
1.3 如何計(jì)算兩個(gè)單鏈表所代表的數(shù)之和27
1.4 如何對(duì)鏈表進(jìn)行重新排序30
1.5 如何找出單鏈表中的倒數(shù)第k個(gè)元素32
1.6 如何檢測(cè)一個(gè)較大的單鏈表是否有環(huán)36
1.7 如何把鏈表相鄰元素反轉(zhuǎn)38
1.8 如何把鏈表以k個(gè)結(jié)點(diǎn)為一組進(jìn)行反轉(zhuǎn)40
1.9 如何合并兩個(gè)有序鏈表43
1.10 如何在只給定單鏈表中某個(gè)結(jié)點(diǎn)的指針的情況下刪除該結(jié)點(diǎn)（不包括尾結(jié)點(diǎn)）45
1.11 如何判斷兩個(gè)單鏈表（無環(huán)）是否交叉47
1.12 如何展開鏈接列表50
第2章 棧與隊(duì)列53
2.1 如何實(shí)現(xiàn)棧53
2.2 如何實(shí)現(xiàn)隊(duì)列57
2.3 如何反轉(zhuǎn)棧的所有元素60
2.4 如何根據(jù)入棧序列判斷可能的出棧序列64
2.5 如何用O(1)的時(shí)間復(fù)雜度求棧中最小元素65
2.6 如何用兩個(gè)棧模擬隊(duì)列操作67
2.7 如何設(shè)計(jì)一個(gè)排隊(duì)系統(tǒng)68
2.8 如何實(shí)現(xiàn)LRU緩存方案70
2.9 如何從給定的車票中找出旅程71
2.10 如何從數(shù)組中找出滿足a+b=c+d的兩個(gè)數(shù)對(duì)73
第3章 二叉樹75
3.1 二叉樹基礎(chǔ)知識(shí)75
3.2 如何把一個(gè)有序的整數(shù)數(shù)組放到二叉樹中77
3.3 如何從頂部開始逐層打印二叉樹結(jié)點(diǎn)數(shù)據(jù)78
3.4 如何求一棵二叉樹的最大子樹和80
3.5 如何判斷兩棵二叉樹是否相等82
3.6 如何把二叉樹轉(zhuǎn)換為雙向鏈表83
3.7 如何判斷一個(gè)數(shù)組是否是二元查找樹后序遍歷的序列85
3.8 如何找出排序二叉樹上任意兩個(gè)結(jié)點(diǎn)的最近共同父結(jié)點(diǎn)87
3.9 如何復(fù)制二叉樹92
3.10 如何在二叉樹中找出與輸入整數(shù)相等的所有路徑93
3.11 如何對(duì)二叉樹進(jìn)行鏡像反轉(zhuǎn)95
3.12 如何在二叉排序樹中找出第一個(gè)大于且數(shù)值最接近中間值的結(jié)點(diǎn)96
3.13 如何在二叉樹中找出路徑最大的和98
3.14 如何實(shí)現(xiàn)反向DNS查找域名99
第4章 數(shù)組102
4.1 如何找出數(shù)組中唯一的重復(fù)元素102
4.2 如何查找數(shù)組中元素的最大值和最小值107
4.3 如何找出旋轉(zhuǎn)數(shù)組的最小元素110
4.4 如何找出數(shù)組中丟失的數(shù)113
4.5 如何找出數(shù)組中出現(xiàn)奇數(shù)次的數(shù)115
4.6 如何找出數(shù)組中第k小的數(shù)117
4.7 如何求數(shù)組中兩個(gè)元素的最小距離120
4.8 如何求解最小三元組距離122
4.9 如何求數(shù)組中絕對(duì)值最小的數(shù)126
4.10 如何求數(shù)組連續(xù)最大和129
4.11 如何找出數(shù)組中出現(xiàn)一次的數(shù)132
4.12 如何旋轉(zhuǎn)數(shù)組134
4.13 如何在不排序的情況下求數(shù)組中的中位數(shù)135
4.14 如何求集合的所有子集137
4.15 如何對(duì)數(shù)組進(jìn)行循環(huán)移位140
4.16 如何在有規(guī)律的二維數(shù)組中進(jìn)行高效的數(shù)據(jù)查找142
4.17 如何尋找最多的覆蓋點(diǎn)144
4.18 如何判斷請(qǐng)求能否在給定的存儲(chǔ)條件下完成145
4.19 如何按要求構(gòu)造新的數(shù)組147
4.20 如何獲取最好的矩陣鏈相乘方法148
4.21 如何求解迷宮問題150
4.22 如何從三個(gè)有序數(shù)組中找出它們的公共元素152
4.23 如何求兩個(gè)有序集合的交集153
4.24 如何對(duì)有大量重復(fù)的數(shù)字的數(shù)組排序156
4.25 如何對(duì)任務(wù)進(jìn)行調(diào)度159
4.26 如何對(duì)磁盤分區(qū)160
第5章 字符串162
5.1 如何求一個(gè)字符串的所有排列162
5.2 如何求兩個(gè)字符串的最長(zhǎng)公共子串166
5.3　如何對(duì)字符串進(jìn)行反轉(zhuǎn)169
5.4 如何判斷兩個(gè)字符串是否為換位字符串171
5.5　如何判斷兩個(gè)字符串是否具有包含關(guān)系173
5.6　如何對(duì)由大小寫字母組成的字符數(shù)組排序175
5.7　如何消除字符串的內(nèi)嵌括號(hào)176
5.8　如何判斷字符串是否是整數(shù)177
5.9　如何實(shí)現(xiàn)字符串的匹配180
5.10　如何求字符串里的最長(zhǎng)回文子串183
5.11　如何按照給定的字母序列對(duì)字符數(shù)組排序189
5.12　如何判斷一個(gè)字符串是否包含重復(fù)字符191
5.13　如何找到由其他單詞組成的最長(zhǎng)單詞193
5.14　如何統(tǒng)計(jì)字符串中連續(xù)重復(fù)字符個(gè)數(shù)195
5.15　如何求最長(zhǎng)遞增子序列的長(zhǎng)度196
5.16　如何求一個(gè)串中出現(xiàn)的第一個(gè)最長(zhǎng)重復(fù)子串197
5.17　如何求解字符串中字典序最大的子序列199
5.18　如何判斷一個(gè)字符串是否由另外一個(gè)字符串旋轉(zhuǎn)得到202
5.19　如何求字符串的編輯距離203
5.20　如何在二維數(shù)組中尋找最短路線205
5.21 如何截取包含中文的字符串207
5.22　如何求相對(duì)路徑209
5.23　如何查找到達(dá)目標(biāo)詞的最短鏈長(zhǎng)度210
第6章　基本數(shù)字運(yùn)算213
6.1　如何判斷一個(gè)自然數(shù)是否是某個(gè)數(shù)的二次方213
6.2　如何判斷一個(gè)數(shù)是否為2的n次方215
6.3　如何不使用除法操作符實(shí)現(xiàn)兩個(gè)正整數(shù)的除法216
6.4　如何只使用++操作符實(shí)現(xiàn)加減乘除運(yùn)算220
6.5　如何根據(jù)已知隨機(jī)數(shù)生成函數(shù)計(jì)算新的隨機(jī)數(shù)222
6.6　如何判斷1024!末尾有多少個(gè)0224
6.7　如何按要求比較兩個(gè)數(shù)的大小225
6.8　如何求有序數(shù)列的第1500個(gè)數(shù)的值226
6.9　如何把十進(jìn)制數(shù)（long型）分別以二進(jìn)制和十六進(jìn)制形式輸出227
6.10　如何求二進(jìn)制數(shù)中1的個(gè)數(shù)228
6.11　如何找最小的不重復(fù)數(shù)230
6.12　如何計(jì)算一個(gè)數(shù)的n次方233
6.13　如何在不能使用庫函數(shù)的條件下計(jì)算正數(shù)n的算術(shù)平方根235
6.14　如何不使用^操作實(shí)現(xiàn)異或運(yùn)算235
6.15　如何不使用循環(huán)輸出1～100237
第7章　排列組合與概率238
7.1　如何求數(shù)字的組合238
7.2　如何拿到最多金幣240
7.3　如何求正整數(shù)n所有可能的整數(shù)組合241
7.4　如何用一個(gè)隨機(jī)函數(shù)得到另外一個(gè)隨機(jī)函數(shù)243
7.5　如何等概率地從大小為n的數(shù)組中選取m個(gè)整數(shù)244
7.6　如何計(jì)算1、2、5這三個(gè)數(shù)使其和為100的組合個(gè)數(shù)245
7.7　如何判斷還有幾盞燈泡亮著246
第8章　 大數(shù)據(jù)249
8.1　如何從大量的url中找出相同的url249
8.2　如何從大量數(shù)據(jù)中找出高頻詞250
8.3　如何找出某一天訪問百度網(wǎng)站最多的IP251
8.4　如何在大量的數(shù)據(jù)中找出不重復(fù)的整數(shù)251
8.5　如何在大量的數(shù)據(jù)中判斷一個(gè)數(shù)是否存在252
8.6　如何查詢最熱門的查詢串253
8.7　如何統(tǒng)計(jì)不同電話號(hào)碼的個(gè)數(shù)254
8.8　如何從5億個(gè)數(shù)中找出中位數(shù)255
8.9　如何按照query的頻度排序256
8.10　如何找出排名前500的數(shù)257