軟體工程師面試問題

框架: 查找互補值

暴力解會檢查每一組數對，需要 O(n^2) 的時間。比較好的做法是用一個雜湊表，把數值對應到索引。掃描陣列時，對每個數字 x，我們需要的值是 target - x。如果這個互補值已經在雜湊表裡，就回傳目前的索引和表中儲存的索引；否則就把 x 和它的索引存進去，繼續往下掃。 正確性的關鍵在於：處理到索引 i 時，雜湊表裡剛好只有先前索引的值。所以只要有一組有效的數對以 i 結尾，我們就會立刻找到它。而且因為只和前面的元素配對，也不會重複使用同一個元素。 時間複雜度是 O(n)，因為每個值只會插入和查找一次。空間複雜度是 O(n)，用於雜湊表。邊界情況包括重複值、負數、零，以及在題目允許的情況下，找不到任何有效數對。

框架: 滑動視窗搭配最後出現位置

使用滑動視窗，並讓視窗內永遠只包含不重複的字元。維護一個左指標，以及一個記錄每個字元最近一次出現索引的雜湊表。右指標從頭到尾掃過字串。如果目前的字元曾在目前的視窗內出現過，就把左指標移到它前一次出現位置的下一格。接著更新這個字元的索引，並記錄視窗的最大長度。 重要的細節是：左指標只能往前移。如果某個字元上次出現的位置在目前視窗之前，就不應該縮小視窗。這就是為什麼更新式是 left = max(left, lastSeen[char] + 1)。 時間複雜度是 O(n)，因為每個字元只處理一次，而且左指標只會往前移動。空間複雜度是 O(k)，k 是字元集的大小。邊界情況包括空字串、所有字元都不重複、所有字元都重複，以及當程式語言對字元和位元組的處理方式不同時的 Unicode 問題。

框架: 標準化鍵值

字母重組詞的字元組成完全相同。為每個單字建立一個標準化的鍵值，再用雜湊表依照這個鍵值把單字分組。最直接的鍵值，就是把單字的字元排序後的結果。例如「eat」、「tea」和「ate」都會對應到「aet」。 如果字串很短，把每個單字排序既簡單又可靠。如果字母固定只有小寫英文字母，而且字串很長，使用長度 26 的頻率計數元組會更快，因為可以省下每個單字 O(k log k) 的排序成本。 使用排序時，時間複雜度是 O(n * k log k)，n 是字串數量，k 是平均字串長度。改用固定字母表計數，則可以做到 O(n * k)。空間複雜度是 O(n * k)，包含輸出與鍵值。邊界情況包括空字串、重複字串、大小寫規則，以及非英文字元。

框架: 三個指標：previous、current、next

使用三個指標。previous 一開始是 null，current 一開始指向 head。對每個節點，先存下 next = current.next，把 current.next 改指向 previous，再把 previous 移到 current、current 移到 next。當 current 變成 null 時，previous 就是新的 head。 這裡的不變量是：previous 指向已經反轉好的部分，current 指向第一個還沒反轉的節點。在修改 current.next 之前一定要先存下 next，否則串列剩下的部分就會遺失。 時間複雜度是 O(n)，空間複雜度是 O(1)。邊界情況包括空串列、只有一個節點，以及要確保原本的 head 變成尾端，而且它的 next 設為 null。

框架: 範圍限制

常見的錯誤是只檢查每個節點是否大於左子節點、小於右子節點。這樣並不夠，因為整棵子樹都必須滿足祖先節點帶來的限制。 用 DFS 並帶入上下界。對每個節點，驗證 lower < node.value < upper。左子節點沿用相同的下界，並以目前節點的值作為上界；右子節點以目前節點的值作為下界，並沿用相同的上界。只要有任何節點超出它的範圍，就回傳 false。 時間複雜度是 O(n)，因為每個節點只造訪一次。空間複雜度是 O(h)，用於遞迴深度，h 是樹高。邊界情況包括重複值、整數最小值與最大值的邊界、空樹，以及歪斜樹。記得先確認是否允許重複值；如果允許，要確認它們該放在哪一側。

框架: 依距離逐層進行廣度優先搜尋

把每個可通行的格子視為圖中的節點，往上、下、左、右移動則是權重相同的邊。因為每一步的成本都一樣，BFS 就能找出最短路徑。從起點格子開始，以距離 0 放進佇列，並標記為已造訪。每從佇列取出一個格子，就探索它在範圍內、不是障礙物且尚未造訪的相鄰格子。第一次抵達終點時，當下的距離就是最短距離。 正確性來自 BFS 會依照距離遞增的順序處理節點。在無權重圖中，一個格子一旦被造訪過，之後再走到它，都不可能產生更短的路徑。 時間複雜度是 O(rows * cols)，因為每個格子最多造訪一次。空間複雜度是 O(rows * cols)，用於佇列與 visited 集合。邊界情況包括起點或終點被擋住、起點就是終點、沒有路徑，以及是否允許斜向移動。

