DSA面試題

你已經寫過幾百題，卻還是覺得沒準備好，這通常代表你練習的是錯誤的那一半。本節說明面試到底在考什麼，讓練習方向對上。

一場即時的資料結構與演算法面試會同時考查四件事：你能不能認出題目屬於哪種模式、能不能在寫程式前說清楚思路、實作在邊界情況下是否正確，以及能不能用口語說明複雜度。許多候選人只優化第三點、忽略第二點，結果一個正確卻沒有解釋的答案反而被扣分。

辨識這一步，正是模式練習勝過刷題數量的原因。題目很少是全新的，大多是既有模式的重新組合。一旦你能在頭一分鐘內說出這是在頻率映射表上做滑動視窗，剩下的就只是執行。依語言與職缺分類的相關題庫，見面試問題庫。

這些模式涵蓋了大部分常見考題。要學會辨識指向每種模式的訊號。

• 雙指標。已排序輸入、兩數之和、原地分割、迴文檢查。
• 滑動視窗。在限制條件下求最長或最短的連續子陣列。
• 雜湊表計數。字母異位詞、重複元素、頻率比較、第一個不重複元素。
• 二分搜尋。已排序陣列，以及陣列未排序時在答案空間上做二分。
• 廣度優先與深度優先搜尋。樹、網格、連通元件、無權重最短路徑。
• 堆積與優先佇列。前 k 大問題、合併已排序資料流、動態求中位數。
• 區間問題。依起點排序後進行合併、插入與重疊偵測。
• 動態規劃。重疊子問題：爬樓梯、找零錢、編輯距離、子序列問題。
• 回溯。排列、組合、子集合、限制類謎題。
• 圖論演算法。拓撲排序、聯集查找、帶權重最短路徑。

以下是面試官常用措辭給出的代表性題目：

• 在陣列中找到兩個總和為目標值的數，然後不使用額外空間實作。
• 回傳不含重複字元的最長子字串長度。
• 給定一個旋轉排序陣列，在對數時間內找到目標值。
• 合併重疊區間，並說明為什麼排序這一步是值得的。
• 反轉一棵二元樹，然後求出它的最大深度。
• 驗證一棵二元搜尋樹，並說明簡單粗暴的檢查會漏掉什麼。
• 統計網格中島嶼的數量，然後說明當網格大到記憶體放不下時該怎麼處理。
• 找出出現頻率最高的 k 個元素，並說明你選擇該資料結構的理由。
• 計算湊出某個金額所需的最少硬幣數，並寫出遞迴關係式。
• 偵測鏈結串列中是否存在環，然後回傳環的起始節點。
• 對一棵二元樹進行序列化與反序列化。
• 給定課程的先修關係，判斷該課程安排是否可行。

一位應徵後端職缺的社會新鮮人拿到子字串問題後立刻開始打程式。程式碼幾乎是對的，但面試官整場都在追問這段程式在做什麼，最終的評分反映的是這份沉默，而不是那個小 bug。另一位候選人花四十秒說出在字元映射表上滑動視窗，遇到重複就收縮左邊界，同時記錄最大值，就已經通過了最難挽回的那部分。

默默解題會養成錯誤的反射動作。即時面試要求你同時講解與寫程式，這是一項獨立於兩者之一的技能。

要改變的是練習方式，而不是題目本身。動筆之前，先用口語說出模式、思路和預期複雜度。寫程式的同時繼續講解。寫完後再說一次複雜度，並說出一個你已經處理的邊界情況，以及一個你會向面試官確認的邊界情況。用這種方式練十題，比默默刷五十題更能提升面試能力。

一場模擬面試會提供追問環節——這是無法自己練習的部分，還會留下你自己講解過程的錄音供你回顧。這裡有一條始終成立的誠實限制：附監考的瀏覽器內打字測驗不是對話，任何即時助手都不該出現在其中。面試類型總覽說明了哪些程式測驗形式是即時的，哪些是自動評測的。