Technical Questions#

技術問題是許多頂尖科技公司面試的核心。許多應試者會被這些問題的難度嚇到，但其實有邏輯性的方法可以應對。

How to Prepare（如何準備）#

許多應試者只是閱讀題目和解答，這就像讀一道微積分題和它的答案來學微積分——你需要的是實際練習解題。

對書中（以及任何你遇到的）每道題目，請遵循以下步驟：

1. 自己嘗試解題：盡量不用提示。許多題目設計本來就很難，卡住是正常的。思考時也要考慮時間與空間效率。
2. 在紙上寫程式碼：電腦提供語法高亮、自動補全和快速除錯——紙上沒有。提前適應這種緩慢的節奏。
3. 在紙上測試程式碼：包含一般情況、邊界情況、錯誤情況等。面試時需要這樣做，提前練習。
4. 將紙上的程式碼原封不動輸入電腦：你可能會犯許多錯誤。記錄這些錯誤，以便在真正的面試中多加注意。

盡量多做模擬面試。你和朋友可以輪流擔任面試官，給彼此出題。擔任面試官也能讓你學到很多，因為你會理解面試官視角。

What You Need To Know（必備知識）#

許多公司的資料結構與演算法題不是知識測驗，但確實預設你有基礎知識。

Core Data Structures, Algorithms, and Concepts（核心知識清單）#

對於每個主題，確保你理解如何使用和實作它，以及其時間與空間複雜度。

Hash Table 是極其重要的資料結構，務必非常熟悉。如果你對上述任何資料結構或演算法不夠熟悉，請從頭實作練習。

Powers of 2 Table（2 的冪次表）#

這張表對涉及擴展性或記憶體限制的題目很有用：

Walking Through a Problem（解題步驟）#

書中提供了一張解題流程圖，依序為 7 個步驟：

1. Listen Carefully（仔細聆聽）#

不只是確保聽對題目，更要記住題目中所有獨特的資訊。

• 題目說「兩個已排序的陣列」→ 排序這個特性很可能對最優解很重要
• 題目說「設計一個在伺服器上重複執行的演算法」→ 這意味著可能適合預計算或快取

許多應試者一開始聽得很清楚，但 10 分鐘後就忘掉了關鍵細節，導致無法找到最優解。

2. Draw an Example（畫一個例子）#

例子能大幅提升你解題的能力，但要畫一個好的例子：

• 具體：使用真實的數字或字串（不要只畫空框）
• 夠大：大多數例子太小了，大約需要比直覺多 50%
• 不是特殊情況：要非常小心，特殊情況很容易讓你誤解問題

3. State a Brute Force（說出暴力解）#

一旦有了例子，先說出暴力解。這是可以預期的，面試官知道初始解通常不是最優的。

• 說明暴力解的時間和空間複雜度
• 然後再討論如何改進

不要因為覺得暴力解太明顯或太差就跳過這步。即使對你來說很顯然，面試官也想看到你能識別簡單解法。

4. Optimize（最佳化）#

有了暴力解後，努力最佳化。幾個有效的技巧：

1. 尋找任何未使用的資訊——題目給你的資訊幾乎都有用
2. 使用新的例子，有時換個例子能讓你看出模式
3. 「錯誤地」解決問題，然後思考為什麼失敗，能否修正？
4. 時間與空間的取捨——使用 Hash Table 往往非常有用
5. 預計算資訊——重新組織資料（排序等）或提前計算某些值
6. 使用 Hash Table——在面試題中極為常用
7. 思考最佳可能執行時間（BCR）

5. Walk Through（完整走一遍）#

確定了最優解後，不要立刻開始寫程式碼。先完整走過你的演算法：

• 確保真正理解每個細節
• 知道哪些變數以及何時會改變

在白板上寫程式碼很慢，而且很難修改，所以盡量一開始就寫接近完美的程式碼。

6. Implement（實作）#

現在你知道要寫什麼了，開始實作：

• 從白板左上角開始寫（你會需要空間）
• 避免「線條偏斜」（每行都歪著寫）

好的程式碼具備以下特性：

• Correct（正確）：對所有預期和非預期的輸入都能正確運作
• Efficient（高效）：在時間和空間上都盡可能高效，包含漸進效率和實際效率
• Simple（簡單）：如果 10 行能做到，不要寫 100 行
• Readable（易讀）：其他開發者應該能看懂你的程式碼，適時加入必要的註解
• Maintainable（可維護）：程式碼應易於修改和維護

在實作中展示好程式碼的方法：

