程序員面試手冊：概念、編程問題及面試題 ( 簡體 字) |
| 作者：[印] 納拉辛哈·卡魯曼希（Narasimha Karumanchi） 著 | 類別：1. -> 程式設計 -> 面試指南 |
| 譯者： |
| 出版社：機械工業出版社 |  3dWoo書號： 48560
詢問書籍請說出此書號！【缺書】
NT售價： 495 元 |
| 出版日：3/1/2018 |
| 頁數：680 |
| 光碟數：0 |
|
站長推薦：   |
| 印刷：黑白印刷 | 語系： ( 簡體 版 ) |
| |
加入購物車  │加到我的最愛
(請先登入會員) |
| ISBN：9787111590118 |
| 作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 序 |
| (簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證) |
| 作者序： |
| 譯者序： |
前言：親愛的讀者：
請先別急著翻過這一頁。我知道，有很多人是不看前言的，但是這次，強烈建議大家讀一讀接下來的幾段話，因為這里面有一些和其他前言不同的地方。
本書的前提是，讀者已經掌握了一些計算機科學的基本知識。它的主要目標并不是提供與數據結構和算法有關的定理及證明，而是以一種逐步完善的方式來告訴大家：我們可以使用那些復雜度各不相同的辦法來解決同一個編程問題。也就是說，針對每一個編程問題，筆者都會按照復雜度遞減的順序來講解各種解法。總的來說，本書中囊括了各種編程解決方案，可以用來有效地應對面試、考試及校園招聘。
求職者如果能夠讀完本書，并很好地理解其中的內容，那么筆者保證：你肯定能夠反過來給面試官提出幾個難題。這正是本書想要達成的效果。
本書對于攻讀工程學位及工程碩士的學生也會很有幫助。書中的每一章都會把重心放在編程問題及對這些問題所做的分析上，而不會只談理論。筆者會在每章的開頭講解閱讀此章所需的基礎理論知識，然后列出一組問題。全書大約有700道算法題，而且每道題都有解答。
本書的大多數章節都會專注于問題本身，并對這些問題做出分析，而不會過多地聚焦在理論上面。各章開頭會給出該章所要求的基本理論，然后提出問題。
書中的許多問題都有不止一種解法，而且這些解法的復雜度也各不相同。我們首先會講解一種蠻力解法（brute force solution），然后逐漸改進，以求找到該問題的最佳解法（best solution）。筆者盡量使大家能夠理解每個算法所耗費的時間，以及它所占據的內存量。
你至少應該將本書通讀一遍，以求對其中的全部話題都有所了解。然后可以根據自己的需要，直接跳到某一章，以參考其內容。盡管本書經過多次校對，但錯誤在所難免，本書勘誤會更新在網站上。你可以定期查閱此網站，以了解最新的勘誤、習題及解決方案。也歡迎你發送郵件到，給筆者提出寶貴的建議。
祝萬事順心、閱讀愉快！
—Narasimha Karumanchi
印度理工學院孟買校區技術碩士、CareerMonk.com創始人 |
內容簡介：內容簡介
本書是一本題目豐富、思路清晰而且解法多樣的程序員面試大全。書中的題目涵蓋了編程基礎、架構設計、網絡技術、數據庫技術、數據結構及算法等主要的話題，而且還談及趣味謎題和非技術的問題。每章都會先講解閱讀本章所需的基礎理論知識，然后列出一組問題，在解讀問題時會先用通俗易懂的語言簡潔地描述解題思路，再從不同的思考方向給出多種解法。
本書涵蓋各大軟件公司面試以及一些競賽（如GATE）中涉及的題目，幫助你在面試中脫穎而出。書中針對各類競賽和面試中的每個難點和考點提供了大量習題和詳細解答，幫助你理解所學概念、強化相關知識，順利通過各種面試和考試。
以通俗易懂的方式講述面試題，涵蓋編程基礎、架構設計、網絡技術、數據庫技術、數據結構及算法等主題
書中的題目來自微軟、谷歌、亞馬遜、雅虎、Oracle、Facebook等大公司的面試題，以及一些知名競賽（如GATE）的考試題
全書約有700道算法題，每道題都有詳細解答
針對每一編程問題，都會按照復雜度遞減的順序給出各種解法
專注于問題本身并對這些問題做出分析，而不會過多地聚焦于理論，缺乏計算機基礎知識的讀者也可以輕松閱讀
軟件開發人員可以將本書作為常備的參考手冊，隨時翻看，溫故而知新 |
目錄：譯者序
前 言
致 謝
第1章 編程基礎1
1.1 變量1
1.2 數據類型1
1.3 數據結構2
1.4 抽象數據類型3
1.5 內存與變量3
1.6 指針4
1.6.1 指針的聲明4
1.6.2 指針的使用5
1.6.3 指針的操縱6
1.6.4 數組與指針7
1.6.5 動態內存分配7
1.6.6 函數指針7
1.7 參數傳遞的方式8
1.7.1 實際參數與形式參數8
1.7.2 參數傳遞的語義8
1.7.3 各種編程語言所支持的參數傳遞方式9
1.7.4 按值傳遞9
1.7.5 按結果傳遞10
1.7.6 有可能發生的參數沖突10
1.7.7 按值-結果傳遞11
1.7.8 按引用傳遞（別名機制）11
1.7.9 按名稱傳遞12
1.8 綁定12
1.8.1 靜態綁定（前期綁定）13
1.8.2 動態綁定（后期綁定）13
1.9 作用域13
1.9.1 靜態作用域13
1.9.2 動態作用域14
1.10 存儲類別15
1.10.1 存儲類別為auto的變量15
1.10.2 存儲類別為extern的變量16
1.10.3 存儲類別為register的變量18
1.10.4 存儲類別為static的變量19
1.11 存儲空間的安排19
1.12 編程方式22
1.12.1 無結構的編程22
1.12.2 過程式的編程22
1.12.3 模塊式的編程22
1.12.4 面向對象的編程23
1.13 面向對象編程的基本概念23
1.13.1 類與對象24
1.13.2 封裝24
1.13.3 抽象25
1.13.4 數據隱藏25
1.13.5 多態25
1.13.6 繼承26
1.13.7 繼承的類型26
1.13.8 動態綁定27
1.13.9 消息傳遞28
第2章 腳本語言83
2.1 解釋器與編譯器83
2.1.1 編譯器83
2.1.2 解釋器84
2.1.3 編譯器與解釋器的區別84
2.2 什么是腳本語言84
2.3 shell腳本編程85
2.3.1 命令的重定向與管道85
2.3.2 變量86
2.3.3 命令行參數87
2.3.4 命令替換88
2.3.5 算術擴展88
2.3.6 控制結構88
2.3.7 函數92
2.4 Perl94
2.4.1 從“Hello world!”程序開始94
2.4.2 Perl的命令行參數95
2.4.3 Perl的數據類型與變量95
2.4.4 引用98
2.4.5 聲明變量98
2.4.6 變量的作用域99
2.4.7 字符串字面量99
2.4.8 Perl的標準輸入端100
2.4.9 Perl語言的運算符101
2.4.10 條件語句110
2.4.11 循環113
2.4.12 子例程115
2.4.13 字符串操作117
2.4.14 包/模塊118
2.5 Python118
2.5.1 什么是Python118
2.5.2 布爾類型119
2.5.3 整數119
2.5.4 字符串119
2.5.5 列表與元組121
2.5.6 函數122
2.5.7 把代碼包裝成模塊123
第3章 與設計有關的面試題124
3.1 術語介紹124
3.2 技巧125
3.3 可供練習的其他設計問題179
第4章 操作系統的概念180
4.1 術語介紹180
4.2 與操作系統概念有關的問題183
第5章 計算機網絡的基礎知識188
5.1 介紹188
5.2 局域網與廣域網188
5.3 數據包分割與多路復用189
5.4 終端設備190
5.5 中介設備190
5.6 集線器、交換機與路由器的定義191
5.7 介質192
5.8 端對端網絡與客戶端/服務器網絡192
5.9 互聯網是如何運作的193
5.10 OSI模型與TCP/IP模型的區別196
5.11 客戶端/服務器結構與互聯網197
5.12 ARP與RARP198
5.13 子網199
5.14 路由器的工作原理200
5.15 單播、廣播、多播201
5.16 tracert/traceroute及ping命令的工作原理202
5.17 什么是QoS203
第6章 數據庫概念204
6.1 術語介紹204
6.2 與數據庫概念有關的問題206
第7章 智力題213
7.1 智力題213
第8章 算法介紹217
8.1 什么是算法217
8.2 為什么要做算法分析218
8.3 算法分析的目標218
8.4 什么是運行時間分析218
8.5 怎樣對比不同的算法218
8.6 什么是增長率219
8.7 幾種常見的增長形式219
8.8 算法分析的類型220
8.9 漸近表示法221
8.10 大O表示法221
8.11 大Ω表示法222
8.12 大Θ表示法223
8.13 算法分析為什么又叫漸近分析225
8.14 漸近分析指南225
8.15 三種表示法的性質227
8.16 常用的對數公式與求和公式227
8.17 分治算法的主定理227
8.18 與分治算法的主定理有關的問題228
8.19 遞減式遞推（減而治之）算法的主定理229
8.20 另一種遞減式遞推（減而治之）算法的主定理229
8.21 與算法分析有關的問題230
第9章 遞歸與回溯240
9.1 介紹240
9.2 什么是遞歸240
9.3 為什么要用遞歸的辦法解決問題240
9.4 遞歸函數的格式241
9.5 演示遞歸調用時的內存占用情況241
9.6 遞歸與迭代242
9.7 運用遞歸時的注意事項243
9.8 遞歸算法舉例243
9.9 與遞歸有關的問題243
9.10 什么是回溯245
9.11 回溯算法舉例245
9.12 與回溯有關的問題245
第10章 鏈表248
10.1 什么是鏈表248
10.2 將鏈表用作抽象的數據類型248
10.3 為什么要用鏈表249
10.4 數組概述249
10.5 比較鏈表、數組與動態數組250
10.6 單鏈表251
10.7 雙鏈表256
10.8 循環鏈表261
10.9 節省內存的雙鏈表266
10.10 松散鏈表268
10.11 跳躍鏈表273
10.12 與鏈表有關的問題276
第11章 棧295
11.1 什么是棧295
11.2 怎樣使用棧296
11.3 將棧用作抽象數據類型296
11.4 棧的運用296
11.5 實現297
11.6 對比各種實現方式302
11.7 與棧有關的問題303
第12章 隊列324
12.1 什么是隊列324
12.2 如何使用隊列324
12.3 將隊列用作抽象數據類型325
12.4 異常325
12.5 運用325
12.6 實現326
12.7 與隊列有關的問題331
第13章 樹337
13.1 什么是樹337
13.2 術語表337
13.3 二叉樹339
13.4 二叉樹的類型339
13.5 二叉樹的性質340
13.6 遍歷二叉樹342
13.7 泛化樹（N叉樹）362
13.8 通過線索二叉樹來遍歷369
13.9 表達式樹376
13.10 異或樹379
13.11 二叉搜索樹380
13.12 平衡二叉搜索樹395
13.13 AVL樹396
13.14 其他形式的樹413
13.14.1 紅黑樹413
13.14.2 伸展樹414
13.14.3 擴充樹（增強樹）414
13.14.4 區間樹（區段樹）415
13.14.5 替罪羊樹416
第14章 優先級隊列與堆418
14.1 什么是優先級隊列418
14.2 將優先級隊列用作抽象數據結構418
14.3 運用419
14.4 實現419
14.5 堆與二叉堆420
14.6 二叉堆421
14.7 與優先級隊列和堆有關的問題428
第15章 圖算法442
15.1 介紹442
15.2 術語表442
15.3 圖的運用446
15.4 將圖用作抽象的數據結構446
15.4.1 鄰接矩陣446
15.4.2 鄰接列表447
15.4.3 鄰接集合449
15.4.4 表示圖的方法的對比449
15.5 圖的遍歷449
15.5.1 深度優先搜索（DFS）450
15.5.2 廣度優先搜索（BFS）454
15.5.3 對比DFS與BFS456
15.6 拓撲排序457
15.7 最短路徑算法458
15.8 最小生成樹465
15.9 與圖算法有關的問題469
第16章 排序475
16.1 什么是排序475
16.2 為什么要排序475
16.3 排序算法的分類方式475
16.3.1 按照比較的次數來分類475
16.3.2 按照交換操作的次數來分類476
16.3.3 按照內存使用量來分類476
16.3.4 按照是否遞歸來分類476
16.3.5 按照是否穩定來分類476
16.3.6 按照適應性來分類476
16.4 其他的分類方式476
16.5 冒泡排序477
16.6 選擇排序478
16.7 插入排序479
16.8 希爾排序481
16.9 歸并排序483
16.10 堆排序485
16.11 快速排序485
16.12 樹排序488
16.13 線性時間的排序算法489
16.14 計數排序489
16.15 桶排序490
16.16 基數排序490
16.17 拓撲排序491
16.18 外部排序491
16.19 與排序有關的問題492
第17章 搜索500
17.1 什么是搜索500
17.2 為什么要搜索500
17.3 各種類型的搜索500
17.4 在無序的數據中執行線性搜索501
17.5 在已經排好序/有序的數組中執行線性搜索501
17.6 二分搜索501
17.7 對比幾種基本的搜索算法502
17.8 符號表與哈希502
17.9 字符串搜索算法502
17.10 與搜索有關的問題503
第18章 選擇算法530
18.1 什么是選擇算法530
18.2 通過排序來選擇530
18.3 基于分區的選擇算法531
18.4 線性選擇算法—中位數的中位數算法531
18.5 把最小的k個元素找出來531
18.6 與選擇算法有關的問題531
第19章 符號表541
19.1 介紹541
19.2 什么是符號表541
19.3 實現符號表542
19.4 比較實現符號表的各種方式543
第20章 哈希544
20.1 什么是哈希544
20.2 為什么要使用哈希544
20.3 將哈希表用作抽象數據結構544
20.4 哈希技術的原理545
20.5 哈希技術的組成要素546
20.6 哈希表546
20.7 哈希函數547
20.8 負載因子547
20.9 沖突547
20.10 沖突解決技術548
20.11 單獨鏈接法548
20.12 開放定址548
20.12.1 線性探測548
20.12.2 二次探測549
20.12.3 二次哈希550
20.13 比較各種沖突解決技術550
20.14 哈希技術如何把復雜度降為O(1)551
20.15 哈希技術551
20.16 哪些問題不適合用哈希表解決551
20.17 Bloom過濾器552
20.17.1 工作原理552
20.17.2 選擇合適的哈希函數553
20.17.3 設置長度合適的位向量553
20.17.4 空間方面的優勢553
20.17.5 時間方面的優勢554
20.17.6 實現554
20.18 與哈希有關的問題554
第21章 字符串算法565
21.1 介紹565
21.2 字符串匹配算法565
21.3 蠻力法566
21.4 Rabin-Karp字符串匹配算法566
21.5 用有限狀態機來實現字符串匹配算法567
21.5.1 狀態機的運作過程568
21.5.2 構建有限狀態機時的注意事項568
21.5.3 匹配算法568
21.6 KMP算法569
21.6.1 前綴表569
21.6.2 匹配算法571
21.7 Boyce-Moore算法573
21.8 適合用來保存字符串的數據結構573
21.9 用哈希表來保存字符串574
21.10 用二叉搜索樹來存放字符串574
21.11 前綴樹574
21.11.1 什么是前綴樹574
21.11.2 為什么要使用前綴樹575
21.11.3 聲明前綴樹575
21.11.4 向前綴樹中插入字符串576
21.11.5 在前綴樹中查找字符串576
21.11.6 用前綴樹來表示字符串有什么缺點577
21.12 三元搜索樹577
21.12.1 聲明三元搜索樹577
21.12.2 向三元搜索樹中插入字符串578
21.12.3 在三元搜索樹中查找字符串580
21.12.4 顯示三元搜索樹中的全部字符串580
21.12.5 在三元搜索樹中查找最長的字符串581
21.13 比較二叉搜索樹、前綴樹及三元搜索樹581
21.14 后綴樹581
21.14.1 前綴與后綴582
21.14.2 規律582
21.14.3 什么是后綴樹582
21.14.4 構建后綴樹582
21.14.5 運用后綴樹585
21.15 與字符串有關的問題585
第22章 算法設計技巧591
22.1 介紹591
22.2 分類591
22.3 按實現方式分類591
22.3.1 遞歸算法與迭代算法591
22.3.2 過程式算法與聲明式（非過程式）算法592
22.3.3 串行算法、并行算法、分布式算法592
22.3.4 確定性的算法與非確定性的算法592
22.3.5 精確算法與近似算法592
22.4 按設計方式分類592
22.4.1 貪婪算法592
22.4.2 分治算法593
22.4.3 動態規劃算法593
22.4.4 線性規劃算法593
22.4.5 歸約（轉化并治理）算法593
22.5 其他分類方式594
22.5.1 按研究領域劃分594
22.5.2 按復雜程度劃分594
22.5.3 隨機化的算法594
22.5.4 分支定界與回溯594
第23章 貪婪算法595
23.1 介紹595
23.2 貪婪算法的策略595
23.3 哪些問題適合用貪婪算法求解595
23.4 貪婪算法是否能應對所有的問題596
23.5 貪婪算法的優點與缺點596
23.6 可以運用貪婪算法的場合596
23.7 理解貪婪算法596
23.8 與貪婪算法有關的問題599
第24章 分治算法606
24.1 介紹606
24.2 什么是分治策略606
24.3 分治技術是否能用來解決所有的問題606
24.4 用示意圖來說明分治技術607
24.5 理解分治技術607
24.6 分治技術的優點608
24.7 分治技術的缺點608
24.8 分治算法的主定理609
24.9 分治算法的適用場合609
24.10 與分治技術有關的問題609
第25章 動態規劃623
25.1 介紹623
25.2 什么是動態規劃策略623
25.3 什么樣的問題適合用動態規劃來解決624
25.4 動態規劃技術能否應對所有的問題624
25.5 動態規劃的方式624
25.5.1 自下而上的動態規劃624
25.5.2 自上而下的動態規劃624
25.5.3 兩種規劃方向的對比624
25.6 動態規劃算法示例625
25.7 理解動態規劃625
25.7.1 斐波那契數列625
25.7.2 求某數的階乘627
25.7.3 最長的公共子序列628
25.8 與動態規劃有關的問題631
第26章 復雜度類668
26.1 介紹668
26.2 多項式時間/指數時間669
26.3 什么是判定性問題669
26.4 判定過程669
26.5 什么是復雜度類669
26.6 復雜度類的類型669
26.6.1 P類669
26.6.2 NP類670
26.6.3 反NP類670
26.6.4 P、NP與反NP之間的關系670
26.6.5 NP困難類670
26.6.6 NP完全類671
26.6.7 P、NP、反NP、NP困難與NP完全之間的關系671
26.6.8 P是否等于NP671
26.7 歸約672
第27章 其他概念675
27.1 介紹675
27.2 與位運算有關的技巧675
27.2.1 按位與675
27.2.2 按位或675
27.2.3 按位異或676
27.2.4 左移位676
27.2.5 右移位676
27.2.6 按位取反676
27.2.7 判斷第K個二進制位有沒有設置（或者說是不是1）676
27.2.8 設置第K個二進制位（也就是將其設為1）677
27.2.9 清除第K個二進制位（也就是將其設為0）677
27.2.10 切換第K個二進制位677
27.2.11 把值為1且最靠右的二進制位設置成0677
27.2.12 把值為1且最靠右的二進制位標出來677
27.2.13 把值為0且最靠右的二進制位標出來678
27.2.14 判斷某數是不是2的冪678
27.2.15 與2的冪相乘678
27.2.16 與2的冪相除678
27.2.17 求出與2的冪相除的余數678
27.2.18 將二進制表示形式反轉678
27.2.19 統計值為1的二進制位個數679
27.2.20 創建掩碼，以便將尾部連續出現的0標注出來680
27.2.21 把奇數位置上的二進制位與偶數位置上的二進制位互換680
27.2.22 用不做除法的方式來求平均值680
27.3 其他編程問題680
第28章 非技術問題686
28.1 面試技巧686
28.2 非技術問題舉例688 |
| 序： |
