面試系列之一：關於前端面試演算法的一些建議

01-29

雖然周報系列停了，但是技術博客還是要繼續！

----------

7.12 日更新：評論中同學指出了我文章中的一些錯誤，我個人還在理解和修改。因為數學和演算法是我的弱項，文中的內容都是我查找資料和個人理解而來，所以有不足之處還請多多諒解。也歡迎直接糾正我文中的內容，留言給我，我會更新到文章中去。

----------

前言

如果你想去更大的平台發展，比如微軟、阿里、Airbnb、亞馬遜，即使是前端的崗位，在面試時（甚至每一輪）也會考驗一些演算法題目（雖然我覺得沒什麼道理）。總的來說面試演算法題的公司一半一半吧，另一半傾向於面試前端相關的實戰練習題。外企基本不考察你的前端能力，只考慮你的演算法和數據結構能力（別問我是怎麼知道的，我的面試史就是一部血淚史）。所以前端同學懂一些基本的演算法也是有必要的。我不知道其他語言的程序員在找工作時面試的演算法題有哪些，但前端的演算法面試題還算是比較基礎並且不難（至少相對於我而言）。我也算是面霸了，所以分享一些個人經驗，同時也是記錄下來寫給將來的有需要的自己。

中間還會穿插兩道實戰題，以及強調一些概念。

送分題不能丟

你常常有聽到說面試前刷 leetcode 的說法。但是在刷 leetcode 題目之前，我認為有些基礎分必須拿到，或者說送分題必須不能丟。

什麼是送分題？就是你大學數據結構或者是C語言教材遇到的那些題目。這些題目你做過，花一個學期學習過，即使現在忘了撿起來也算是容易的。例如數據結構里的那些排序演算法，查找演算法，還有樹的相關知識。面試的題目相對於書的內容其實更窄，比如關於樹的知識點，面試官的題目可能會暗示你是用二叉樹去解決一個問題，或者計算葉子節點個數，或者計算樹的深度。其他更簡單的例如使用遞歸和非遞歸的方式寫出二叉樹的前中後序遍歷。並不會考到例如平衡二叉樹或者是完全二叉樹的這樣的概念（至少我沒有遇到過），更不要說圖這樣的概念了。

查找演算法遇見的不多，更多的是考察排序演算法。演算法的基本款是必須要掌握的：冒泡排序、選擇排序、插入排序、快速排序、歸併排序、桶排序。學會寫這些演算法是下策，上策是你要知道這些演算法的原理和效率（也就是時間複雜度）。比如當你在面試里卡殼的時候，你至少可以描述演算法是如何工作的。而之所以要了解它們的效率，是因為面試官有可能讓你間接的寫一個演算法，例如不考慮空間效率，寫一個時間效率最高的。學會判斷時間複雜度很重要，在後面我們也會用到。

當你確保這些基礎題都已經萬無一失了。那麼就可以開始嘗試練習更難的題目了（抱歉我也不知道什麼樣才算更難得題目）。

當然難和容易依然是相對的，或許這些題目對我來說還算是簡單，但是一部分人來說仍然困難。但無論如何都有你擅長和曾經遇到過的問題，穩紮穩打，這些送分題不能丟。

對演算法精益求精

我高中數學老師曾經教導我們考試的最高境界是揣摩出出題者的意圖。每一位面試官提出的問題，其實在他心裡都已經有一個最佳答案了。所以面試的最高境界也是要擊中面試官心中的那個最優解，至少演算法題這一塊必須如此，當然你要是有更好的解決方案會更棒。

當一道演算法題給出時，你要想的不僅僅是如何解決這個問題，並且是如何最好的解決這個問題（如果時間允許的話你可以寫兩個解法）。然而怎樣算更優的解呢，當然是更高效，時間複雜度更低的方案。

接下來我們先粗略的說一說如何計算時間複雜度，以及通過實例說明什麼是更優的方案。

計算時間複雜度

時間複雜度是衡量一個演算法快慢的標誌（當然也存在空間複雜度）。時間複雜度說白了就是語句的執行次數，但這個執行次數我們要從抽象和宏觀的角度去考慮。

