面試筆試經(jīng)驗(yàn)技巧5 如何回答算法設(shè)計(jì)問題

在面試中，很多算法設(shè)計(jì)問題都是各家企業(yè)歷年來(lái)的現(xiàn)成題目，不管求職者以前對(duì)算法知識(shí)學(xué)習(xí)得是否扎實(shí)，理解得是否深入，學(xué)上一段時(shí)間，牢記于心，應(yīng)付此類題目應(yīng)該沒有問題，但遺憾的是，很多世界級(jí)知名企業(yè)也深知這一點(diǎn)，如果純粹是出一些毫無(wú)技術(shù)含量的題目，會(huì)讓考前“突擊手”占盡便宜，這樣不利于人才的選拔，所以，為了把優(yōu)秀的求職者與一般的求職者能夠更好地區(qū)分開來(lái)，他們往往會(huì)推陳出新，越來(lái)越傾向于出一些有技術(shù)含量的新題。

在面試中，算法的地位如同托福考試在出國(guó)考試中的地位——是必需的但不是最重要的，它只是眾多考核方面中的一個(gè)，不直接決定求職者的“生死”。雖然如此，但并不是說(shuō)不用去準(zhǔn)備算法知識(shí)，因?yàn)樗惴ㄖR(shí)回答得好，必然會(huì)成為面試的加分項(xiàng)，對(duì)于求職成功，百利而無(wú)一害。那么，如何應(yīng)對(duì)此類題目呢？很顯然，編者不可能將此類題目都在《程序員面試筆試寶典》中一一解答，一來(lái)由于內(nèi)容眾多，篇幅有限；二來(lái)也沒必要，今年考過了，以后一般就不會(huì)再考了，不然還是沒有區(qū)分度。編者以為，靠死記硬背肯定是行不通的，解答此類算法設(shè)計(jì)問題，需要求職者具有扎實(shí)的基本功以及良好的運(yùn)用能力，這里僅提供一些比較好的答題方法和解題思路，以供求職者在面試時(shí)應(yīng)對(duì)此類算法設(shè)計(jì)問題。

（1）歸納法 此方法通過寫出問題的一些特例來(lái)分析總結(jié)其中的一般規(guī)律。具體而言，就是通過列舉少量的特殊情況，經(jīng)過分析，最后找出其中的一般關(guān)系。例如，某人有一對(duì)兔子飼養(yǎng)在圍墻中，如果它們每個(gè)月生一對(duì)兔子，且新生的兔子在第二個(gè)月后也是每個(gè)月生一對(duì)兔子，問：一年后圍墻中共有多少對(duì)兔子？

使用歸納法解答此題，首先想到的就是第一個(gè)月有多少對(duì)兔子。第一個(gè)月，最初的一對(duì)兔子生下一對(duì)兔子，此時(shí)圍墻內(nèi)共有兩對(duì)兔子。第二個(gè)月仍是最初的一對(duì)兔子生下一對(duì)兔子，共有3對(duì)兔子。到第三個(gè)月，除最初的兔子新生一對(duì)兔子外，第一個(gè)月生的兔子也開始生兔子，因此共有5對(duì)兔子。通過舉例，可以看出，從第二個(gè)月開始，每一個(gè)月兔子總數(shù)都是前兩個(gè)月兔子總數(shù)之和，U_n+1=U_n+U_n-1，一年后，圍墻中的兔子總數(shù)為377對(duì)。

此種方法比較抽象，也不可能對(duì)所有的情況進(jìn)行列舉，所以，得出的結(jié)論只是一種猜測(cè)，還需要進(jìn)一步證明。

（2）相似法 如果面試官提出的問題與求職者以前用某個(gè)算法解決過的問題相似，此時(shí)就可以觸類旁通，嘗試改進(jìn)原有算法來(lái)解決這個(gè)新問題。而通常情況下，此種方法都會(huì)比較有效。

例如，實(shí)現(xiàn)字符串的逆序打印，也許求職者從來(lái)就沒遇到過此問題，但將字符串逆序肯定是在求職準(zhǔn)備的過程中見過的。將字符串逆序的算法稍加處理，即可實(shí)現(xiàn)字符串的逆序打印。

（3）簡(jiǎn)化法 使用此方法，應(yīng)先將問題簡(jiǎn)單化，例如改變一下數(shù)據(jù)類型、空間大小等，然后嘗試著將簡(jiǎn)化后的問題解決，一旦有了一個(gè)算法或思路可以解決這個(gè)被簡(jiǎn)化過的問題，再將問題還原，嘗試用此類方法解決原有問題。