框架: 用 visited 雜湊表對應原始節點與複製節點

使用一個雜湊表，把每個原始節點對應到它的複製節點。在 DFS 或 BFS 的過程中造訪原始節點時，如果它的複製節點還不存在，就建立一個。接著以遞迴或迭代的方式複製每個相鄰節點，再把複製出來的相鄰節點加進複製節點的鄰接串列。 這個 visited 雜湊表解決了兩個問題：它能避免在有環的圖中陷入無窮迴圈，也能保留共用的參照，讓複製出來的圖和原圖有相同的拓撲結構。 時間複雜度是 O(V + E)，V 是節點數，E 是邊數。空間複雜度是 O(V)，用於雜湊表以及走訪用的堆疊或佇列，不含輸出的圖。邊界情況包括 null 輸入、自環、題目只要求從起始節點開始複製時的非連通圖，以及鄰接串列中重複出現的相鄰節點。

框架: 針對金額由下而上的 DP

定義 dp[a] 為湊出金額 a 所需的最少硬幣數。初始化 dp[0] = 0，其他值都設為無限大。對 1 到目標金額之間的每個金額，嘗試每一種硬幣。如果 a - coin 不是負數，就令 dp[a] = min(dp[a], dp[a - coin] + 1)。最後如果 dp[target] 仍然是無限大，就回傳 -1。 這個遞迴關係式之所以成立，是因為最佳解中的最後一枚硬幣一定是其中一種面額。如果最後一枚硬幣的面額是 c，剩下的金額就是 target - c，而這部分同樣應該取最佳解。 時間複雜度是 O(金額 * 硬幣種類數)，空間複雜度是 O(金額)。邊界情況包括金額為 0、無法湊出的金額、面額為 1 的硬幣、重複的面額，以及很大的目標金額。

框架: 以結尾位置定義 DP，再用二分搜尋最佳化

清楚的 DP 解法是定義 dp[i] 為以索引 i 結尾的最長遞增子序列長度。對每個 i，檢查所有在它之前的 j。如果 nums[j] < nums[i]，nums[i] 就能接在以 j 結尾的子序列後面，所以 dp[i] = max(dp[i], dp[j] + 1)。答案是 max(dp)。這需要 O(n^2) 的時間與 O(n) 的空間。 最佳化後的 O(n log n) 做法會維護一個 tails 陣列，其中 tails[length - 1] 是長度為 length 的遞增子序列所能有的最小結尾值。對每個數字，用二分搜尋找出第一個大於或等於它的 tail，並把它替換掉。tails 的長度就是 LIS 的長度。 面試時如果時間有限，先提出 O(n^2) 的 DP 解法，再討論最佳化版本，是很合理的做法。邊界情況包括重複值、遞減陣列、空輸入，以及子序列是否必須嚴格遞增。

框架: 只建立合法的前綴

使用回溯，並記錄兩個計數：已用的左括號數 open 與已用的右括號數 close。每一步只要 open < n，就可以加入左括號；只要 close < open，就可以加入右括號。第二個條件確保每個前綴都維持合法，所以永遠不會產生需要事後過濾的不合法字串。 當目前字串的長度達到 2n 時，就把它加入結果。這樣只會探索合法的前綴，並及早剪掉不可能的狀態。 合法輸出的數量是第 n 個卡特蘭數，所以執行時間主要取決於輸出的大小。空間複雜度包含 O(n) 的遞迴深度，再加上輸出。邊界情況依題目定義而定，包括 n = 0 或 n = 1。

框架: 需求 → API → ID 產生 → 儲存 → 重新導向路徑 → 擴展