例如你寫了一段十行的代碼，但代碼語句不一定只執行了十條，因為其中可能有一條語句需要循環執行N次。當這個N等於10或20時，循環執行對於性能開銷微乎其微，但如果N變成百萬或者千萬級別的，性能的開銷就很可觀了。更甚者，如果這10行代碼中有一條語句是被N次嵌套循環執行，那麼執行的次數就是N*N = N^2，如果此時N依舊是百萬或者千萬級別，那麼後果就可想而知了。

通過以上的實例可以看出，一段代碼執行速度的瓶頸其實在於循環語句的執行效率（次數），所以當需要計算一段代碼的時間複雜度時，我們著重把代碼中影響最大的循環部分抽取出來，統計它的執行次數即可。時間複雜度用大O（Big O notion）表示。常見的時間複雜度情況有以下幾種

常數（Constant Time）級別O(1)：當執行代碼中不存在循環語句時時間複雜度即為常數級別，值得一提的是此時即使你的代碼有上百行也算是這個級別的，因為相對於循環中無限可能的N來說不值一提；
線性（Linear Time）級別O(n)：即一層嵌套循環，最常見的操作就是遍曆數組，查找最小值什麼的；
對數（Logarithmic Time）級別O(logN): 即執行次數是N的一半，例如在一個有序的數組中做折半查找、或者是二叉樹搜索：

while ( low <= high ) {n mid = ( low + high ) / 2;n if ( target < list[mid] )n high = mid - 1;n else if ( target > list[mid] )n low = mid + 1;n else break;n}n

平方數（Quadratic Time）級別O(n^2)，執行次數是N的平方，也就是我們最常見的兩層嵌套循環。這種場景在接下來的冒泡排序或者選擇排序中都能看到

以上是常見的一些複雜度級別，基於以上的認知，還可以推斷出當代碼中有c層嵌套循環時，時間複雜度可以是指數級別O(n^c)；又例如代碼有有一層循環執行，但每層循環執行中又有一個折半查找，那麼這段代碼的時間複雜度就是一個組合情況O(N * logN)。

你可能存在的另一個疑問是，如果在計算時間複雜度時不加上其他語句執行的次數，這樣豈不是更精確。例如一段一百行的代碼，其中有三行負責的是N次循環的語句，其餘的97行都是非循環語句，那麼時間複雜度可以是O(N + 97)？

這麼說沒有錯，但這麼做大可不必，因為常量對N的影響微乎其微。想像當N增長到百萬級別時，常量（無論是成百還是上千）在N、logN、N^2前都顯得太渺小，也就是說，這個演算法效率差的本質其實是 N本身以及它的循環次數決定的，增加或者減少一個常量並不會讓它執行變得更快或者更慢。所以通常在描述演算法是都會撇棄常量。

在某些場景中，例如排序演算法，循環的執行次數可能還與初始化等待排序的數組次序有關。所以還要區分最好情況和最壞情況的時間複雜度，這個問題具體情況具體分析。

更優解實戰

基於上面的知識點，我們用一道題實戰一下。題目如下：

給出任何一個字元串，比如sdjkasbfknmsdlasdhjbbmrtuy，找出第一次出現（從左至右順序）的，且在字元串里只出現過一次的字元。

首先我們懟上暴力解法，即依次遍歷：

function find(str) {n for (var i = 0; i < str.length; i++) {n var count = 0;n var flag = true;n for (var j = 0; j < str.length; j++) {n if (str[i] === str[j]) {n count++;n }n if (count > 1) {n flag = false;n break;n }n }n if (flag) {n return str[i];n }n }n}n

這個方案有沒有解決問題？有。但是不是最優解？不是，很顯然它有兩層循環嵌套，時間複雜度是O(n^2)。接下來我直接給出更優解，你們先看看是什麼原理：

如果只看代碼里的循環的話，最多只存在三個循環，注意這三個循環是線性的，不是嵌套的，所以時間複雜度是O(3n)，移除常量的話即是O(n)。

