Moderate • 破解程式面試

概述#

Chapter 16 包含 26 道中等難度的程式設計題目，涵蓋數學運算、字串處理、幾何計算、資料結構設計、陣列操作等多個領域。這些題目不需要特別進階的演算法知識，但需要清晰的思路與對邊界條件的謹慎處理。

本章題目難度介於基礎與困難之間，適合作為熱身練習或面試中段的評量題目。

16.2 Word Frequencies：設計方法找出某個字詞在書本中出現的頻率；若演算法需多次執行，如何最佳化？
16.8 English Int：給定任意整數，輸出對應的英文描述，例如 “One Thousand, Two Hundred Thirty Four”。
16.18 Pattern Matching：給定由 a 與 b 組成的 pattern 字串，判斷 value 字串是否符合此 pattern。
16.20 T9：舊式手機數字鍵盤輸入法——給定一串數字，回傳所有可能匹配的有效英文單字。

16.4 Tic Tac Win：設計演算法判斷井字遊戲是否有人獲勝。
16.15 Master Mind：實作猜色遊戲（Master Mind），給定猜測與答案，回傳「正確位置」與「顏色存在但位置錯誤」的數量。
- 電腦有 4 個槽，每個槽可放紅（R）、黃（Y）、綠（G）、藍（B）。
- 猜中正確顏色與位置得一個「hit」；顏色存在但位置錯誤得一個「pseudo-hit」。
16.22 Langton’s Ant：模擬 Langton’s Ant 在無限棋盤上的前 K 步，最後印出棋盤狀態。
- 在白格：翻色、右轉 90 度、前進一格。
- 在黑格：翻色、左轉 90 度、前進一格。

16.6 Smallest Difference：給定兩個整數陣列，找出各取一個元素後差值最小（非負）的配對。
- 範例：Input {1,3,15,11,2}, {23,127,235,19,8} → Output: 3，即 (11, 8)
16.10 Living People：給定一份人口清單（含出生年與死亡年），找出 1900–2000 年間同時在世人數最多的年份。
16.11 Diving Board：使用 K 塊木板（長度為 shorter 或 longer），產生所有可能的跳水板總長度。
16.16 Sub Sort：找出陣列中的子陣列索引範圍 [m, n]，使得排序此子陣列後整體陣列即排序完成，且使 n - m 最小。
- 範例：Input 1,2,4,7,10,11,7,12,6,7,16,18,19 → Output: (3, 9)
16.17 Contiguous Sequence：給定正負整數混合的陣列，找出總和最大的連續子陣列，回傳其總和。
- 範例：Input 2,-8,3,-2,4,-10 → Output: 5（即 {3,-2,4}）
16.19 Pond Sizes：給定整數矩陣代表地形高度，0 表示水域，水域相連（含斜角）形成池塘，計算所有池塘的大小。
16.21 Sum Swap：給定兩個整數陣列，找出各自一個元素，交換後使兩陣列總和相等。
- 範例：Input {4,1,2,1,1,2} 與 {3,6,3,3} → Output: {1, 3}
16.24 Pairs with Sum：設計演算法找出陣列中所有總和等於指定值的整數配對。

16.12 XML Encoding：將 XML 依據預定義的標籤對整數映射進行壓縮編碼。
- 例如：family→1, person→2, firstName→3, lastName→4, state→5
- <family lastName="McDowell" state="CA"><person firstName="Gayle">Some Message</person></family> 編碼為 1 4 McDowell 5 CA 0 2 3 Gayle 0 Some Message 0 0
16.25 LRU Cache：設計並實作「最近最少使用」快取，支援 key-value 存取，容量滿時淘汰最久未使用的項目。
16.26 Calculator：給定由正整數與 +、-、*、/ 組成的算術算式（無括號），計算結果。
- 範例：Input 2*3+5/6*3+15 → Output: 23.5

解題時注意：許多 Moderate 題目的關鍵在於選擇正確的資料結構（如 hash map 加速查找）以及仔細處理邊界條件（如負數、空陣列、零值）。