經(jīng)驗技巧5 如何回答算法設(shè)計問題

程序員面試中的很多算法設(shè)計問題，都是歷年來各家企業(yè)的“炒現(xiàn)飯”，不管求職者以前對算法知識學(xué)習(xí)得是否扎實，理解得是否深入，只要面試前買本《程序員面試筆試寶典》（編者早前編寫的一本書，由機(jī)械工業(yè)出版社出版），學(xué)習(xí)上一段時間，牢記于心，應(yīng)付此類題目完全沒有問題。但遺憾的是，很多世界級知名企業(yè)也深知這一點，如果純粹是出一些毫無技術(shù)含量的題目，對于考前“突擊手”而言，可能會占盡便宜，但對于那些技術(shù)好的人而言是非常不公平的。所以，為了把優(yōu)秀的求職者與一般的求職者能夠更好地區(qū)分開來，他們會年年推陳出新，越來越傾向于出一些有技術(shù)含量的“新”題，這些題目以及答案，不再是以前的陳谷子爛芝麻了，而是經(jīng)過精心設(shè)計的好題。

在程序員面試中，算法的地位就如同是GRE或托福考試在出國留學(xué)中的地位一樣，必須但不是最重要的，它只是眾多考核方面中的一個而已，不一定就能決定求職者的生死。雖然如此，但并非說就不用去準(zhǔn)備算法知識了，因為算法知識回答得好，必然會成為面試的加分項，對于求職成功，百利而無一害。那么如何應(yīng)對此類題目呢？很顯然，編者不可能將此類題目都在本書中一一解答，一來由于內(nèi)容眾多，篇幅有限，二來也沒必要，今年考過了，以后一般就不會再考了，不然還是沒有區(qū)分度。編者以為，靠死記硬背肯定是行不通的，解答此類算法設(shè)計問題，需要求職者具有扎實的基本功以及良好的運用能力，編者無法左右求職者的個人基本功以及運用能力，因為這些能力需要求職者“十年磨一劍”地苦學(xué)，但編者可以提供一些比較好的答題方法和解題思路，以供求職者在面試時應(yīng)對此類算法設(shè)計問題。“授之以魚不如授之以漁”，豈不是更好？

（1）歸納法

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

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

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

（2）相似法

此方法考慮解決問題的算法是相似的。如果面試官提出的問題與求職者以前用某個算法解決過的問題相似，此時此刻就可以觸類旁通，嘗試改進(jìn)原有算法來解決這個新問題。而通常情況下，此種方法都會比較奏效。

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

（3）簡化法

此方法首先將問題簡單化，例如改變一下數(shù)據(jù)類型、空間大小等，然后嘗試著將簡化后的問題解決，一旦有了一個算法或者思路可以解決這個被簡化過的問題，再將問題還原，嘗試著用此類方法解決原有問題。

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

（4）遞歸法

為了降低問題的復(fù)雜度，很多時候都會將問題逐層分解，最后歸結(jié)為一些最簡單的問題，這就是遞歸。此種方法，首先要能夠解決最基本的情況，然后以此為基礎(chǔ)，解決接下來的問題。

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

（5）分治法

任何一個可以用計算機(jī)求解的問題所需的計算時間都與其規(guī)模有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計算時間也越少。而分治法正是充分考慮到這一內(nèi)容，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。分治法一般包含以下三個步驟：

1）將問題的實例劃分為幾個較小的實例，它們之間最好具有相等的規(guī)模。

2）對這些較小的實例求解，而最常見的方法一般是遞歸。

3）如果有必要，合并這些較小問題的解，以得到原始問題的解。

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

（6）Hash法

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

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

（7）輪詢法

在設(shè)計每道面試筆試題時，往往會有一個載體，這個載體便是數(shù)據(jù)結(jié)構(gòu)，例如數(shù)組、鏈表、二叉樹或圖等，當(dāng)載體確定后，可用的算法自然而然地就會暴露出來。可問題是很多時候并不確定這個載體是什么。當(dāng)無法確定這個載體時，一般也就很難想到合適的方法了。

編者建議，此時求職者可以采用最原始的思考問題的方法--輪詢法，在腦海中輪詢各種可能的數(shù)據(jù)結(jié)構(gòu)與算法，常考的數(shù)據(jù)結(jié)構(gòu)與算法一共就那么幾種（見表1），即使不完全一樣，也是由此衍生出來的或者相似的，總有一款適合考題。

此種方法看似笨拙，其實實用，只要求職者對常見的數(shù)據(jù)結(jié)構(gòu)與算法爛熟于心，一點都沒有問題。

為了更好地理解這些方法，求職者可以在平時的準(zhǔn)備過程中，應(yīng)用此類方法去答題，做得多了，自然對各種方法也就熟能生巧了，面試的時候，再遇到此類問題，也就能夠收放自如了。算法設(shè)計功力的練就是平時一點一滴的付出和思維的磨煉。方法與技巧也許只是給面試打了一針“雞血”、喂一口“大補(bǔ)丸”，不會讓自己變得從容自信，真正的功力還是需要一個長期的積累過程的。