需求：使用者提交一個長網址，取得一個短網址。有人造訪短網址時，要能快速重新導向。選配功能包括自訂別名、到期時間、流量分析、垃圾訊息偵測與使用者帳號。 核心 API：createShortUrl(longUrl, optionalAlias, expiration) 與 redirect(shortCode)。資料模型：shortCode、longUrl、userId、createdAt、expiresAt、status，必要時再加上分析用的中繼資料。 ID 產生的選項包括：以 base62 編碼的自動遞增 ID、搭配碰撞檢查的隨機 base62 短碼，或分散式 ID 產生。自動遞增很簡單，但除非經過混淆，否則會洩漏資料量。隨機 ID 容易分散產生，但需要處理碰撞。在中等規模下，隨機 base62 搭配資料庫的唯一性限制就足夠了。 讀取路徑最重要。重新導向必須夠快：先從快取讀取 shortCode，沒有命中再查資料庫，驗證到期時間與狀態，然後回傳 HTTP 301 或 302。如果在意流量分析，或目的地可能會變更，就用 302；如果是永久重新導向、希望瀏覽器更積極地快取，就用 301。 擴展：把熱門短碼快取在 Redis 或邊緣快取中，必要時依 shortCode 分片，透過佇列非同步儲存分析資料，對建立短網址做速率限制，並執行垃圾訊息與惡意軟體檢查。監控重新導向延遲、快取命中率、錯誤率、濫用檢舉與資料庫飽和度。

框架: 使用者 → 貼文 → fanout → 排序 → 讀取 → 一致性

先釐清動態消息的類型：社群追蹤型、推薦型，還是混合型。假設是追蹤型動態消息：使用者發布貼文，追蹤者依照相關性或時間順序看到這些貼文。 核心物件：使用者、追蹤關係、貼文、媒體、動態項目、按讚與留言，以及排序特徵。API 包括 createPost、getFeed、followUser、unfollowUser 與 interactWithPost。 常見的動態產生模型有兩種。Fanout-on-write 會在貼文建立時，把新貼文推送到每位追蹤者的動態儲存區。這讓讀取很快，但對追蹤者很多的使用者來說，寫入成本很高。Fanout-on-read 則是在收到請求時，才從追蹤對象抓取貼文來計算動態。這讓寫入成本很低，但讀取比較慢。常見的做法是混合式：一般使用者用 fanout-on-write，名人帳號則用 fanout-on-read 或特殊處理。 架構：貼文服務負責寫入貼文，關係圖服務儲存追蹤關係，動態服務維護動態時間軸，排序服務為候選貼文評分，快取存放熱門動態，媒體則放到物件儲存與 CDN。用佇列處理非同步的 fanout 與排序更新。 取捨：動態新鮮度與排序品質、追蹤關係變更的一致性、名人帳號的處理、快取失效、垃圾訊息、隱私封鎖，以及佇列故障後的資料回補。監控動態載入延遲、新鮮度、fanout 延遲、互動率、快取命中率、排序錯誤與濫用檢舉。

框架: 連線 → 訊息流程 → 持久化 → 送達 → 可靠性

需求：一對一與群組訊息、線上送達、離線送達、訊息紀錄、已讀回條、輸入中提示與推播通知。也要確認是否需要端對端加密、附件與多裝置同步。 用戶端會與閘道服務維持 WebSocket 連線。使用者傳送訊息時，閘道會先驗證身分，指派或接收一個冪等鍵（idempotency key），把訊息寫入持久儲存，發布事件，再透過線上收件者的有效連線把訊息送達。離線使用者會收到推播通知，之後可以再拉取訊息紀錄。 資料模型：對話、參與者、訊息、送達狀態、已讀狀態，以及裝置與工作階段。儲存層必須能依對話與時間有效率地讀取。中等規模下用關聯式資料庫就可以；規模更大時，則會改用分散式儲存。附件應該放在物件儲存，而不是訊息資料庫。 可靠性的考量：重複傳送、訊息順序錯亂、重新連線、遺漏訊息、大型群組的 fanout，以及上線狀態的準確性。使用冪等鍵、每個對話單調遞增的序號、確認回應（ACK）、重試邏輯，以及「從上次看到的位置開始同步」的 API。 監控訊息傳送延遲、送達成功率、WebSocket 連線數、重新連線率、佇列延遲、推播通知失敗與儲存寫入錯誤。

框架: 確認訊號 → 界定範圍 → 近期變更 → 拆解相依服務 → 緩解

首先確認訊號是真的。檢查延遲上升是否同時出現在多個監控系統中，以及影響的是 p50、p95、p99，還是只有某個特定端點。也要確認使用者是否真的感受得到。 接著界定問題範圍：依端點、區域、可用區域、客群、版本、主機、相依服務與請求類型逐一切分。如果是全面性上升，代表可能是共用的相依服務或某次部署出了問題；如果只集中在小範圍，則指向特定路由、查詢、客戶或基礎架構區域。 然後檢查近期的變更：部署、設定變更、資料庫遷移、流量高峰、feature flag、快取變更，或下游服務的事故。用 trace 依服務 span 拆解延遲。檢查資料庫查詢時間、快取命中率、佇列延遲、CPU、記憶體、垃圾回收、執行緒池、連線池與外部 API。 如果使用者已經受到影響，先緩解，再追求完美的根本原因。可以 rollback、關閉 feature flag、擴充容量、繞過緩慢的相依服務，或在安全的前提下延長快取 TTL。恢復之後，寫下根本原因、偵測上的缺口與預防計畫。