• 善用資料結構：設計適當的資料結構，而非把所有東西塞進陣列
• 適當複用程式碼（Code Reuse）：找出可以共用的邏輯，寫一個通用函式
• 模組化（Modular）：將相對獨立的邏輯分離成自己的方法，使程式碼更易讀、測試和維護
• 彈性與健壯（Flexible and Robust）：考慮更通用的情況，避免 hardcode 特定值
• 錯誤檢查（Error Checking）：不假設輸入的合法性，進行驗證

好的程式設計師不假設輸入，而是驗證輸入是否符合預期。若錯誤檢查很繁瑣，可以說明「我會寫這些檢查」並在旁邊留空間，先完成主要邏輯。

7. Test（測試）#

不要在真實世界提交未測試的程式碼，面試中也一樣。

聰明的測試順序：

1. 概念測試（Conceptual Test）：像 code review 一樣逐行讀你的程式碼，它做了你認為它做的事嗎？
2. 奇怪的程式碼（Weird-looking Code）：注意 x = length - 2 這樣的行、從 1 開始的迴圈等容易出錯的地方
3. 熱點（Hot Spots）：遞迴的 base case、整數除法、二元樹的 null 節點、linked list 的首尾
4. 小測試案例（Small Test Cases）：使用 3~4 個元素的陣列，而非 8 個元素的大陣列——速度更快，效果一樣好
5. 特殊情況（Special Cases）：null 或單個元素的值、極端值、其他特殊情況

找到 bug 時，仔細分析為什麼會發生，確保你的修正是最好的方案，而非第一個想到的修正。

Optimize & Solve Techniques（最佳化與解題技巧）#

Technique #1: Look for BUD#

BUD 是最有用的最佳化方法，代表三種演算法常見的「浪費」：

• Bottlenecks（瓶頸）：演算法中拖慢整體速度的部分
• Unnecessary Work（不必要的工作）：可以省略的計算
• Duplicated Work（重複的工作）：一再重複計算相同的東西

Bottleneck 範例：給定整數陣列，計算差為 k 的整數對數量。

• 暴力解：O(N²)——對每個元素搜尋另一個元素
• 瓶頸是「搜尋」：將陣列放入 hash table，搜尋變成 O(1)
• 最終：O(N)

Unnecessary Work 範例：找出 a³ + b³ = c³ + d³ 的所有整數解（1 到 1000）。

• 暴力解是四層迴圈 O(N⁴)
• 發現 d 可以直接計算：d = ∛(a³ + b³ - c³)，省去最內層迴圈
• 降至 O(N³)

Duplicated Work 範例：同樣的問題，對每個 (a,b) 都重新計算所有 (c,d)。

• 預先計算所有 (c,d) 組合放入 hash map
• 查詢時直接 lookup，降至 O(N²)

Technique #2: DIY (Do It Yourself)#

人類的直覺往往比我們自己意識到的更強。把演算法問題想成一個真實的例子，然後直覺地手動解決它。

範例：給定小字串 s 和大字串 b，找出 s 在 b 中所有排列的位置。

大多數人看到這個題目會想：「生成 s 的所有排列，然後在 b 中搜尋」——這是 O(S! × B) 的爛解法。

但如果你給自己一個具體的例子，手動找答案，幾乎所有人都會自然地用「滑動視窗」的方法。把你直覺的解法逆向工程出來，就是好演算法。

Technique #3: Simplify and Generalize#

1. 先簡化問題的某個限制（例如把資料型態從 string 改成 character）
2. 解決簡化後的問題
3. 將解法推廣回原始的複雜問題

Technique #4: Base Case and Build#

1. 先解決 n = 1 的 base case
2. 嘗試從 n-1 的解構建出 n 的解
3. 當 n = 3 或 4 時，用先前的解推導

Base Case and Build 演算法通常會自然地引導出遞迴解法。

Technique #5: Data Structure Brainstorm#

有時候只需要腦力激盪各種資料結構，嘗試套用每一種，看哪種最合適。

範例：數字隨機生成後儲存到陣列，如何追蹤中位數？

• Linked List？不太好，存取和排序都不方便
• Array？需要保持排序，成本高
• Binary Tree？可行，平衡 BST 的中間節點接近中位數
• Heap？最棒！兩個 heap（一個 min-heap、一個 max-heap）可以追蹤大半和小半的元素

做的題目越多，你對「哪種資料結構適合哪種問題」的直覺就越精準。

Best Conceivable Runtime (BCR)#

BCR（最佳可想像執行時間） 是你能合理想像的對一個問題的最快解法。

• 找出兩個長度 A 和 B 的陣列的共同元素：BCR 是 O(A + B)，因為你至少要看過每個元素一次
• 印出陣列中所有整數對：BCR 是 O(N²)，因為有 N² 對要印出

BCR 與 Best Case Runtime 完全不同！BCR 是針對「問題」，描述任何演算法都無法突破的理論下界。Best Case Runtime 是針對「特定演算法」，幾乎沒什麼用。

