常見面試演算法題

① 面試會出哪些經典演算法題

如下：

1、排序演算法∶快速排序、歸並排序、計數排序

2、搜索演算法∶回溯、遞歸、剪枝技巧

3、圖論∶最短路、最小生成樹、網路流建模

4、動態規劃：背包問題、最長子序列、計數問題

5、基礎技巧：分治、倍增、二分、貪心

6、數組與鏈表：單/雙向鏈表、跳舞鏈

7、棧與隊列

8、樹與圖：最近公共祖先、並查集

9、哈希表

10、堆：大/小根堆、可並堆

11、字元串∶字典樹、後綴樹

演算法簡介：

演算法（Algorithm）是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。

如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。

演算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化演算法在內的一些演算法，包含了一些隨機輸入。

形式化演算法的概念部分源自嘗試解決希爾伯特提出的判定問題，並在其後嘗試定義有效計算性或者有效方法中成形。

這些嘗試包括庫爾特·哥德爾、Jacques Herbrand和斯蒂芬·科爾·克萊尼分別於1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義為形式化演算法的情況。

② 演算法面試題——動態規劃Kadane』s algorithm

動態規劃是大公司面試必考的演算法題。其中，「最大子序和」是其中的經典：

面試官：年輕人，前面表現的不錯嘛！看下這道題，給你這個數組[-2, 1, -3, 4, -1, 2, 1, -5, 4]，找到其中和最大的連續子數組，返回最大值。

我：

使用Kadane』s Algorithm解決這個問題。Kadane』s Algorithm可以簡單理解為動態規劃的一種應用，它通過維護兩個變數：localMax和globalMax，來計算連續子數組的最大和。localMax表示以當前元素結尾的子數組的最大和，而globalMax則記錄遍歷過程中發現的最大值。

我們以數組[-2, 1, -3, 4, -1, 2, 1, -5, 4]為例，從左到右遍歷數組。

當遍歷到元素4時，localMax為4（因為4是當前元素），globalMax也更新為4（因為這是遍歷到的第一個元素）。

遍歷到元素-1時，我們考慮兩種情況：
1. 包括前面的元素4，即localMax更新為4 + (-1) = 3。
2. 不包括前面的元素4，即從元素-1開始新的子數組。由於-1 > 3，我們選擇-1作為新的localMax。
因此，globalMax更新為-1。

遍歷到元素2時，localMax為2（因為2 > 1），globalMax更新為2。

遍歷到元素1時，localMax更新為3（因為3 > 2 + 1），globalMax也更新為3。

遍歷到元素-5時，我們考慮兩種情況：
1. 包括前面的元素3，即localMax更新為3 + (-5) = -2。
2. 不包括前面的元素3，即從元素-5開始新的子數組。由於-5 < 3，我們選擇3作為新的localMax。
因此，globalMax更新為3。

遍歷到元素4時，localMax為4（因為4 > 3 + 4），globalMax更新為4。

最終，我們得到數組的最大子序和為4。

動態規劃和Kadane』s Algorithm在解決「最大子序和」問題時，通過維護局部最優解和全局最優解，避免了暴力演算法中的重復計算，大大提高了效率。

理解Kadane』s Algorithm的關鍵在於，它通過比較當前元素和當前元素加上前面元素的最大和，來決定是否更新局部最優解。這樣，我們不僅避免了重復計算，還能在遍歷過程中不斷更新全局最優解。

此外，Kadane』s Algorithm在解決類似問題時，如「買賣股票的最佳時機」，同樣可以應用動態規劃的思想，通過維護局部最優解和全局最優解，來找到最優策略。

動態規劃和Kadane』s Algorithm是解決一系列動態規劃問題的有效工具，通過理解和應用這些演算法，可以大大提高解決問題的效率和准確性。