- 相關(guān)推薦
筆試面試算法總結(jié)
筆試面試算法問(wèn)題總結(jié)
算法
1. 算法的幾個(gè)特征是什么。
2. 算法復(fù)雜性的定義。大O、θ、?、小o分別表示的含義。
3. 遞歸算法的定義、遞歸算法的兩要素。
4. 分治算法的思想，經(jīng)典的分治算法(全排列、二分搜索、歸并排序、快速排序、線性時(shí)間選擇、最接近點(diǎn)對(duì)問(wèn)題)。
5. 動(dòng)態(tài)規(guī)劃算法解題框架，動(dòng)態(tài)規(guī)劃算法的兩個(gè)要素是什么？備忘錄方法是什么？
6. 經(jīng)典的動(dòng)態(tài)規(guī)劃問(wèn)題(矩陣連乘問(wèn)題、最長(zhǎng)公共子序列問(wèn)題、0-1背包問(wèn)題)。
7. 貪心算法的思想，貪心算法的兩個(gè)要素。
8. 經(jīng)典的貪心問(wèn)題(活動(dòng)安排問(wèn)題、背包問(wèn)題、裝載問(wèn)題、哈夫曼編碼、單源最短路徑、最小生成樹(shù)問(wèn)題)。
9. 回溯法的思想，回溯法中有哪兩種典型的模型。
10. 經(jīng)典的回溯算法(n后問(wèn)題、0-1背包問(wèn)題、旅行售貨商問(wèn)題)。
11. 分支限界法思想，有哪兩種分支限界法。
12. 經(jīng)典的分支限界算法(0-1背包問(wèn)題、旅行售貨商問(wèn)題)。
數(shù)據(jù)結(jié)構(gòu)
1. 數(shù)據(jù)結(jié)構(gòu)的定義。
2. 棧的兩個(gè)應(yīng)用：括號(hào)匹配和表達(dá)式的計(jì)算。是怎么應(yīng)用的？表達(dá)式計(jì)算用的是哪種表達(dá)方式？有什么好處?
3. 字符串匹配算法：樸素的匹配算法、KMP 算法 。
4. 二叉樹(shù)前序、中序、后序遞歸遍歷算法。二叉樹(shù)前序非遞歸遍歷算法。
5. 堆 ，建堆算法，堆的插入和刪除算法，堆排序 。
6. 哈希 。哈希函數(shù)的有哪些種？余數(shù)的取法？ 處理沖突的方法？ 閉散列方法有哪些？
7. 二叉搜索樹(shù)的搜索、插入、刪除。時(shí)間復(fù)雜度。
8. 二叉平衡樹(shù)的插入結(jié)點(diǎn)的原理 ，有哪幾種旋轉(zhuǎn)方式？分別適用于哪種情況。分析二叉平衡樹(shù)的時(shí)間復(fù)雜度。
9. 紅黑樹(shù)的定義，紅黑樹(shù)的性能分析和與二叉平衡樹(shù)的比較 。
10. 圖有哪些儲(chǔ)存表示。
11. 鏈表插入排序、鏈表歸并排序。
12. 常見(jiàn)的有哪幾種排序算法，試比較其時(shí)間復(fù)雜度，以及是否穩(wěn)定，及各自使用的情形。
13. 常用分配排序有哪幾種？ 基數(shù)排序的定義，分類(lèi)及原理。
14. 外部排序的過(guò)程。
15. B樹(shù)、B+樹(shù)、Trie的概念及用途，添加刪除結(jié)點(diǎn)的原理。
面試算法總結(jié)
【一】 時(shí)間受限
大部分的面試題，都是對(duì)時(shí)間復(fù)雜度有所要求的，如果有涉及，“最快”一類(lèi)的字樣，毫無(wú)疑問(wèn)，先上時(shí)空原理，用空間來(lái)?yè)Q時(shí)間。Hash，大數(shù)組，一些輔助性的空間，都是首選。在我的面試經(jīng)歷中，有無(wú)數(shù)次用到過(guò)Hash和大數(shù)組的。不過(guò)，通常這不會(huì)是面試官想聽(tīng)的唯一解法，他們緊接著十有八-九是會(huì)說(shuō)“如果只有xx-xx空間呢？”。說(shuō)此類(lèi)方法只是為自己爭(zhēng)取更多的時(shí)間，并且體現(xiàn)思考的完整性，簡(jiǎn)而言之，裝B用。。。
eg1.1：求一個(gè)char（8bit）中，二進(jìn)制1的個(gè)數(shù)，越快越好。 -- 《編程之美》
編程之美上提供了五種方法，（1）使用除法操作 （2）使用位操作 （3）在位操作的基礎(chǔ)上改進(jìn)，算法的復(fù)雜度只于1的個(gè)數(shù)有關(guān) （4）使用分支操作 （5）查表法。
第2種方法用的是位運(yùn)算，比第一種方法高效很多。第3種方法非常有技巧。第4，5兩種方法其實(shí)是用空間換時(shí)間，但是如果是一個(gè)int（32bit），那么這兩種方法就不適用了。方法3的代碼
int Count(BYTE v) {
int num = 0;
while( v ) {
v &= ( v - 1 );
num++;
}
}
eg1.2：有一個(gè)整數(shù)數(shù)組A[N]，讓你不用除法，求另一個(gè)數(shù)組B[N]，其中B[i] = A[0]*A[1] ... * A[N-1] / A[i]，期望復(fù)雜度是O(N)。 -- TopLanguage
利用兩個(gè)輔助數(shù)組 C[N],D[N] 完成 ，其中 C[i] = A[0]*A[1]*...A[i-1]*A[i], D[i]=A[i]*A[i+1]*...A[N-2]*A[N-1]，B[i] =C[i-1] *D[i+1]
【二】 空間受限
這里的空間受限，指的是在大數(shù)據(jù)分析的邏輯下，空間受限的問(wèn)題。大部分情況下，就是壓縮。位圖是一個(gè)很好的方法，用一個(gè)bit（ 或幾個(gè)） 取代更大的int類(lèi)型，最常見(jiàn)的位圖是1bit 取代 1int，其實(shí)，很多時(shí)候，1bit可以取代更大的空間，這完全取決于你需要保留的信息。。。
eg2.1：有一個(gè)很大的文件，存放一堆7位的電話號(hào)碼，號(hào)碼無(wú)重復(fù)，請(qǐng)用最小的內(nèi)存消耗，將其排序。 -- 《編程珠璣》
利用位圖技術(shù)實(shí)現(xiàn)。每一個(gè)號(hào)碼如果用一個(gè)int存儲(chǔ)，那么需要40MB ( (10^7*4)/10^6 MB)，如果用位圖技術(shù)，則只需用1位來(lái)存放1個(gè)號(hào)碼，需要1.25MB( ( 10^7/8)/10^6 MB)
每個(gè)號(hào)碼對(duì)應(yīng)位圖的一位，位圖初始全清零，讀入一個(gè)號(hào)碼就把相應(yīng)的位置位，遍歷后按位圖順序輸出對(duì)應(yīng)的數(shù)字。
eg2.2：給10MB的內(nèi)存，給一個(gè) 4百萬(wàn) 整數(shù)的文件，找一個(gè)不在文件中的整數(shù)。
可以用10MB內(nèi)存來(lái)存放 0 到（8*10^7-1）范圍數(shù)的出現(xiàn)情況。掃描文件一遍，將該范圍中相應(yīng)的位置位，超出范圍的數(shù)簡(jiǎn)單丟棄。然后遍歷位圖，找到第一個(gè)為0的位即可，位圖中肯定有未置位的位。
擴(kuò)展1 ：給10MB的內(nèi)存，給一個(gè) 40億 整數(shù)的文件，找一個(gè)不在文件中的整數(shù)。
同樣可以用上述的方法，不過(guò)可能需要多遍掃描。因?yàn)槲募械恼麛?shù)是多于 8*10^7，第一遍掃描后，位圖的所有位都可能被置位。如果出現(xiàn)這種情況，那么用10MB內(nèi)存存放 （8*10^7）到 （16*10^7-1）范圍數(shù)的出現(xiàn)情況，再次嘗試。平均性能幾乎是掃描1次。
擴(kuò)展2 ：給10MB的內(nèi)存，給一個(gè)40億 整數(shù)的文件，找一個(gè)不在文件中的整數(shù)。只能掃描文件1遍
暫時(shí)未想到確定性的算法，這里給出一種近似的方法。隨機(jī)生成200萬(wàn)個(gè)數(shù)，然后排序。掃描文件1遍，把文件中出現(xiàn)的對(duì)應(yīng)數(shù)刪除，比如200萬(wàn)個(gè)隨機(jī)數(shù)中有5，而文件中也有5，那么把隨機(jī)數(shù)5從數(shù)組中刪除（簡(jiǎn)單置為-1即可）。最終隨機(jī)生成的200萬(wàn)個(gè)數(shù)中會(huì)剩余 (2*10^6) * ( 1 - (4*10^9)/2^32) ，取其中的任意一個(gè)即可。幾乎不會(huì)失敗。
【三】 基于文件
越來(lái)越多的大公司，開(kāi)始關(guān)系對(duì)文件的處理，上面所說(shuō)的空間受限的問(wèn)題，其實(shí)也基本都是和文件打交道�；谖募奶幚恚径际菍ふ�，或者排序，最最核心的，就是減少文件讀取的次數(shù)。除了位圖法，還可以考慮哨兵，典型的案例就是外排中，增加單個(gè)文件大小的方法。
eg3.1：給定一個(gè)包含4300000000個(gè)32位整數(shù)的順序文件，找到一個(gè)至少出現(xiàn)兩次的整數(shù)。 -- 《編程珠璣》
思路1：如果內(nèi)存不受限，用位圖技術(shù)，必有2個(gè)數(shù)會(huì)落到同一位中，其實(shí)是運(yùn)用了鴿巢原理。32位整數(shù)能表示的最大數(shù)為4294967295，小于43億。
思路2：如果內(nèi)存受限，采用二分搜索法 。 由于4.3G>32位的整數(shù)空間，根據(jù)鴿籠原理，肯定會(huì)有重復(fù)的整數(shù)。搜索范圍從所有的32位正整數(shù)開(kāi)始（全部當(dāng)成unsigned int，簡(jiǎn)化問(wèn)題），即[0,2^32)，中間值即為2^31。然后遍歷文件，如果小于2^31的整數(shù)個(gè)數(shù)大于2^31，則調(diào)整搜索范圍為[0,2^31]，反之亦然；然后再對(duì)整個(gè)文件再遍歷一遍，直到得到最后的結(jié)果。這樣一共會(huì)有l(wèi)ogn次的搜索，每次過(guò)n個(gè)整數(shù)（每次都是完全遍歷），總體的復(fù)雜度為o(nlogn)
eg3.2：有一個(gè)文件，有很多很多的整數(shù)（也許有100億），尋找其中最大的K個(gè)。 -- 《編程之美》列舉幾種解法
解法1：如果元素不是很多，用快速排序，然后遍歷找到最大的K個(gè)�？偟臅r(shí)間復(fù)雜度為 O(N logN) + O(K)
解法2：找K個(gè)數(shù)中最小的那個(gè)，就是第K大的數(shù)。利用二分搜索找到第K大的數(shù)，然后在遍歷�？偟臅r(shí)間復(fù)雜度為 O(NlogN)
解法3：如果數(shù)據(jù)不能全部裝入內(nèi)存，上面兩種方法不是很好�？梢岳枚雅判�，即維護(hù)一個(gè)K個(gè)元素的最小堆即可。每次新考慮的一個(gè)數(shù)，如果比堆的最小數(shù)還要小，丟棄；如果比堆的最小數(shù)要大，那么替換最小元素，然后調(diào)整堆。時(shí)間復(fù)雜度為 O(N logK)
解法4：如果數(shù)據(jù)的范圍有限，可以利用計(jì)數(shù)法，即掃描文件一遍，記錄每個(gè)整數(shù)出現(xiàn)的次數(shù)，然后再?gòu)拇蟮叫∪∽畲蟮腒個(gè)即可。時(shí)間復(fù)雜度為O(N)
【四】 常見(jiàn)方法
你需要相信，面試官也是人，他不會(huì)有心情花30分鐘給你描述一個(gè)問(wèn)題，或者讓你做50頁(yè)紙的推導(dǎo)，考算法的目的只是為了你的思維能力，而不是真的想讓你搞定一個(gè)復(fù)雜的問(wèn)題。大部分問(wèn)題，都是有比較快速清晰的解決方法的。。。
1. 分治法 這絕對(duì)是你必須考慮使用的一種方法，如果有可能的話。動(dòng)態(tài)規(guī)劃這東西，在面試的時(shí)候比較沉重，不好描述，不好書(shū)寫(xiě)，而分治卻剛剛好，美麗，快捷，易書(shū)寫(xiě)，是面試官殺人越貨的首選武器。分治的用法實(shí)在是太多了，幾乎是無(wú)所不在，二分，快排，種群計(jì)數(shù)，各個(gè)唯美無(wú)比。。。
eg4.1：給你一個(gè)長(zhǎng)度為N的整數(shù)數(shù)組，請(qǐng)找出最大的子數(shù)組和。 -- 《編程之美》
這一題其實(shí)可以用動(dòng)態(tài)規(guī)劃解決。定義兩個(gè)輔助數(shù)組Start [N] 和 All [N] ，Start [i] 表示從元素i開(kāi)始，包含元素i的最大的一段連續(xù)數(shù)組和。All[i] 表示從元素i開(kāi)始，最大的一段連續(xù)數(shù)組和。All[0] = max { A[0], A[0]+Start[1], All[1] } 可以很方便的用動(dòng)態(tài)規(guī)劃解決。
int MaxSum(int *A, int n) {
All[n-1]=Start [n-1]=A[n-1];
for(int i=n-2;i>=0;i--) {
Start[i]= max( A[i], A[i]+Start[i+1] );
All[i]=max( Start[i], All[i+1] );
}
return All[0];
}
如果要求返回最大子數(shù)組的位置，可以在循環(huán)中記錄一下。算法還是能保持O(N)的時(shí)間復(fù)雜度的。
eg4.2： 求一個(gè)int（32bit）中，二進(jìn)制1的個(gè)數(shù)。 -- 《代碼之美》
可以參考eg1.1的方法1、方法2、方法3
2. 排序和查找 排序出現(xiàn)的次數(shù)實(shí)在是太多了，很重要的一點(diǎn)，排序的東西才能用二分。二分是如此好用，以至于我們總是想著排序。查找和排序總是緊密聯(lián)系的，當(dāng)然，僅僅是為了查找，做一次排序，你需要衡量一下代價(jià)。。。
eg4.3：有一個(gè)論壇，有ID發(fā)帖數(shù)目超過(guò)總數(shù)的一半，給你論壇所有帖子的ID列表，請(qǐng)你找到這個(gè)水王。 -- 《編程之美》
解法1：先將ID排個(gè)序，然后取中間位置的那個(gè)ID即可。
解法2：每次刪除不同的ID，最后剩下的ID即為所求。
擴(kuò)展1：如果有3個(gè)發(fā)帖很多的ID，并且發(fā)帖的數(shù)目都超過(guò)了總數(shù)N的1/4，找到這3個(gè)ID。
可以用類(lèi)似的解法，維護(hù)3個(gè)候選者。對(duì)于新ID，檢查3個(gè)候選者的出現(xiàn)次數(shù)。如果次數(shù)有0，那么將該候選者設(shè)置為新ID，并且把次數(shù)加1；如果次數(shù)都是大于0，并且新ID等于其中的一個(gè)候選者，那么將該候選者的出現(xiàn)次數(shù)加1；如果次數(shù)都是大于0，并且新ID不等于三個(gè)中的任意一個(gè)，那么將三個(gè)候選者的出現(xiàn)次數(shù)各減少1次。最后剩下的3個(gè)ID即為所求。
eg4.4：給一組一維的空間 [1, 6] [2, 4] ... ，請(qǐng)求是否有區(qū)間重疊。 -- 《編程之美》
解法：將目標(biāo)區(qū)間按X坐標(biāo)排序，然后合并相交區(qū)間，最后掃描一遍合并后的區(qū)間，檢查源區(qū)間是否在其中一個(gè)目標(biāo)區(qū)間中。最后一步也可以利用二分查找。
3. 減小問(wèn)題規(guī)模 很多時(shí)候，題目看上去很?chē)樔�，仔�?xì)分析一下，就可以刨去其中大部分的無(wú)關(guān)內(nèi)容，獲得真正的出題意圖，這一點(diǎn)很重要。另外有些時(shí)候，題目會(huì)在空間上做出一些限制，這個(gè)時(shí)候，你可以考慮動(dòng)態(tài)的對(duì)數(shù)據(jù)規(guī)模進(jìn)行縮減，比如用減法或除法抵消，用抑或抵消，等等。。。
eg4.5：給一個(gè)整數(shù)N，求它的階乘N!，有幾個(gè)0結(jié)尾。 -- 《編程之美》
解法：0的出現(xiàn)是因?yàn)?*5帶來(lái)的，因此只要計(jì)算min( 2的個(gè)數(shù), 5的個(gè)數(shù))即可。又由于2的出現(xiàn)頻率大于5，只要求5的個(gè)數(shù)即可
eg4.6：盒子里有三種顏色的球，紅黃藍(lán)，可以用任意兩個(gè)不同顏色的球，換兩個(gè)另外顏色的球，比如1紅 + 1黃 = 2藍(lán)�，F(xiàn)在盒子里面有171個(gè)紅球，172個(gè)黃球，173個(gè)藍(lán)球，問(wèn)，能不能經(jīng)過(guò)若干次交換，最終變成同一顏色的球。 -- TopLanguage
猜測(cè)：不能，最多只能是某種顏色0個(gè)，另一種1個(gè)，其余是第三種顏色。
eg4.7：有一組數(shù)，除了一個(gè)數(shù)只有1個(gè)，其他都是兩兩成對(duì)的，請(qǐng)找出那一個(gè)不成對(duì)的數(shù)。另，如果不成對(duì)的數(shù)有兩個(gè)，該如何是好。
解法：如果只有1個(gè)，可以將所有數(shù)做異或運(yùn)算，最后的結(jié)果就是要找的數(shù)。如果是2個(gè)，那么先將所有數(shù)做異或運(yùn)算，得到一個(gè)數(shù)，然后找到這個(gè)數(shù)的其中一位非0 bit，利用這一位將這組數(shù)分成兩部分，不成對(duì)的兩個(gè)數(shù)不會(huì)在同一部分，然后對(duì)這兩個(gè)部分分別調(diào)用只有1個(gè)情況的算法即可。
4. 常量法 典型的速餐方法，它的思想是，一組數(shù)，在某些情況下，和一定，通過(guò)這個(gè)常量，進(jìn)行反推，可快速搞定一些問(wèn)題。。。
eg4.9：有一副撲克牌（你可以用任意方式來(lái)表示），被抽去一張，請(qǐng)快速找出這抽去的一張是什么？ -- 微軟面試題
解法：算一下目前牌的數(shù)值總和x，原來(lái)完整的總和是y，則丟掉的牌是y-x。
5. 編碼 編碼真是個(gè)好東西，它可以將復(fù)雜的問(wèn)題抽象化。比如，對(duì)一個(gè)序列進(jìn)行編碼，可以直接映射到數(shù)組腳標(biāo)上，大大提高訪問(wèn)速度。。。
eg4.10：最近一次百度筆試題 eg4.11：有1000瓶超級(jí)名貴的葡萄酒，其中有1瓶有毒。這種毒藥很厲害，哪怕被稀釋了1000000倍還是可以毒死人的。但這個(gè)毒藥一定時(shí)間后才會(huì)毒發(fā)，時(shí)長(zhǎng)是1個(gè)月。為了不浪費(fèi)這些葡萄酒，有1000個(gè)壯士決定花5周的時(shí)間將毒酒找出，他們只希望最多有10個(gè)人犧牲，你需要如何安排才能實(shí)現(xiàn)。 -- TopLanguage
待解答
6. 概率 不要輕視概率題，哪怕是最基本的概率常識(shí)。概率題之所以被青睞，因?yàn)樗鼈兺`背直覺(jué)，容易讓人陷入迷茫，這種場(chǎng)面是面試官喜聞樂(lè)見(jiàn)的。我曾經(jīng)在baidu面試中，被一道簡(jiǎn)單的概率題，調(diào)戲的臉面全無(wú)，至今想起，仍然是汗流滿面。所以，為了人身安全，復(fù)習(xí)一下概率的基本知識(shí)吧。。。
eg4.12：有一個(gè)長(zhǎng)度為N的鏈表，N未知。希望你只遍歷一次鏈表，就從鏈表中等概率的挑出K個(gè)數(shù)。 -- TopLanguage
某博客的解法，非常好 http://m.emrowgh.com
a：首先挑出前k個(gè)數(shù)，保存在pick[1...k]中，然后從第k+1個(gè)開(kāi)始遍歷
for i = k+1 to N do //這里N不知道，但是可以用鏈表->next == null 來(lái)判斷是否到達(dá)鏈表末尾。
r = random(1, i);
if (1 <= r <= k);
pick[r] = i;
簡(jiǎn)單數(shù)學(xué)證明如下：
歸納法，算法剛開(kāi)始，對(duì)于前k個(gè)數(shù)被選中的概率都為1，，不失一般性，選擇其中的第j個(gè)來(lái)討論，
i = k+1輪：
random(1, i)返回值為j的概率為1/k+1，所以j保留下來(lái)的概率為k/k+1
i = k+2輪：
random(1, i)返回值為j的概率為1/k+2，所以j保留下來(lái)的概率為(k/k+1) * (k+1/k+2) = k/k+2
...
i = N輪
random(1, i)返回值為j的概率為1/N，所以j保留下來(lái)的概率為(k/k+1) * (k+1/k+2)*....* (N-1/N) = k/N
對(duì)于第k+1到第N個(gè)數(shù)，選擇其中的數(shù)m來(lái)討論，
當(dāng)i = m時(shí)：
random(1, i)返回值在[1, k]內(nèi)的概率為k/m，所以j保留下來(lái)的概率為k/m，設(shè)m保存在第s位
i = m+1輪：
random(1, i)返回值為s的概率為1/(m+1)，所以j保留下來(lái)的概率為(k/m) * (m/m+1) = k/(m+1)
...
i = N輪
random(1, i)返回值為s的概率為1/N，所以j保留下來(lái)的概率為(8/m) * (m/m+1) *....* (N-1/N) = k/N
得證。
【五】 加速方法
很多時(shí)候，你給的算法基本正確，但是還不夠優(yōu)秀。面試官會(huì)希望你優(yōu)化一下。優(yōu)化的方法有很多，就基本的思路就是，考慮一下到底哪里出現(xiàn)了浪費(fèi)。常見(jiàn)的浪費(fèi)有兩種，一種是用了比較沉重的運(yùn)算，比如除法、取模等，你可能需要為計(jì)算來(lái)加速。另外有時(shí)候，你的算法還太粗線條，比如只需要符號(hào)，你卻計(jì)算了總數(shù)等等。。。
eg5.1：求兩個(gè)數(shù)的最大公約數(shù)。 -- 《編程之美》
解法1：利用的原理 f( x, y) = f(y, x%y) ，即輾轉(zhuǎn)相除法
解法2：利用的原理 f(x , y) = f( y, x-y)，即輾轉(zhuǎn)相減法
解法3：根據(jù)兩個(gè)數(shù)的奇偶性
x is even, y is even f(x, y) = 2 * f( x>>1, y>>1)
x is even, y is odd f(x,y) = f( x>>1, y)
x is odd, y is even f(x,y) = f( x, y>>1)
x is odd, y is odd f(x,y) = f(y, x-y)
eg5.2：有一個(gè)整數(shù)數(shù)組A[N]，求其中任意N-1個(gè)數(shù)的最大乘積。 -- 《編程之美》
解法1：利用eg1.2的算法，計(jì)算出所有可能的N-1個(gè)數(shù)的乘積，然后遍歷一遍找出最大的乘積。
解法2：利用N個(gè)數(shù)的正負(fù)分布情況。先掃描一遍，統(tǒng)計(jì)處數(shù)組中正數(shù)個(gè)數(shù)p，負(fù)數(shù)個(gè)數(shù)n，零的個(gè)數(shù)z，絕對(duì)值最小的正數(shù)a 和負(fù)數(shù) b。
如果 z >=2 結(jié)果為0
如果 z =1
如果n為odd 結(jié)果為0
如果n為even 結(jié)果為除0外的乘積
如果 z =0
如果n為odd 結(jié)果為去掉絕對(duì)值最小負(fù)數(shù)后的乘積
如果n為even 結(jié)果為去掉絕對(duì)值最小的正數(shù)的乘積
eg5.3：估計(jì)一下快速排序的比較次數(shù)。 -- 《代碼之美》
解法：
int cc(int n){
int m;
if (n <= 1) return 0;
m = randint(1, n);
return n-1 + cc(m-1) + cc(n-m);
}
【六】 數(shù)據(jù)結(jié)構(gòu)
大部分面試時(shí)候，我們都是面向數(shù)組來(lái)設(shè)計(jì)算法，因?yàn)楹?jiǎn)單變化多，面試官好把握。但其他數(shù)據(jù)結(jié)果，同樣也很重要。AVL，B樹(shù)那樣的可能比較復(fù)雜，但是鏈表、樹(shù)這樣的結(jié)構(gòu)，也經(jīng)常出沒(méi)，我個(gè)人就碰見(jiàn)多次。。。
1. 鏈表 eg6.1：給你一個(gè)單鏈表的頭指針，在不使用大量附加數(shù)據(jù)或修改原有數(shù)據(jù)的前提下，檢查一個(gè)單鏈表是否有環(huán)。 -- 微軟面試題
解法：使用快慢兩個(gè)指針，慢指針p = p->next，快指針q = q->next->next，如果相遇，那么就有環(huán) 。
eg6.2：給你兩個(gè)鏈表，如何判斷其是否相交，如果相交，如何找到兩個(gè)鏈表的第一個(gè)交點(diǎn)。 -- 《編程之美》
解法：2個(gè)鏈表都遍歷到尾部，即p->next==null && q->next==null，然后判斷p == q。
eg6.3：只給你一個(gè)指向鏈表中某元素的指針，請(qǐng)刪除該元素。 -- 《編程之美》
解法：將后一個(gè)元素復(fù)制到當(dāng)前元素p->value = p->next->value，然后刪除后一個(gè)元素。
2. 樹(shù) eg6.4：寫(xiě)堆排序的算法
一般算法書(shū)上都有的，這里就不列了
eg6.5：判斷一棵二叉樹(shù)T中，是否包含另一顆二叉樹(shù)P的結(jié)構(gòu)。 -- 微軟面試題
【筆試面試算法總結(jié)】相關(guān)文章：
筆試面試的問(wèn)題04-21
面試筆試問(wèn)題及答案04-12
面試筆試試題及答案04-12
企業(yè)面試筆試題與答案04-16
筆試面試成功體會(huì)文章04-16
大學(xué)生筆試面試技巧04-18
面試行政筆試問(wèn)題04-20
文員面試筆試題及答案04-19
公司面試筆試題及答案04-19