例如，在海量日志數(shù)據(jù)中提取出某日訪問×××網(wǎng)站次數(shù)最多的IP。很顯然，由于數(shù)據(jù)量巨大，直接進(jìn)行排序不可行，但如果數(shù)據(jù)規(guī)模不大，采用直接排序不失為一種好的解決方法。那么，如何將問題規(guī)?？s小呢？于是想到了散列法，散列往往可以縮小問題規(guī)模，然后在簡(jiǎn)化過的數(shù)據(jù)里面使用常規(guī)排序算法即可找出此問題的答案。

（4）遞歸法 為了降低問題的復(fù)雜度，很多時(shí)候都會(huì)將問題逐層分解，最后分解為一些最簡(jiǎn)單的問題，這就是遞歸。使用此種方法，應(yīng)先解決最基本的情況，然后以此為基礎(chǔ)，解決其他問題。

例如，在尋求全排列時(shí)，可能會(huì)感覺無(wú)從下手，但仔細(xì)推敲，會(huì)發(fā)現(xiàn)后一種排列組合往往是在前一種排列組合的基礎(chǔ)上進(jìn)行重新排列，一旦知道了前一種排列組合的各類組合情況，只需要把最后一個(gè)元素插入到前面各種組合的排列里面，就解決了這一問題，即先截去字符串s[1，…，n]中的最后一個(gè)字母，生成所有s[1，…，n-1]的全排列，然后再將最后一個(gè)字母插入到每一個(gè)可插入的位置。

（5）分治法 任何一個(gè)可以用計(jì)算機(jī)求解問題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計(jì)算時(shí)間也越少。而分治法也是如此，即將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，各個(gè)擊破，分而治之。分治法一般包含三個(gè)步驟：①將問題的實(shí)例劃分為幾個(gè)較小的實(shí)例，最好具有相等的規(guī)模；②對(duì)這些較小的實(shí)例求解，而最常見的方法一般是遞歸；③如果有必要，則合并這些較小問題的解，以得到原始問題的解。

分治法是程序員面試常考的算法之一，一般適用于二分查找、大整數(shù)相乘、求最大子數(shù)組和、找出偽幣、金塊問題、矩陣乘法、殘缺棋盤、歸并排序、快速排序、距離最近的點(diǎn)對(duì)、導(dǎo)線與開關(guān)等。

（6）散列法 很多面試筆試題目都要求求職者給出的算法盡可能高效。那么，究竟什么樣的算法是高效的？一般而言，時(shí)間復(fù)雜度越低，算法越高效。而要想達(dá)到時(shí)間復(fù)雜度的高效，很多時(shí)候就必須在空間上有所犧牲，即“用空間來(lái)?yè)Q時(shí)間”。而用空間換時(shí)間最有效的方式就是散列法、大數(shù)組、位圖法。當(dāng)然，此類方法并非“包治百病”，有時(shí)面試官也會(huì)對(duì)空間大小進(jìn)行限制，此時(shí)，求職者只能再去思考其他的方法了。

其實(shí)，凡是涉及大規(guī)模數(shù)據(jù)處理的算法設(shè)計(jì)，散列法就是最好的方法之一。

（7）輪詢法 每道面試筆試題，在設(shè)計(jì)時(shí)，往往會(huì)有一個(gè)載體，這個(gè)載體便是數(shù)據(jù)結(jié)構(gòu)，例如數(shù)組、鏈表、二叉樹、圖等。當(dāng)載體確定后，可用的算法自然而然地就會(huì)顯露出來(lái)?？蓡栴}是，很多時(shí)候并不確定這個(gè)載體是什么。當(dāng)無(wú)法確定這個(gè)載體時(shí)，求職者一般也就很難想到合適的方法了。

編者建議，此時(shí)求職者可以采用最原始的方法——輪詢，在腦海中輪詢各種可能的數(shù)據(jù)結(jié)構(gòu)與算法，從中找出一種合適的解法。?？嫉臄?shù)據(jù)結(jié)構(gòu)與算法知識(shí)點(diǎn)見下表。

此種方法看似笨拙，其實(shí)很實(shí)用，只要求職者對(duì)常見的數(shù)據(jù)結(jié)構(gòu)與算法爛熟于心。

為了更好地理解這些方法，求職者可以在平時(shí)的準(zhǔn)備過程中，應(yīng)用此類方法去答題，練習(xí)得多了，自然就熟能生巧了，面試時(shí)遇到此類問題，也就能夠應(yīng)對(duì)自如了。