框架: 單元測試案例 → 臨界值 → 無效輸入 → 不變量

我會先釐清規則：折扣類型、能不能疊加、到期時間、最低消費、使用者資格、金額的四捨五入，以及是否包含稅金或運費。 單元測試應該涵蓋一般情況、臨界值、無效輸入，以及規則之間的交互作用。例如：沒有折扣、百分比折扣、固定金額折扣、折扣大於小計、剛好達到最低消費、差一點沒達到最低消費門檻、折扣已過期、使用者不符資格、允許的話測試多重折扣，以及以「分」為單位的四捨五入。 我也會測試不變量：最終價格永遠不能是負數、折扣不能超過符合條件的小計、過期的促銷不應該套用，而且重複計算的結果必須一致。如果這牽涉到付款，我會再加上與定價服務的整合測試，以及針對發票輸出的快照測試。 為了正式環境的安全，我會用原因代碼記錄每一次的折扣判斷，這樣客服和工程團隊在處理價格客訴時，就能直接診斷，而不必用猜的。

框架: 正確性 → 可維護性 → 風險 → 清晰度

我會分層來做 code review。第一，它有沒有解決原本要解決的問題，並且維持正確性？第二，它好不好維護：命名是否清楚、邊界劃分是否合理、有沒有不必要的複雜度、風格是否一致？第三，風險在哪裡：資料庫遷移、並行處理、資安、效能、向下相容與可觀測性？第四，測試是否足以涵蓋這次變更的行為？ 好的 code review 不是為了顯示自己比較厲害，而是要在維持團隊開發速度的同時，讓程式碼變得更好。我會把會擋下合併（blocking）的問題和單純的建議分開。正確性 bug、資安問題或資料庫遷移風險屬於 blocking；命名偏好或小幅重構，則可以是 non-blocking。 我也會留意缺少的脈絡：產品行為不明確、沒測到的邊界情況、靜默失敗的路徑、薄弱的錯誤處理，以及高風險的變更缺乏指標監控。

框架: 背景 → 選項 → 取捨 → 決策 → 結果

選一個真的有取捨的決策：自建還是外購、SQL 還是 NoSQL、單體架構還是拆成服務、快速修補還是深入重構，或是強一致性還是可用性。先說明背景與限制條件，再說明你考慮過哪些選項。 好的回答會把取捨講清楚。例如：「方案 A 讓我們一週內就能上線，但會增加維運負擔；方案 B 要花三週，但能消除擴展上的瓶頸。」接著說明是哪些證據促成了這個決定：流量、客戶的期限、過去的事故紀錄、團隊人力，或長期的 roadmap。 最後說明結果和你學到的東西。如果這個決策並不完美，就說出你會怎麼做得不一樣。比起假裝每個決策都理所當然，面試官更看重成熟的判斷力。

框架: 事故 → 影響 → 應變 → 根本原因 → 預防

盡可能用真實發生過的事故。先從對使用者的影響談起：什麼東西壞了、影響到誰、嚴重程度如何。接著說明你在應變中扮演的角色：偵測、分級處理（triage）、rollback、緩解、溝通，或根本原因分析。 最好的回答會展現冷靜的優先順序判斷。事故發生時，恢復服務比證明某個推論更重要。說明你如何運用 log、指標、trace、feature flag、rollback 或相依服務檢查。 緩解之後，說明根本原因與預防措施。好的預防措施可能包括更完善的測試、更安全的上線方式、監控、警示調校、runbook、circuit breaker、backpressure，或資料庫遷移的防護機制。避免怪罪個人。強大的團隊會改善系統，讓同樣的錯誤更難再次發生。

框架: 共同目標 → 限制條件 → 選項 → 取捨 → 決策

我會先和對方對齊使用者目標與商業目標。很多分歧其實不是工程和產品之間的對立，而是彼此的假設不同。我會清楚說明技術上的限制：複雜度、可靠性風險、時程、可維護性、資安或效能。 接著我會提出替代方案，而不是只說不行。例如：先推出規模較小的 MVP、暫時用人工流程處理、把功能藏在 feature flag 後面、把技術工作分階段進行，或選擇一個更簡單、但仍能解決使用者核心問題的設計。 如果取捨影響重大，我會把各個選項、風險和我的建議整理成文件，讓決策過程透明。目標不是讓工程這一方贏，而是讓團隊在充分了解狀況的前提下，做出明確的決定。