然而原理是什麼？相信你也看出來了，就是用空間犧牲時間，和桶排序的原理相似。我們把字元串的每個字元分離出來，構造一個hash表，key就是字元，值即為一個數組的索引值，而數組則按照字元出現的順序記錄字元出現的次數。最後再遍歷計數表，即能找到第一個只出現一次的字元。

原理如下圖所示：

請同時考慮遞歸和非遞歸的解法

如果你在練習演算法的過程中習慣使用遞歸演算法，那麼請同時考慮非遞歸演算法如何實現。個人經驗是通常使用遞歸演算法實現的功能也會要求用非遞歸演算法實現。為什麼要使用非遞歸解法？因為如果數量級較大的話，遞歸解法會出現棧溢出的情況。接下來我舉一個在實際面試中遇見的動態規劃的例子。

比如我有下面代碼中這種個數按照行數依次遞增的數字三角形，尋找一條從頂部到底邊的路徑（即每行選取一個數），使得路徑上所經過的數字之和最大。路徑上的每一步都只能往左下右下走。只需要求出這個最大和即可，不必給出具體路徑。

5, n 6, 7,n 9, 10, 3,n 12, 23, 0, 20n 8, 10, 11, 16, 8,n

首先我們決定用二維數組的方式存儲這類數據結構：

var arr = [n [5], n [6, 7],n [9, 10, 3],n [12, 23, 0, 20],n [8, 10, 11, 16, 8]n];n

遞歸解法

例如我們要求從第1行到第2行的路徑最大值，那麼實際上只要從第二行中選一個最大值的然後加上第一行的就可以了；
如果需要求從第1行到第3行的路徑最大值，那麼原理其實也是找出第二行到第三行的路徑最大值，然後加上第一行的值。那麼如何求從第二行到第三行的最大值呢，可以利用上一步中的原理，找到6或7的最大值取較大值。

也就是說，想求a[i][j]的路徑最大值，實際上是求a[i + 1][j]或a[i + 1][j + 1]兩者中較大的路徑最大值，取得後加上a[i][j]的值。而a[i + 1][j]和ar[i + 1][j + 1]路徑最大值的求發與a[i][j]一致。這就形成了一個遞歸。而遞歸的終止條件則是a[i][j]已經是最後一行的元素了，或者a[i][j]不存在

function max(arr, i, j) {n if (arr[i][j] == undefined || i === arr.length - 1) {n return arr[i][j] || 0;n } else {n return arr[i][j] + Math.max(n max(arr, i + 1, j),n max(arr, i + 1, j + 1)n )n }n}n

而非遞歸演算法理解起來更簡單。看最後兩行：

[12, 23, 0, 20],n[8, 10, 11, 16, 8]n

對於倒數第二行的第一個數12來說，最大路徑只可能是12 + 8或者12 + 10；很明顯最大值是12 + 10 = 22。此時為了節省空間，我們可以把最大值22覆蓋原始值12. 同理，我們可以依次求出倒數第二行其他數值的最大路徑值，最後結果是：

[22, 34, 16, 36]n[8, 10, 11, 16, 8]n

同理，我們可以求出倒數第三行，倒數第四行每個數的最大路徑值，直到第一行第一個數。實現如下：

function maxWithoutRecursion(arr) {n for (var i = arr.length - 2; i >= 0; i--) {n for (var j = 0; j < arr[i].length; j++) {n arr[i][j] = arr[i][j] + Math.max(n arr[i + 1][j],n arr[i + 1][j + 1] || 0n )n }n }n return arr[0][0]n}n

結束語

關於演算法面試我要分享的就這麼多了。下次聊關於React面試中需要注意的地方。也歡迎留言補充。

教你徹底學會動態規劃——入門篇
動態規劃之背包問題（一）
P01: 01背包問題
Array data structure
Binary tree data structure
Computer science in JavaScript: Quicksort
Friday Algorithms: JavaScript Merge Sort
Computer science in JavaScript: Merge sort
Problem Solving with Algorithms and Data Structures using Python
How to find time complexity of an algorithm