前 言
2011年9月份以來,我的面試題博客(http://zhedahht.blog.163.com/)點擊率上升很快,累計點擊量超過了70萬,并且平均每天還會增加約3000次點擊。每一年隨著秋季新學期的開始,新一輪招聘高峰也即將來到。這不禁讓我想起幾年前自己找工作的情形。那個時候的我,也是在網絡的各個角落搜索面試經驗,盡可能多地收集各個公司的面試題。
當時網上的面試經驗還很零散,應聘者如果想系統地收集面試題,需要付出很大的努力。于是我萌生了一個念頭,在博客上系統地收集、整理有代表性的面試題,這樣可以極大地方便后來人。經過一段時間的準備,我于2007年2月在網易博客上發表了第一篇關于編程面試題的博客。
在過去4年多的日子里,我陸續發表了60余篇關于面試題的博客。隨著博客數目的增加,我也逐漸意識到一篇篇博客仍然是零散的。一篇博客只是單純地分析一個面試題,但對解題思路缺乏系統性的梳理。于是在2010年10月我有了把博客整理成一本書的想法。經過一年的努力,這本書終于和讀者見面了。
本書內容
全書分為7章,各章的主要內容如下:
第1章介紹面試的流程。通常整個面試過程可以分為電話面試、共享桌面遠程面試和現場面試3個階段,每一輪面試又可以分為行為面試、技術面試和應聘者提問3個環節。本章詳細討論了面試中每一環節需要注意的問題。其中第1.3.2節深入討論了技術面試中的5個要素,是全書的大綱,接下來的第2~6章逐一討論每個要點。
第2章梳理應聘者接受技術面試時需要用到的基礎知識。本章從編程語言、數據結構及算法三方面總結了程序員面試的知識點。
第3章討論應聘者在面試時寫出高質量代碼的3個要點。通常面試官除了期待應聘者寫出的代碼能夠完成基本的功能之外,還能應對特殊情況并對非法輸入進行合理的處理。讀完這一章,讀者將學會如何從規范性、完整性和魯棒性3個方面提高代碼的質量。
第4章總結在編程面試中解決難題的常用思路。如果在面試過程中遇到復雜的難題,應聘者最好在寫代碼之前形成清晰的思路。讀者在讀完這一章之后將學會如何用畫圖、舉例和分解復雜問題3種思路來解決問題。
第5章介紹如何優化代碼的時間效率和空間效率。如果一個問題有多種解法,面試官總是期待應聘者能找到最優的解法。讀完這一章,讀者將學會優化時間效率及空間換時間的常用算法。
第6章總結面試中的各項能力。面試官在面試過程中會一直關注應聘者的學習能力和溝通能力。除此之外,有些面試官還喜歡考查應聘者的知識遷移能力、抽象建模能力和發散思維能力。讀完這一章,讀者將學會如何培養和運用這些能力。
第7章是兩個面試的案例。在這兩個案例中,我們將看到應聘者在面試過程中的哪些舉動是不好的行為,而哪些表現又是面試官所期待的行為。衷心地希望應聘者能在面試時少犯甚至不犯錯誤,完美地表現出自己的綜合素質,最終拿到心儀的Offer。
本書特色
正如前面提到的那樣,本書的原型是我過去4年多陸陸續續發表的幾十篇博客,但這本書也不僅僅是這些博客的總和,它在博客的基礎上添加了如下內容。
本書試圖以面試官的視角來剖析面試題。本書前6章的第一節都是“面試官談面試”,收錄了分布在不同IT企業(或者IT部門)的面試官們對代碼質量、應聘者如何形成及表達解題思路等方面的理解。在本書中穿插著幾十條“面試小提示”,是我作為面試官給應聘者在面試方法、技巧方面的建議。在第7章的案例中,“面試官心理”揭示了面試官在聽到應聘者不同回答時的心理活動。應聘者如果能了解面試官的心理活動,無疑能在面試時更好地表現自己。
本書總結了解決面試難題的常用方法,而不僅僅只是解決一道道零散的題目。在仔細分析、解決了幾十道典型的面試題之后,我發現其實是有一些通用的方法可以在面試的時候幫助我們解題的。舉個例子,如果面試的時候遇到的題目很難,我們可以試圖把一個大的復雜的問題分解成若干個小的簡單的子問題,然后遞歸地去解決這些子問題。再比如,我們可以用數組實現一個簡單的哈希表解決一系列與字符串相關的面試題。在詳細分析了一道面試題之后,很多章節都會在“相關題目”中列舉出同類型的面試題,并在“舉一反三”中總結解決這一類型題目的方法和要點。
本書收集的面試題是都是各大公司的編程面試題,極具實戰意義。包括谷歌、微軟在內的知名IT企業在招聘的時候,都非常重視應聘者的編程能力,編程技術面試也是整個面試流程中最為重要的一個環節。本書選取的題目都是被各大公司面試官反復采用的編程題。如果讀者一開始覺得書中的有些題目比較難,那也正常,沒有必要感到氣餒,因為像谷歌、微軟這樣的大企業的面試本身就不簡單。讀者逐步掌握了書中總結的解題方法之后,編程能力和分析復雜問題的能力將會得到很大的提升,再去大公司面試將會輕松很多。
本書附帶提供了50道編程題的完整的源代碼,其中包含了每道題的測試用例。很多面試官在應聘者寫完程序之后,都會要求應聘者自己想一些測試用例來測試自己的代碼,一些沒有實際項目開發經驗的應聘者不知道如何做單元測試。相信讀者朋友在讀完這本書之后就會知道如何從基本功能測試、邊界值測試、性能測試等方面去設計測試用例,從而提高編寫高質量代碼的能力。
本書體例
在本書的正文中間或者章節的末尾,穿插了不少特殊體例。這些體例或用來給應聘者提出建議,或用來總結解題方法,希望能夠引起讀者的注意。
面試小提示:
本條目是從面試官的角度對應聘者的建議或者希望應聘者能夠注意到的細節。
源代碼:
讀者將在本條目中看到一個格式為XX\_YYYYY或者XX\_Y\_ZZZZZ的項目名稱,該名稱與用Visual Studio打開文件InterviewQuestions.sln之后看到的項目名稱對應。本書附帶的源代碼請到電子工業出版社的官方網站下載。讀者下載源代碼并解壓縮之后,請用Visual Studio 2008或者更新的版本閱讀或者運行代碼。
測試用例:
本條目列舉應聘者在面試時可以用來測試代碼是否完整、魯棒的單元測試用例。通常本書從基本功能、邊界值、無效的輸入等方面測試代碼的完整性和魯棒性,針對在時間效率或者空間效率有要求的面試題還包含性能測試的測試用例。
本題考點:
本條目總結面試官采用一道面試題的考查要點。
相關題目:
本條目列舉一些和詳細分析的面試例題相關或者類似的面試題。
舉一反三:
本條目從解決面試例題中提煉出常用的解題方法。這些解題方法能夠應用到解決其他同類型的問題中去,達到舉一反三的目的。
面試官心理:
在第七章的面試案例中,本條目用來模擬面試官聽到應聘者的回答之后的心理活動。
關于遺漏的問題
由于時間倉促,再加上筆者的能力有限,書中難免會有一些遺漏。今后一旦發現遺漏的問題,我將第一時間在博客(http://zhedahht.blog.163.com/)上公布勘誤信息。讀者如果發現任何問題或者有任何建議,也請在博客上留言、評論,或者通過微博(http://weibo.com/zhedahht)和我聯系。
致謝
在寫博客及把博客整理成書的過程中,我得到了很多人的幫助。沒有他們,也就沒有這本書。因此,我想在這里對他們誠摯地說一聲:謝謝!
首先我要謝謝個人博客上的讀者。網友們的鼓勵讓我在博客上的寫作從2007年2月開始堅持到了現在。也正是由于網友們的鼓勵,我最終下定決心把博客整理成一本書。
在本書的寫作過程中,我得到了很多同學、同事的幫忙,包括Autodesk的馬凌洲、劉景勇、王海波,支付寶殷焰,百度的張珺、張曉禹,Intel的尹彥,交通銀行的朱麟,淘寶的堯敏,微軟的陳黎明、田超,NVidia的吳斌,SAP的何幸杰和華為的韓偉東(在書稿寫作階段他還在盛大工作)。感謝他們和大家分享了對編程面試的理解和思考。同時還要感謝GlaxoSmithKline Investment的Recruitment & HRIS Manager蔡詠來(也是2008年把我招進微軟的HR)和大家分享了微軟所推崇的STAR簡歷模型。還要感謝在微軟期間我的兩個老板徐鵬陽和Matt Gibbs,他們都是在微軟有十幾年面試經驗的資深面試官,對面試有著深刻的理解。感謝二位在百忙之中抽時間為本書寫序,為本書增色不少。
我同樣要感謝現在思科的老板Min Lu及TQSG上海團隊的同事王劦、趙斌和朱波對我的理解。他們在我寫作期間替我分擔了大量的工作,讓我能夠集中更多的精力來寫書。
感謝電子工業出版社的工作人員,尤其是張春雨和趙樹剛的幫助。兩位編輯大到全書的構架,小到文字的推敲,都給予了我極大的幫助,從而使本書的質量有了極大的提升。
本書還得到了很多朋友的支持和幫助,限于篇幅,雖然不能在此一一說出他們的名字,但我一樣對他們心存感激。
最后,我要衷心地感謝我的愛人劉素云。感謝她在過去一年中對我的理解和支持,為我營造了一個溫馨而又浪漫的家,讓我能夠心無旁騖地寫書。我無以為謝,謹以此書獻給她及我們尚未出生的小寶寶。
何海濤
2011年9月8日清晨于上海三涇南宅
- 目錄
- 扉頁
- 版權頁
- 推薦序一
- 推薦序二
- 前言
- 第1章 面試的流程
- 1.1 面試官談面試
- 1.2 面試的三種形式
- 1.2.1 電話面試
- 1.2.2 共享桌面遠程面試
- 1.2.3 現場面試
- 1.3 面試的三個環節
- 1.3.1 行為面試環節
- 1.應聘者的項目經驗
- 2.應聘者掌握的技能
- 3.回答“為什么跳槽”
- 1.3.2 技術面試環節
- 1.扎實的基礎知識
- 2.高質量的代碼
- 3.清晰的思路
- 4.優化效率的能力
- 5.優秀的綜合能力
- 1.3.3 應聘者提問環節
- 1.4 本章小結
- 第2章 面試需要的基礎知識
- 2.1 面試官談基礎知識
- 2.2 編程語言
- 2.2.1 C++
- 面試題1:賦值運算符函數
- 經典的解法,適用于初級程序員
- 考慮異常安全性的解法,高級程序員必備
- 2.2.2 C#
- 面試題2:實現Singleton模式
- 不好的解法一:只適用于單線程環境
- 不好的解法二:雖然在多線程環境中能工作但效率不高
- 可行的解法:加同步鎖前后兩次判斷實例是否已存在
- 強烈推薦的解法一:利用靜態構造函數
- 強烈推薦的解法二:實現按需創建實例
- 解法比較
- 2.3 數據結構
- 2.3.1 數組
- 面試題3:二維數組中的查找
- 2.3.2 字符串
- 面試題4:替換空格
- 時間復雜度為O(n2)的解法,不足以拿到Offer
- 時間復雜度為O(n)的解法,搞定Offer就靠它了
- 2.3.3 鏈表
- 面試題5:從尾到頭打印鏈表
- 2.3.4 樹
- 面試題6:重建二叉樹
- 2.3.5 棧和隊列
- 面試題7:用兩個棧實現隊列
- 2.4 算法和數據操作
- 2.4.1 查找和排序
- 面試題8:旋轉數組的最小數字
- 2.4.2 遞歸和循環
- 面試題9:斐波那契數列
- 效率很低的解法,挑剔的面試官不會喜歡
- 面試官期待的實用解法
- 時間復雜度O(logn)但不夠實用的解法
- 解法比較
- 2.4.3 位運算
- 面試題10:二進制中1的個數
- 可能引起死循環的解法
- 常規解法
- 能給面試官帶來驚喜的解法
- 2.5 本章小結
- 第3章 高質量的代碼
- 3.1 面試官談代碼質量
- 3.2 代碼的規范性
- 3.3 代碼的完整性
- 1.從3方面確保代碼的完整性
- 2.3種錯誤處理的方法
- 面試題11:數值的整數次方
- 自以為題目簡單的解法
- 全面但不夠高效的解法,我們離Offer已經很近了
- 全面又高效的解法,確保我們能拿到Offer
- 面試題12:打印1到最大的n位數
- 跳進面試官陷阱
- 在字符串上模擬數字加法的解法,繞過陷阱才能拿到Offer
- 把問題轉換成數字排列的解法,遞歸讓代碼更簡潔
- 面試題13:在O(1)時間刪除鏈表結點
- 面試題14:調整數組順序使奇數位于偶數前面
- 只完成基本功能的解法,僅適用于初級程序員
- 考慮可擴展性的解法,能秒殺Offer
- 3.4 代碼的魯棒性
- 面試題15:鏈表中倒數第k個結點
- 面試題16:反轉鏈表
- 面試題17:合并兩個排序的鏈表
- 面試題18:樹的子結構
- 3.5 本章小結
- 第4章 解決面試題的思路
- 4.1 面試官談面試思路
- 4.2 畫圖讓抽象問題形象化
- 面試題19:二叉樹的鏡像
- 面試題20:順時針打印矩陣
- 4.3 舉例讓抽象問題具體化
- 面試題21:包含min函數的棧
- 面試題22:棧的壓入、彈出序列
- 面試題23:從上往下打印二叉樹
- 面試題24:二叉搜索樹的后序遍歷序列
- 面試題25:二叉樹中和為某一值的路徑
- 4.4 分解讓復雜問題簡單化
- 面試題26:復雜鏈表的復制
- 面試題27:二叉搜索樹與雙向鏈表
- 面試題28:字符串的排列
- 4.5 本章小結
- 第5章 優化時間和空間效率
- 5.1 面試官談效率
- 5.2 時間效率
- 面試題29:數組中出現次數超過一半的數字
- 解法一:基于Partition函數的O(n)算法
- 解法二:根據數組特點找出O(n)的算法
- 解法比較
- 面試題30:最小的k個數
- 解法一:O(n)的算法,只有當我們可以修改輸入的數組時可用
- 解法二:O(nlogk)的算法,特別適合處理海量數據
- 解法比較
- 面試題31:連續子數組的最大和
- 解法一:舉例分析數組的規律
- 解法二:應用動態規劃法
- 面試題32:從1到n整數中1出現的次數
- 不考慮時間效率的解法,靠它想拿Offer有點難
- 從數字規律著手明顯提高時間效率的解法,能讓面試官耳目一新
- 面試題33:把數組排成最小的數
- 5.3 時間效率與空間效率的平衡
- 面試題34:丑數
- 逐個判斷每個整數是不是丑數的解法,直觀但不夠高效
- 創建數組保存已經找到的丑數,用空間換時間的解法
- 面試題35:第一個只出現一次的字符
- 面試題36:數組中的逆序對
- 面試題37:兩個鏈表的第一個公共結點
- 5.4 本章小結
- 第6章 面試中的各項能力
- 6.1 面試官談能力
- 6.2 溝通能力和學習能力
- 1.溝通能力
- 2.學習能力
- 3.善于學習、溝通的人也善于提問
- 6.3 知識遷移能力
- 面試題38:數字在排序數組中出現的次數
- 面試題39:二叉樹的深度
- 需要重復遍歷結點多次的解法,簡單但不足以打動面試官
- 每個結點只遍歷一次的解法,正是面試官喜歡的
- 面試題40:數組中只出現一次的數字
- 面試題41:和為s的兩個數字VS和為s的連續正數序列
- 面試題42:翻轉單詞順序VS左旋轉字符串
- 6.4 抽象建模能力
- 面試題43:n個骰子的點數
- 解法一:基于遞歸求骰子點數,時間效率不夠高
- 解法二:基于循環求骰子點數,時間性能好
- 面試題44:撲克牌的順子
- 面試題45:圓圈中最后剩下的數字
- 經典的解法,用環形鏈表模擬圓圈
- 創新的解法,拿到Offer不在話下
- 6.5 發散思維能力
- 面試題46:求1+2+…+n
- 解法一:利用構造函數求解
- 解法二:利用虛函數求解
- 解法三:利用函數指針求解
- 解法四:利用模板類型求解
- 面試題47:不用加減乘除做加法
- 面試題48:不能被繼承的類
- 常規的解法:把構造函數設為私有函數
- 新奇的解法:利用虛擬繼承,能給面試官留下很好的印象
- 6.6 本章小結
- 第7章 兩個面試案例
- 7.1 案例一:(面試題49)把字符串轉換成整數
- 7.2 案例二:(面試題50)樹中兩個結點的最低公共祖先