內容簡介
本書剖析了50個典型的程序員面試題,從基礎知識、代碼質量、解題思路、優化效率和綜合能力五個方面系統整理了影響面試的5個要點。全書分為7章,主要包括面試的流程,討論面試流程中每一環節需要注意的問題;面試需要的基礎知識,從編程語言、數據結構及算法三方面總結了程序員面試的知識點;高質量的代碼,討論影響代碼質量的的3個要素(規范性、完整性和魯棒性),強調高質量的代碼除了能夠完成基本的功能之外,還能考慮到特殊情況并對非法輸入進行合理的處理;解決面試題的思路,總結在編程面試中解決難題的常用思路,如果在面試過程中遇到了復雜的難題,應聘者可以利用畫圖、舉例和分解復雜問題3種方法化繁為簡,先形成清晰的思路再動手編程;優化時間和空間效率,介紹如何優化代碼的時間效率和空間效率,讀完這一章讀者將學會常用的優化時間效率及空間換時間的常用算法,從而在面試中找到最優的解法;面試中的各種能力,本章總結應聘者在面試過程中如何表現學習能力和溝通能力,并通過具體的面試題討論如何培養知識遷移能力、抽象建模能力和發散思維能力;兩個面試案例,這兩個案例總結了應聘者在面試過程中哪些舉動是不好的行為,而哪些表現又是面試官所期待的行為。
本書適合即將走向工作崗位的大學生閱讀,也適合作為正在應聘軟件行業的相關就業人員和計算機愛好者的參考書。
未經許可,不得以任何方式復制或抄襲本書的任何部分。
版權所有,侵權必究。
圖書在版編目(CIP)數據
劍指Offer:名企面試官精講典型編程題/何海濤著.—北京:電子工業出版社,2012.1
ISBN 978-7-121-14875-0
Ⅰ.①劍… Ⅱ.①何… Ⅲ.①程序設計-工程技術人員-資格考試-習題集 Ⅳ.①TP311.1-44
中國版本圖書館CIP數據核字(2011)第215025號
策劃編輯:張春雨
責任編輯:李云靜
特約編輯:趙樹剛
印 刷:北京豐源印刷廠
裝 訂:三河市鵬成印業有限公司
出版發行:電子工業出版社
北京市海淀區萬壽路173信箱 郵編 100036
開 本:787×980 1/16 印張:17.25 字數:354千字
印 次:2012年1月第1次印刷
印 數:4000冊 定價:45.00元
凡所購買電子工業出版社圖書有缺損問題,請向購買書店調換。若書店售缺,請與本社發行部聯系,聯系及郵購電話:(010)88254888。
質量投訴請發郵件至zlts@phei.com.cn,盜版侵權舉報請發郵件至dbqq@phei.com.cn。
服務熱線:(010)88258888。
- 目錄
- 扉頁
- 版權頁
- 推薦序一
- 推薦序二
- 前言
- 第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)樹中兩個結點的最低公共祖先