本章透過八道經典的面試難題，展示如何運用前面各章介紹的理論來解決實際問題。這些問題都是 Google、微軟、Facebook 等公司常考的面試題。如果能不經提示就解決所有這些問題，說明已經超過 70% 的頂尖公司新入職工程師的水平。
11.1 最長連續子序列問題#
最長連續子序列（Longest Consecutive Subsequence）是很多計算機公司常考的面試題。
問題定義#
- 給定一個隨機的整數序列，找到其中最長的連續子序列
- 需要先釐清「子序列」的嚴格定義：子序列是指將原序列刪除一部分元素後所剩餘的序列，而非子集合
版本一：序列中的子序列#
- 關鍵在於使用哈希表將隨機訪問和順序訪問聯繫起來
- 算法 11.1：對序列中的每個元素，檢查它是否是某個連續子序列的最大元素（在哈希表中查找 element[i]-1 是否存在），如果不存在則新建條目，如果存在則合併到已有子序列中
- 時間複雜度為 O(N)，因為只掃描一遍序列，每個元素的處理時間是常數 O(1)
版本二：集合中的最大子集#
- 原先的序列變成了集合，尋找讓子集中的元素構成一個連續序列的最大子集
- 算法 11.2：在算法 11.1 的基礎上，對哈希表中的每個數據項進行掃描，檢查是否能與其他子序列合併（往前延展）
- 兩個算法配合使用，複雜度不變，仍為 O(N)
11.2 區間合併問題#
問題定義#
- 給定若干區間 [l1,u1], [l2,u2], …，將它們合併並輸出合併後的區間列表
- 兩個區間有重疊時合併為一個，無重疊時保持分開
解法#
- 先將所有區間按下界排序（下界相同時比較上界）
- 順序掃描：判斷相鄰兩個區間是否有重疊（比較前一個的上界和後一個的下界）
- 有重疊則合併為 [l1, max(u1, u2)]，無重疊則分別輸出
- 時間複雜度為 O(NlogN)，排序是瓶頸，合併過程是線性的
- 不存在線性複雜度的算法，因為在確定區間下界時需要排序
11.3 12 球問題#
12 球問題是一道非常難的思考題，考查的是對信息和編碼的理解。
問題#
- 12 個外觀一樣的球，其中 1 個球的質量和其他 11 個不同（可能輕或重）
- 用天平秤 3 次，找到那個壞球，並確定它是輕還是重
解題思路#
- 問題的本質是 24 選 1（12 種球 x 2 種輕重可能），共 24 種情況
- 每次稱重產生 3 種結果（<、=、>），即 1 吹特的信息，3 次稱重共 3 吹特可以區分 27 種情況
- 核心原則：每次稱重必須獲得 1 吹特的信息，否則信息不夠用
- 第一步：將 12 個球分為 3 組（1-4、5-8、9-12），取前 2 組稱重，3 種結果各將 8 種可能減少到 3 種、3 種或 2 種
- 後續兩步：恪守每稱一次就把可能的情況除以 3 的原則，逐步縮小範圍
- 延伸問題：120 個球稱 5 次可以找到壞球，但 121 個球不可能用 5 次稱出
11.4 天際線問題#
問題#
- 給定一些長方形的坐標（左下角和右上角），描繪出它們合併後的輪廓（天際線）
- 輸入是成對的坐標，輸出是輪廓多邊形的頂點列表
解法#
- 將每個長方形表示為兩個三元組：左上角 (position, height, L) 和右上角 (position, height, R)
- 將所有頂點按橫坐標排序後順序掃描
- 維護一個高度隊列，判斷當前最高的高度和新遇到的頂點的高度是否相同，確保每個長方形能夠處理完畢
- 遇到左側頂點時：如果比當前最高的高，記錄該點；否則只將高度放入隊列
- 遇到右側頂點時：如果高度和隊列中最高的相同，記錄並刪除；否則只從隊列中移除
- 高度隊列最有效的實現方法是使用優先隊列（Priority Queue）
- 時間複雜度為 O(NlogN)，無法再找到更好的方法
11.5 最長回文問題（Longest Palindrome Match）#
問題#
- 給定一個字符串，用計算複雜度最低的方法找到它最長的回文子串
- 回文就是一串對稱的字符串，如 aba、abba 等
O(N^2) 的中心擴展法#
- 以每個字符為中心，向兩邊擴展，找到以該字符為中心的最長回文
- 為避免遺漏偶數長度的回文（如 abba），在所有字符間插入特殊字符 #
- 複雜度為 O(N^2)，因為要讓 center 掃描整個字符串，每一遍掃描都可能要 O(N)
Manacher 算法（O(N)）#
- 本質上是建立在遞歸基礎之上的動態規劃算法
- 利用已找到的回文（Palindrome_i）的信息，跳過不必要的比較，直接從回文的右端繼續往右搜索
- 三種情況分析：
- 情況 1：第二個回文在第一個回文的範圍內，長度由鏡像位置確定，直接跳過
- 情況 2：第二個回文的左邊界觸及或超出第一個回文的左邊界，需要從第一個回文的右邊界之外開始比較
- 情況 3：第四個回文的中心超出第一個回文的右邊界，需要逐字符比較
- 每個字符只作為某個回文右邊的字符被比較一次，因此總的字符串比較次數是 2N，算法複雜度是線性的
11.6 計算器問題#
設計並實現一個計算器，是一道可以不斷深入的開放式問題，也是 Google 產品經理面試題。
四個層次#
- 第一層：支持不帶括號的四則運算，利用堆棧實現（數字轉換的優先級高於任何運算符）
- 第二層：支持乘方和開方運算，需要用函數表示各種運算的優先級
- 第三層：支持帶括號 “()” 的運算，遇到 “(” 時遞歸調用計算器本身，遇到 “)” 時返回結果
- 第四層：支持三角函數 sin(x)、對數函數 log(x) 等
產品設計考量#
- 需要考慮各種異常情況（如除數為零、括號不匹配）
- 需要考慮不同的表達式理解（如 “5+10%=” 在中美文化中有不同理解）
- 面試官考查的不僅是技術能力，還有產品設計意識和溝通能力
11.7 搜索結果摘要生成#
這是一道 Google 的經典面試題，考查如何從網頁文本中提取包含最多搜索關鍵詞的摘要片段。
問題定義#
- 在一個文本中給定一個長度為 k 的窗口，選定窗口位置使關鍵詞出現的總次數最多
單關鍵詞的滑動窗口算法#
- 利用搜索引擎已建立的索引（記錄關鍵詞在網頁中出現的位置）
- 維護「當前窗口」和「歷史窗口」兩個信息，不斷移動窗口並更新最優結果
- 複雜度為 O(L)，L 為索引的長度
多關鍵詞的索引合併#
- 將兩個詞的索引類似歸併排序的方式合併
- 用兩個指針來回移動，比較兩個詞下一次出現位置誰更靠前
- 複雜度為 O(L1+L2)，通常比直接掃描網頁文本節省 99% 的時間
進階考量#
- 關鍵詞權重：使用逆向文件頻率（IDF）加權，讓更重要的詞有更高權重
- 關鍵詞平衡性：把關鍵詞第一次出現在窗口中的權重放大 C 倍（C > 1），鼓勵所有關鍵詞都出現
- N 元組匹配：二元組或 N 元組的匹配應該給予更高的優先級
11.8 尋找和等於 k 的子數組問題#
這是矽谷公司經常考到的動態規劃面試題。
問題定義#
- 給定一個數組，尋找其中連續的子數組，使其元素之和等於給定的常數 k
暴力解法#
- 使用兩重循環確定子數組的起始和結束位置，複雜度為 O(N^2)
線性複雜度解法（算法 11.4）#
- 計算截至每個元素的部分和 Sum_j，並存在哈希表 Sum 中
- 如果 Sum_j - k 是到前面某個元素的部分和 Sum_i，那麼從第 i+1 到第 j 個元素就形成了一個和為 k 的子數組
- 由於在哈希表中查找 Sum_j - k 的時間是 O(1)，整個算法的複雜度為 O(N)
- 兩個關鍵：第一個是從尋找和等於 k 的連續子數組變成尋找部分和等於 Sum_j - k 的子數組；第二個是用哈希表以部分和為索引存儲相關信息
延伸#
- 可以擴展為輸出所有符合條件的子數組，只需在哈希表的數據項中記錄部分和和對應的子數組右邊界位置
結束語#
- 平時要下功夫掌握好計算機科學的精髓，搞懂書中給出的例題和思考題
- 臨場發揮時注意三個技巧：
- 做好溝通：先把問題搞清楚，在此之前不要急於回答
- 避免直覺陷阱：過於直觀的方法常常是陷阱，過於複雜的方法常常會走偏
- 回答好開放式問題：沒有絕對對與錯之分，永遠要立足於找到更好的答案