BCR 的實際用途#

1. 告訴你還有多少優化空間：若你的演算法已達到 BCR，就不用再優化時間複雜度了，可以轉而考慮空間複雜度。
2. 提示你需要減少什麼：若 BCR 是 O(N) 但你的演算法是 O(N log N)，你需要消除那個 log N 因子。
3. 「免費的」工作：任何在 BCR 以內的工作都是「免費的」，不影響整體複雜度。

BCR 範例：在兩個各有 N 個元素的有序陣列中找共同元素。

• 暴力解：O(N²)
• 改進（Binary Search）：O(N log N)
• BCR：O(N)

BCR 告訴我們目標是 O(N)。既然搜尋的工作量是 O(N) 以內都是「免費」的，可以把 B 的所有元素放入 hash table（O(N)），再遍歷 A 進行 O(1) 查詢，達到 O(N) 時間、O(N) 空間。

若還想優化空間，利用兩個陣列都已排序的特性，用雙指針線性掃描，達到 O(N) 時間、O(1) 空間——達到 BCR 且空間最小。

Handling Incorrect Answers（如何面對錯誤答案）#

面試中最普遍也最危險的謠言是：應試者需要把每道題都答對。這不完全正確。

• 面試評估不是二元的「對或錯」，而是綜合評估：解法有多優、花了多長時間、需要多少提示、程式碼有多乾淨
• 你的表現是和其他應試者相比的：難題允許有更多錯誤
• 強力應試者通常需要 20~30 分鐘才能解出設計上的難題
• 就算是拿到錄取通知的人，也幾乎都犯了錯誤

When You’ve Heard a Question Before（聽過這道題）#

如果你之前看過這道題，誠實地告訴面試官。面試官問這道題是要評估你的解題能力；如果你已經知道答案，就剝奪了他們評估你的機會。此外，面試官可能會覺得你不誠實。如果你承認，反而會得到誠信加分。

The “Perfect” Language for Interviews（面試語言的選擇）#

許多頂尖公司的面試官不在乎你用什麼語言，他們更關心你解決問題的能力。不過，如果你有多個熟悉的語言可以選擇，考慮以下因素：

• Prevalence（普及度）：讓面試官能看懂你的程式碼，使用較廣泛的語言（如 Java、Python、C++）會更理想
• Language Readability（易讀性）：有些語言（如 Java）因為和 C/C++ 語法相近，對大多數人來說很易讀；Scala 或 Objective-C 則差異較大
• Potential Problems（潛在問題）：C++ 有記憶體管理和指針問題，可能增加不必要的複雜度
• Verbosity（冗長性）：Java 比 Python 更冗長。在白板上寫 Java 的 HashMap 初始化需要好幾行，而 Python 一行就搞定。可以縮寫後向面試官說明
• Ease of Use（易用性）：Python 能輕鬆從函式回傳多個值；Java 則需要一個新的 class

若被允許選擇語言，選擇你最熟悉的語言。熟悉度比語言特性更重要。

What Good Coding Looks Like（好程式碼的樣貌）#

好的程式碼具備以下特性：

• Correct（正確）：對所有預期和非預期的輸入都正確運作
• Efficient（高效）：時間和空間都盡可能高效（包含漸進效率和實際效率）
• Simple（簡單）：能 10 行解決就不寫 100 行
• Readable（易讀）：其他開發者能看懂並理解其運作方式，必要時加入簡潔的註解
• Maintainable（可維護）：在產品生命週期中易於修改，對他人和原作者都容易維護

在面試中具體展現這些特性的方法：

Use Data Structures Generously（善用資料結構）#

與其用 primitive array 或兩個平行的陣列，不如設計一個適當的資料結構（class/struct）。

Appropriate Code Reuse（適當複用程式碼）#

寫通用函式，讓程式碼能在不同情境下複用，減少重複邏輯。

Modular（模組化）#

將相對獨立的邏輯分離成獨立的函式，這讓程式碼更容易讀、測試和維護。

Flexible and Robust（彈性與健壯）#

不要 hardcode 特定值（如 3×3 的棋盤大小）。使用變數，讓程式碼能處理更通用的情況。

Error Checking（錯誤檢查）#

謹慎的工程師不假設輸入的合法性，而是透過 ASSERT 或 if-statement 驗證輸入。

Don’t Give Up!（不要放棄！）#

面試題可能讓人感到不知所措，但這正是面試在測試的：當你面對困難問題時，你是迎難而上還是退縮？展現你主動應對挑戰問題的精神。

面試題設計本來就很難，遇到很難的題目不應該讓你感到意外。對解決難題表現出興奮感，會加分。