編程之美--微軟技術面試心得

第1章 遊戲之樂--遊戲中碰到的題目
1.1 讓CPU佔用率曲線聽你指揮
1.2 中國象棋將帥問題
1.3 一摞烙餅的排序
1.4 買書問題
1.5 快速找出故障機器
1.6 飲料供貨
1.7 光影切割問題
1.8 小飛的電梯調度演算法
1.9 高效率地安排見面會
1.10 雙執行緒高效下載
1.11 NIM（1）一排石頭的遊戲
1.12 NIM（2）“拈”遊戲分析
1.13 NIM（3）兩堆石頭的遊戲
1.14 連連看遊戲設計
1.15 構造數獨
1.16 24點遊戲
1.17 俄羅斯方塊遊戲
1.18 挖雷遊戲

第2章 數位之魅--數位中的技巧
2.1 求二進位數字中1的個數
2.2 不要被階乘嚇倒
2.3 尋找發帖“水王”
2.4 1的數目
2.5 尋找最大的K個數
2.6 精確表達浮點數
2.7 最大公約數問題
2.8 找符合條件的整數
2.9 斐波那契（Fibonacci）數列
2.10 尋找陣列中的最大值和最小值
2.11 尋找最近點對
2.12 快速尋找滿足條件的兩個數
2.13 子陣列的最大乘積
2.14 求陣列的子陣列之和的最大值
2.15 子陣列之和的最大值（二維）
2.16 求陣列中最長遞增子序列
2.17 陣列迴圈移位元
2.18 陣列分割
2.19 區間重合判斷
2.20 程式理解和時間分析
2.21 只考加法的面試題

第3章 結構之法--字串及鏈表的探索
3.1 字串移位元包含的問題
3.2 電話號碼對應英語單詞
3.3 計算字串的相似度
3.4 從無頭單鏈表中刪除節點
3.5 最短摘要的生成
3.6 程式設計判斷兩個鏈表是否相交
3.7 佇列中取最大值操作問題
3.8 求二叉樹中節點的最大距離
3.9 重建二叉樹
3.10 分層遍歷二叉樹
3.11 程式改錯

第4章 數學之趣--數學遊戲的樂趣
4.1 金剛坐飛機問題
4.2 瓷磚覆蓋地板
4.3 買票找零
4.4 點是否在三角形內
4.5 磁帶檔存放優化
4.6 桶中取黑白球
4.7 螞蟻爬杆
4.8 三角形測試用例
4.9 數獨知多少
4.10 數字啞謎和回文
4.11 挖雷遊戲的概率

我在卡內基梅隆大學畢業找工作的時候，經常和其他同學一起交流面試的經驗。當時令求職者“聞面色變”的公司有微軟，研究所有DEC 的SRC。每次有同學去微軟或SRC面試，回來的時候都會被其他同學追問有沒有什麼有趣的面試題。我也是那時第一次聽說“下水道井蓋為什麼是圓的”這一問題。

我自己申請加入微軟美國研究院時被面試了兩天，見了15 個人，感覺壓力很大。至今還記得當有一位面試者不斷追問我論文中一個演算法的收斂性時，我們進行了熱烈討論。

在微軟工作的十幾年中，我自己也面試了非常多的新員工。特別在微軟亞洲研究院的9年，經常感覺很多剛剛畢業的優秀學生基礎很好，但面試的準備不足。我非常欣慰地看到鄒欣工程師和微軟亞洲研究院其他同事們努力編寫了這本好書，和大家一起分享微軟的面試心得和程式設計技巧。相信更多的同學會因此成為“筆霸”、“面霸”，甚至“offer 霸”。

程式雖然很難寫，卻很美妙。要想把程式寫好，需要學好一定的基礎知識，包括程式設計語言、資料結構和演算法。程式寫得好的人通常都有縝密的邏輯思維能力和良好的數理基礎，而且熟悉程式設計環境和程式設計工具。古人說“見文如見人”， 我覺得程式同樣也能反映出一個人的功力和風格，好的程式讀來非常賞心悅目。

程式設計很艱苦，但是很有趣。本書的作者們從遊戲中遇到的程式設計問題談起，介紹了數位和字串中的很多技巧，探索了資料結構的竅門，還發掘了數學遊戲的樂趣。我希望讀者在閱讀本書時能找到程式設計的快樂，欣賞到程式設計之美。

本書適合電腦學院、軟體學院、資訊學院高年級本科生、研究生作為軟體發展的參考教材，也是程式師繼續進修的優秀閱讀材料，更是每位申請微軟公司和其他公司軟體工程師之職的面試必讀秘笈。

人類的生活因為優秀的程式師和美妙的程式而變得更加美好。

——沈向洋 微軟公司傑出工程師， 微軟公司全球資深副總裁
2008 年春節於香港