本文為掘金投稿求豫，譯文出自：掘金翻譯計劃
- 原文地址：Google Interview University
- 原文作者：John Washam
- 譯者：Aleen熄云，Newton膨更，bobmayuze，Jaeger缴允，sqrthree
- 友情提醒：文章較長荚守，需耐心閱讀。
這是练般？
這是我為了從 Web 開發(fā)者（自學(xué)矗漾、非計算機科學(xué)學(xué)位）蛻變至 Google 軟件工程師所制定的計劃，其內(nèi)容歷時數(shù)月薄料。
這一長列表是從 Google 的指導(dǎo)筆記 中萃取出來并進行擴展敞贡。因此，有些事情你必須去了解一下摄职。我在列表的底部添加了一些額外項誊役，用于解決面試中可能會出現(xiàn)的問題。這些額外項大部分是來自于 Steve Yegge 的“得到在 Google 工作的機會”谷市。而在 Google 指導(dǎo)筆記的逐字間蛔垢，它們有時也會被反映出來。
目錄
—————- 下面的內(nèi)容是可選的 —————-
為何要用到它鞠抑？
我一直都是遵循該計劃去準(zhǔn)備 Google 的面試饭聚。自 1997 年以來，我一直從事于 Web 程序的構(gòu)建碍拆、服務(wù)器的構(gòu)建及創(chuàng)業(yè)型公司的創(chuàng)辦若治。對于只有著一個經(jīng)濟學(xué)學(xué)位慨蓝，而不是計算機科學(xué)學(xué)位（CS degree）的我來說，在職業(yè)生涯中所取得的都非常成功端幼。然而礼烈，我想在 Google 工作，并進入大型系統(tǒng)中婆跑，真正地去理解計算機系統(tǒng)此熬、算法效率、數(shù)據(jù)結(jié)構(gòu)性能滑进、低級別編程語言及其工作原理犀忱。可一項都不了解的我扶关，怎么會被 Google 所應(yīng)聘呢阴汇？
當(dāng)我創(chuàng)建該項目時，我從一個堆棧到一個堆都不了解节槐。那時的我搀庶，完全不了解 Big-O 、樹铜异，或如何去遍歷一個圖哥倔。如果非要我去編寫一個排序算法的話，我只能說我所寫的肯定是很糟糕揍庄。一直以來咆蒿，我所用的任何數(shù)據(jù)結(jié)構(gòu)都是內(nèi)建于編程語言當(dāng)中。至于它們在背后是如何運作蚂子，對此我一概不清楚沃测。此外，以前的我并不需要對內(nèi)存進行管理缆镣，最多就只是在一個正在執(zhí)行的進程拋出了“內(nèi)存不足”的錯誤后芽突，采取一些權(quán)變措施。而在我的編程生活中董瞻，也甚少使用到多維數(shù)組寞蚌，可關(guān)聯(lián)數(shù)組卻成千上萬。而且钠糊，從一開始到現(xiàn)在挟秤，我都還未曾自己實現(xiàn)過數(shù)據(jù)結(jié)構(gòu)。
就是這樣的我抄伍，在經(jīng)過該學(xué)習(xí)計劃后艘刚，已然對被 Google 所雇傭充滿信心。這是一個漫長的計劃截珍，以至于花費了我數(shù)月的時間攀甚。若您早已熟悉大部分的知識箩朴，那么也許能節(jié)省大量的時間。
如何使用它
下面所有的東西都只是一個概述秋度。因此炸庞，你需要由上而下逐一地去處理它。
在學(xué)習(xí)過程中荚斯，我是使用 GitHub 特殊的語法特性 markdown flavor 去檢查計劃的進展埠居，包括使用任務(wù)列表。(注：因極客頭條的 markdown 并不支持此語法事期，因此在下方做了刪除處理)
創(chuàng)建一個新的分支滥壕，以使得你可以像這樣去檢查計劃的進展。直接往方括號中填寫一個x兽泣，表示已經(jīng)完成
更多關(guān)于 Github-flavored markdown 的詳情
我得到了工作嗎绎橘？
我還沒去應(yīng)聘。
因為我離完成學(xué)習(xí)（完成該瘋狂的計劃列表）還需要數(shù)天的時間撞叨，并打算在下周開始用一整天的時間金踪，以編程的方式去解決問題。當(dāng)然牵敷，這將會持續(xù)數(shù)周的時間。然后法希，我才通過使用在二月份所得到的一個介紹資格枷餐，去正式應(yīng)聘 Google（沒錯，是二月份時就得到的）苫亦。
感謝 JP 的這次介紹毛肋。
跟隨著我
目前我仍在該計劃的執(zhí)行過程中，如果你想跟隨我腳步去學(xué)習(xí)的話屋剑，可以登進我在 GoogleyAsHeck.com 上所寫的博客润匙。
不要自以為自己足夠聰明
- Google 的工程師都是才智過人的。但是唉匾，就算是工作在 Google 的他們孕讳，仍然會因為自己不夠聰明而感到一種不安。
- 天才程序員的神話
關(guān)于 Google
面向?qū)W生 —— Google 的職業(yè)生涯：技術(shù)開發(fā)指導(dǎo)
Google 檢索的原理：
系列文章：
相關(guān)視頻資源
部分視頻只能通過在 Coursera巍膘、Edx 或 Lynda.com class 上注冊登錄才能觀看厂财。這些視頻被稱為網(wǎng)絡(luò)公開課程（MOOC）。即便是免費觀看峡懈，部分課程可能會由于不在時間段內(nèi)而無法獲取璃饱。因此，你需要多等待幾個月肪康。
很感謝您能幫我把網(wǎng)絡(luò)公開課程的視頻鏈接轉(zhuǎn)換成公開的視頻源荚恶，以代替那些在線課程的視頻撩穿。此外，一些大學(xué)的講座視頻也是我所青睞的谒撼。
面試過程 & 通用的面試準(zhǔn)備
視頻：
文章：
所有他所提及的事情都列在了下面
附加的（雖然 Google 不建議嗤栓，但我還是添加在此）：
震撼開發(fā)類面試 第一集：
如何在世界四強企業(yè)中獲得一份工作：
“如何在世界四強企業(yè)中獲得一份工作 —— Amazon、Facebook茉帅、Google 和 Microsoft”（視頻）
為你的面試選擇一種語言
在這叨叙，我就以下話題寫一篇短文 —— 重點：為在 Google 的面試選擇一種語言
在大多數(shù)公司的面試當(dāng)中，你可以在編程這一環(huán)節(jié)堪澎，使用一種自己用起來較為舒適的語言去完成編程擂错。但在 Google，你只有三種固定的選擇：
- C++
- Java
- Python
有時你也可以使用下面兩種樱蛤，但需要事先查閱說明钮呀。因為，說明中會有警告：
- JavaScript
- Ruby
你需要對你所選擇的語言感到非常舒適且足夠了解昨凡。
更多關(guān)于語言選擇的閱讀：
- http://www.byte-by-byte.com/choose-the-right-language-for-your-coding-interview/
- http://blog.codingforinterviews.com/best-programming-language-jobs/
- https://www.quora.com/What-is-the-best-language-to-program-in-for-an-in-person-Google-interview
由于爽醋，我正在學(xué)習(xí)C、C++ 和 Python便脊。因此蚂四，在下面你會看到部分關(guān)于它們的學(xué)習(xí)資料。相關(guān)書籍請看文章的底部哪痰。
在你開始之前
該列表已經(jīng)持續(xù)更新了很長的一段時間遂赠，所以，我們的確很容易會對其失去控制晌杰。
這里列出了一些我所犯過的錯誤跷睦，希望您不要重滔覆轍。
1. 你不可能把所有的東西都記住
就算我查看了數(shù)小時的視頻肋演，并記錄了大量的筆記抑诸。幾個月后的我，仍然會忘卻其中大部分的東西惋啃。所以哼鬓，我翻閱了我的筆記，并將可回顧的東西制作成抽認卡（flashcard）（請往下看）
2. 使用抽認卡
為了解決善忘的問題边灭，我制作了一些關(guān)于抽認卡的頁面异希，用于添加兩種抽認卡：正常的及帶有代碼的。每種卡都會有不同的格式設(shè)計。
而且称簿，我還以移動設(shè)備為先去設(shè)計這些網(wǎng)頁扣癣，以使得在任何地方的我，都能通過我的手機及平板去回顧知識憨降。
你也可以免費制作屬于你自己的抽認卡網(wǎng)站：
- 抽認卡頁面的代碼倉庫
- 我的抽認卡數(shù)據(jù)庫：有一點需要記住的是父虑，我做事有點過頭，以至于把卡片都覆蓋到所有的東西上授药。從匯編語言和 Python 的細枝末節(jié)士嚎，乃至到機器學(xué)習(xí)和統(tǒng)計都被覆蓋到卡片上。而這種做法悔叽，對于 Google 的要求來說莱衩，卻是多余。
在抽認卡上做筆記： 若你第一次發(fā)現(xiàn)你知道問題的答案時娇澎，先不要急著把其標(biāo)注成“已懂”笨蚁。你需要做的，是去查看一下是否有同樣的抽認卡趟庄，并在你真正懂得如何解決問題之前括细，多問自己幾次。重復(fù)地問答可幫助您深刻記住該知識點戚啥。
3. 回顧奋单，回顧，回顧
我留有一組 ASCII 碼表虑鼎、OSI 堆棧辱匿、Big-O 記號及更多的小抄紙，以便在空余的時候可以學(xué)習(xí)炫彩。
每編程半個小時就要休息一下，并去回顧你的抽認卡絮短。
4. 專注
在學(xué)習(xí)的過程中丁频，往往會有許多令人分心的事占據(jù)著我們寶貴的時間。因此席里，專注和集中注意力是非常困難的奖磁。
你所看不到的
由于改基，這個巨大的列表一開始是作為我個人從 Google 面試指導(dǎo)筆記所形成的一個事件處理列表秕狰。因此鸣哀，有一些我熟悉且普遍的技術(shù)在此都未被談及到：
- SQL
- Javascript
- HTML我衬、CSS 和其他前端技術(shù)
日常計劃
部分問題可能會花費一天的時間去學(xué)習(xí)井仰，而部分則會花費多天糕档。當(dāng)然，有些學(xué)習(xí)并不需要我們懂得如何實現(xiàn)端仰。
因此荔烧，每一天我都會在下面所列出的列表中選擇一項，并查看相關(guān)的視頻臀稚。然后满哪，使用以下的一種語言去實現(xiàn)：
C —— 使用結(jié)構(gòu)體和函數(shù)蛹屿，該函數(shù)會接受一個結(jié)構(gòu)體指針 * 及其他數(shù)據(jù)作為參數(shù)赖条。 C++ —— 不使用內(nèi)建的數(shù)據(jù)類型谋币。 C++ —— 使用內(nèi)建的數(shù)據(jù)類型早芭，如使用 STL 的 std::list 來作為鏈表退个。 Python —— 使用內(nèi)建的數(shù)據(jù)類型（為了持續(xù)練習(xí) Python），并編寫一些測試去保證自己代碼的正確性刀荒。有時，只需要使用斷言函數(shù) assert() 即可泼返。 此外，你也可以使用 Java 或其他語言柴罐。以上只是我的個人偏好而已。
為何要在這些語言上分別實現(xiàn)一次？
因為可以練習(xí)，練習(xí)虾啦，練習(xí)蝇闭，直至我厭倦它，并完美地實現(xiàn)出來逻悠。（若有部分邊緣條件沒想到時，我會用書寫的形式記錄下來并去記憶） 因為可以在純原生的條件下工作（不需垃圾回收機制的幫助下饥伊，分配/釋放內(nèi)存（除了 Python）） 因為可以利用上內(nèi)建的數(shù)據(jù)類型，以使得我擁有在現(xiàn)實中使用內(nèi)建工具的經(jīng)驗（在生產(chǎn)環(huán)境中，我不會去實現(xiàn)自己的鏈表）
就算我沒有時間去每一項都這么做节腐，但我也會盡我所能的。
在這里狼渊，你可以查看到我的代碼：
你不需要記住每一個算法的內(nèi)部原理。
在一個白板上寫代碼，而不要直接在計算機上編寫蘸嘶。在測試完部分簡單的輸入后褥蚯，到計算機上再測試一遍。
必備知識
計算機是如何處理一段程序：
編譯器
浮點數(shù)是如何存儲的：
32 bit：IEEE754 32-bit 浮點二進制（視頻）
算法復(fù)雜度 / Big-O / 漸進分析法
并不需要實現(xiàn)
Skiena 算法：
高級編程（包括遞歸關(guān)系和主定理）：
如果部分課程過于學(xué)術(shù)性宴凉，你可直接跳到文章底部丧靡，去查看離散數(shù)學(xué)的視頻以獲取相關(guān)背景知識。
數(shù)據(jù)結(jié)構(gòu)
數(shù)組（Arrays）
實現(xiàn)一個可自動調(diào)整大小的動態(tài)數(shù)組熬荆。
介紹：
實現(xiàn)一個動態(tài)數(shù)組（可自動調(diào)整大小的可變數(shù)組）：
練習(xí)使用數(shù)組和指針去編碼，并且指針是通過計算去跳轉(zhuǎn)而不是使用索引
通過分配內(nèi)存來新建一個原生數(shù)據(jù)型數(shù)組
可以使用 int 類型的數(shù)組拆融，但不能使用其語法特性
從大小為16或更大的數(shù)（使用2的倍數(shù) —— 16、32、64散怖、128）開始編寫
size() —— 數(shù)組元素的個數(shù)
capacity() —— 可容納元素的個數(shù)
is_empty()
at(index) —— 返回對應(yīng)索引的元素，且若索引越界則憤然報錯
push(item)
insert(index, item) —— 在指定索引中插入元素，并把后面的元素依次后移
prepend(item) —— 可以使用上面的 insert 函數(shù)具伍，傳參 index 為 0
pop() —— 刪除在數(shù)組末端的元素，并返回其值
delete(index) —— 刪除指定索引的元素，并把后面的元素依次前移
remove(item) —— 刪除指定值的元素惕味，并返回其索引（即使有多個元素）
find(item) —— 尋找指定值的元素并返回其中第一個出現(xiàn)的元素其索引，若未找到則返回 -1
resize(new_capacity) // 私有函數(shù)
若數(shù)組的大小到達其容積，則變大一倍
獲取元素后蹋艺，若數(shù)組大小為其容積的1/4，則縮小一半
時間復(fù)雜度
在數(shù)組末端增加/刪除、定位检吆、更新元素臂寝，只允許占 O(1) 的時間復(fù)雜度（平攤（amortized）去分配內(nèi)存以獲取更多空間）
在數(shù)組任何地方插入/移除元素，只允許 O(n) 的時間復(fù)雜度
空間復(fù)雜度
因為在內(nèi)存中分配的空間鄰近，所以有助于提高性能
空間需求 = （大于或等于 n 的數(shù)組容積）* 元素的大小眷蜈。即便空間需求為 2n酥泛，其空間復(fù)雜度仍然是 O(n)
鏈表（Linked Lists）
介紹：
并非看完整個視頻呆躲，只需要看關(guān)于節(jié)點結(jié)果和內(nèi)存分配那一部分即可
鏈表 vs 數(shù)組：
的確：你需要關(guān)于“指向指針的指針”的相關(guān)知識：（因為當(dāng)你傳遞一個指針到一個函數(shù)時，該函數(shù)可能會改變指針?biāo)赶虻牡刂罚┰擁撝皇菫榱俗屇懔私狻爸赶蛑羔樀闹羔槨边@一概念璃弄。但我并不推薦這種鏈?zhǔn)奖闅v的風(fēng)格。因為，這種風(fēng)格的代碼政己，其可讀性和可維護性太低。
實現(xiàn)（我實現(xiàn)了使用尾指針以及沒有使用尾指針這兩種情況）：
size() —— 返回鏈表中數(shù)據(jù)元素的個數(shù)
empty() —— 若鏈表為空則返回一個布爾值 true
value_at(index) —— 返回第 n 個元素的值（從0開始計算）
push_front(value) —— 添加元素到鏈表的首部
pop_front() —— 刪除首部元素并返回其值
push_back(value) —— 添加元素到鏈表的尾部
pop_back() —— 刪除尾部元素并返回其值
front() —— 返回首部元素的值
back() —— 返回尾部元素的值
insert(index, value) —— 插入值到指定的索引，并把當(dāng)前索引的元素指向到新的元素
erase(index) —— 刪除指定索引的節(jié)點
value_n_from_end(n) —— 返回倒數(shù)第 n 個節(jié)點的值
reverse() —— 逆序鏈表
remove_value(value) —— 刪除鏈表中指定值的第一個元素
雙向鏈表
并不需要實現(xiàn)
堆棧（Stack）
可以不實現(xiàn)，因為使用數(shù)組來實現(xiàn)并不重要
隊列（Queue）
使用含有尾部指針的鏈表來實現(xiàn):
enqueue(value) —— 在尾部添加值
dequeue() —— 刪除最早添加的元素并返回其值（首部元素）
empty()
使用固定大小的數(shù)組實現(xiàn)：
enqueue(value) —— 在可容的情況下添加元素到尾部
dequeue() —— 刪除最早添加的元素并返回其值
empty()
full()
花銷：
在糟糕的實現(xiàn)情況下欠气，使用鏈表所實現(xiàn)的隊列队塘，其入列和出列的時間復(fù)雜度將會是 O(n)。因為鸿市，你需要找到下一個元素剥懒，以致循環(huán)整個隊列
enqueue：O(1)（平攤（amortized）验游、鏈表和數(shù)組 [探測（probing）]）
dequeue：O(1)（鏈表和數(shù)組）
empty：O(1)（鏈表和數(shù)組）
哈希表（Hash table）
視頻：
（進階）隨機取樣（Randomization）：全域哈希（Universal Hashing）& 完美哈希（Perfect Hashing）（視頻）
在線課程：
分布式哈希表：
使用線性探測的數(shù)組去實現(xiàn)
hash(k, m) —— m 是哈希表的大小
add(key, value) —— 如果 key 已存在則更新值
exists(key)
get(key)
remove(key)
更多的知識
二分查找（Binary search）
實現(xiàn)：
二分查找（在一個已排序好的整型數(shù)組中查找）
迭代式二分查找
按位運算（Bitwise operations）
你需要知道大量2的冪數(shù)值（從2^1 到 2^16 及 2^32）
好好理解位操作符的含義：&展东、|权悟、^、~榔昔、>>、<<
好的介紹：
一補數(shù)和補碼
計算置位（Set Bits）
四舍五入2的冪數(shù)：
交換值：
絕對值：
樹（Trees）
樹 —— 筆記 & 背景
基本的樹形結(jié)構(gòu)
遍歷
操作算法
BFS（廣度優(yōu)先檢索默穴，breadth-first search）
層序遍歷（使用隊列的 BFS 算法）
時間復(fù)雜度： O(n)
空間復(fù)雜度：
最好情況： O(1)
最壞情況：O(n/2)=O(n)
DFS（深度優(yōu)先檢索，depth-first search）
筆記：
時間復(fù)雜度：O(n)
空間復(fù)雜度：
最好情況：O(log n) - 樹的平均高度
最壞情況：O(n)
中序遍歷（DFS：左许蓖、節(jié)點本身嚎莉、右）
后序遍歷（DFS：左赃额、右、節(jié)點本身）
先序遍歷（DFS：節(jié)點本身、左吓歇、右）
二叉查找樹（Binary search trees）：BSTs
從符號表開始到 BST 程序
C/C++:
實現(xiàn)：
insert // 往樹上插值
get_node_count // 查找樹上的節(jié)點數(shù)
print_values // 從小到大打印樹中節(jié)點的值
delete_tree
is_in_tree // 如果值存在于樹中則返回 true
get_height // 返回節(jié)點所在的高度（如果只有一個節(jié)點，那么高度則為1）
get_min // 返回樹上的最小值
get_max // 返回樹上的最大值
is_binary_search_tree
delete_value
get_successor // 返回給定值的后繼者吟税，若沒有則返回-1
堆（Heap） / 優(yōu)先級隊列（Priority Queue） / 二叉堆（Binary Heap）
可視化是一棵樹肖抱，但通常是以線性的形式存儲（數(shù)組、鏈表）
實現(xiàn)一個大頂堆：
insert
sift_up —— 用于插入元素
get_max —— 返回最大值但不移除元素
get_size() —— 返回存儲的元素數(shù)量
is_empty() —— 若堆為空則返回 true
extract_max —— 返回最大值并移除
sift_down —— 用于獲取最大值元素
remove(i) —— 刪除指定索引的元素
heapify —— 構(gòu)建堆潮针，用于堆排序
heap_sort() —— 拿到一個未排序的數(shù)組，然后使用大頂堆進行就地排序
注意：若用小頂堆可節(jié)省操作子库，但導(dǎo)致空間復(fù)雜度加倍。（無法做到就地）
字典樹（Tries）
需要注意的是啊楚，字典樹各式各樣。有些有前綴，而有些則沒有。有些使用字符串而不使用比特位來追蹤路徑。
閱讀代碼片排，但不實現(xiàn)寨腔。
短課程視頻：
平衡查找樹（Balanced search trees）
掌握至少一種平衡查找樹（并懂得如何實現(xiàn)）：
“在各種平衡查找樹當(dāng)中迫卢，AVL 樹和2-3樹已經(jīng)成為了過去冶共，而紅黑樹（red-black trees）看似變得越來越受人青睞乾蛤。這種令人特別感興趣的數(shù)據(jù)結(jié)構(gòu)，亦稱伸展樹（splay tree）捅僵。它可以自我管理家卖，且會使用輪換來移除任何訪問過根節(jié)點的 key∶溃” —— Skiena
因此篡九，在各種各樣的平衡查找樹當(dāng)中，我選擇了伸展樹來實現(xiàn)醋奠。雖然榛臼，通過我的閱讀，我發(fā)現(xiàn)在 Google 的面試中并不會被要求實現(xiàn)一棵平衡查找樹窜司。但是沛善，為了勝人一籌，我們還是應(yīng)該看看如何去實現(xiàn)塞祈。在閱讀了大量關(guān)于紅黑樹的代碼后金刁，我才發(fā)現(xiàn)伸展樹的實現(xiàn)確實會使得各方面更為高效。
伸展樹：插入、查找尤蛮、刪除函數(shù)的實現(xiàn)媳友，而如果你最終實現(xiàn)了紅黑樹，那么請嘗試一下：
跳過刪除函數(shù)产捞，直接實現(xiàn)搜索和插入功能
我希望能閱讀到更多關(guān)于 B 樹的資料醇锚，因為它也被廣泛地應(yīng)用到大型的數(shù)據(jù)庫當(dāng)中。
AVL 樹
實際中：我能告訴你的是坯临，該種樹并無太多的用途焊唬，但我能看到有用的地方在哪里：AVL 樹是另一種平衡查找樹結(jié)構(gòu)。其可支持時間復(fù)雜度為 O(log n) 的查詢看靠、插入及刪除赶促。它比紅黑樹嚴(yán)格意義上更為平衡，從而導(dǎo)致插入和刪除更慢挟炬，但遍歷卻更快鸥滨。正因如此，才彰顯其結(jié)構(gòu)的魅力谤祖。只需要構(gòu)建一次爵赵，就可以在不重新構(gòu)造的情況下讀取，適合于實現(xiàn)諸如語言字典（或程序字典泊脐，如一個匯編程序或解釋程序的操作碼）。
伸展樹
實際中：伸展樹一般用于緩存烁峭、內(nèi)存分配者容客、路由器、垃圾回收者约郁、數(shù)據(jù)壓縮缩挑、ropes（字符串的一種替代品，用于存儲長串的文本字符）鬓梅、Windows NT（虛擬內(nèi)存供置、網(wǎng)絡(luò)及文件系統(tǒng)）等的實現(xiàn)。
MIT 教程：伸展樹（Splay trees）：
該教程會過于學(xué)術(shù)绽快，但請觀看到最后的10分鐘以確保掌握芥丧。
2-3查找樹
實際中：2-3樹的元素插入非常快速坊罢，但卻有著查詢慢的代價（因為相比較 AVL 樹來說续担，其高度更高）。
你會很少用到2-3樹活孩。這是因為物遇，其實現(xiàn)過程中涉及到不同類型的節(jié)點。因此，人們更多地會選擇紅黑樹询兴。
2-3-4樹 (亦稱2-4樹)
實際中：對于每一棵2-4樹乃沙，都有著對應(yīng)的紅黑樹來存儲同樣順序的數(shù)據(jù)元素。在2-4樹上進行插入及刪除操作等同于在紅黑樹上進行顏色翻轉(zhuǎn)及輪換诗舰。這使得2-4樹成為一種用于掌握紅黑樹背后邏輯的重要工具警儒。這就是為什么許多算法引導(dǎo)文章都會在介紹紅黑樹之前，先介紹2-4樹始衅，盡管2-4樹在實際中并不經(jīng)常使用冷蚂。
B 樹
有趣的是：為啥叫 B 仍然是一個神秘。因為 B 可代表波音（Boeing）汛闸、平衡（Balanced）或 Bayer（聯(lián)合創(chuàng)造者）
實際中：B 樹會被廣泛適用于數(shù)據(jù)庫中蝙茶，而現(xiàn)代大多數(shù)的文件系統(tǒng)都會使用到這種樹（或變種)。除了運用在數(shù)據(jù)庫中诸老，B 樹也會被用于文件系統(tǒng)以快速訪問一個文件的任意塊隆夯。但存在著一個基本的問題，那就是如何將文件塊 i 轉(zhuǎn)換成一個硬盤塊（或一個柱面-磁頭-扇區(qū)）上的地址别伏。
覆蓋有高速緩存參數(shù)無關(guān)型（cache-oblivious）B 樹和非常有趣的數(shù)據(jù)結(jié)構(gòu)
頭37分鐘講述的很專業(yè)蹄衷，或許可以跳過（B 指塊的大小、即緩存行的大欣灏埂）
紅黑樹
實際中：紅黑樹提供了在最壞情況下插入操作愧口、刪除操作和查找操作的時間保證。這些時間值的保障不僅對時間敏感型應(yīng)用有用类茂，例如實時應(yīng)用耍属，還對在其他數(shù)據(jù)結(jié)構(gòu)中塊的構(gòu)建非常有用，而這些數(shù)據(jù)結(jié)構(gòu)都提供了最壞情況下的保障巩检；例如厚骗，許多用于計算幾何學(xué)的數(shù)據(jù)結(jié)構(gòu)都可以基于紅黑樹，而目前 Linux 系統(tǒng)所采用的完全公平調(diào)度器（the Completely Fair Scheduler）也使用到了該種樹兢哭。在 Java 8中领舰，紅黑樹也被用于存儲哈希列表集合中相同的數(shù)據(jù)，而不是使用鏈表及哈希碼迟螺。
N 叉樹（K 叉樹冲秽、M 叉樹）
注意：N 或 K 指的是分支系數(shù)（即樹的最大分支數(shù)）：
二叉樹是一種分支系數(shù)為2的樹
2-3樹是一種分支系數(shù)為3的樹
排序（Sorting）
筆記:
實現(xiàn)各種排序 & 知道每種排序的最壞、最好和平均的復(fù)雜度分別是什么場景:
不要用冒泡排序 - 大多數(shù)情況下效率感人 - 時間復(fù)雜度 O(n^2), 除非 n <= 16
排序算法的穩(wěn)定性 (“快排是穩(wěn)定的么?”)
哪種排序算法可以用鏈表矩父？哪種用數(shù)組劳跃？哪種兩者都可？
并不推薦對一個鏈表排序浙垫，但歸并排序是可行的.
關(guān)于堆排序刨仑，請查看前文堆的數(shù)據(jù)結(jié)構(gòu)部分郑诺。堆排序很強大，不過是非穩(wěn)定排序杉武。
斯坦福大學(xué)關(guān)于排序算法的視頻:
Shai Simonson 視頻, Aduni.org:
Steven Skiena 關(guān)于排序的視頻:
加州大學(xué)伯克利分校（UC Berkeley） 大學(xué)課程:
歸并排序:
快速排序:
實現(xiàn):
歸并：平均和最差情況的時間復(fù)雜度為 O(n log n)辙诞。
快排：平均時間復(fù)雜度為 O(n log n)。
選擇排序和插入排序的最壞轻抱、平均時間復(fù)雜度都是 O(n^2)飞涂。
關(guān)于堆排序，請查看前文堆的數(shù)據(jù)結(jié)構(gòu)部分祈搜。
有興趣的話较店，還有一些補充 - 但并不是必須的:
圖（Graphs）
圖論能解決計算機科學(xué)里的很多問題，所以這一節(jié)會比較長容燕，像樹和排序的部分一樣梁呈。
Yegge 的筆記:
有 3 種基本方式在內(nèi)存里表示一個圖:
對象和指針
矩陣
鄰接表
熟悉以上每一種圖的表示法，并了解各自的優(yōu)缺點
寬度優(yōu)先搜索和深度優(yōu)先搜索 - 知道它們的計算復(fù)雜度和設(shè)計上的權(quán)衡以及如何用代碼實現(xiàn)它們
遇到一個問題時蘸秘，首先嘗試基于圖的解決方案官卡，如果沒有再去嘗試其他的。
Skiena 教授的課程 - 很不錯的介紹:
圖 (復(fù)習(xí)和其他):
Aduni: 圖的算法 II - 深度優(yōu)先搜索, 廣度優(yōu)先搜索, Kruskal 算法, 并查集數(shù)據(jù)結(jié)構(gòu) - 第七課 (video)
完整的 Coursera 課程:
Yegge: 如果有機會醋虏，可以試試研究更酷炫的算法:
Dijkstra 算法 - 上文 - 6.006
A* 算法
我會實現(xiàn):
DFS 鄰接表 (遞歸)
DFS 鄰接表 (棧迭代)
DFS 鄰接矩陣 (遞歸)
DFS 鄰接矩陣 (棧迭代)
BFS 鄰接表
BFS 鄰接矩陣
單源最短路徑問題 (Dijkstra)
最小生成樹
基于 DFS 的算法 (根據(jù)上文 Aduni 的視頻):
檢查環(huán) (我們會先檢查是否有環(huán)存在以便做拓撲排序)
拓撲排序
計算圖中的連通分支
列出強連通分量
檢查雙向圖
可以從 Skiena 的書（參考下面的書推薦小節(jié)）和面試書籍中學(xué)習(xí)更多關(guān)于圖的實踐寻咒。
更多知識
遞歸（Recursion）
Stanford 大學(xué)關(guān)于遞歸 & 回溯的課程:
什么時候適合使用
尾遞歸會更好么?
動態(tài)規(guī)劃（Dynamic Programming）
This subject can be pretty difficult, as each DP soluble problem must be defined as a recursion relation, and coming up with it can be tricky.
這一部分會有點困難，每個可以用動態(tài)規(guī)劃解決的問題都必須先定義出遞推關(guān)系颈嚼，要推導(dǎo)出來可能會有點棘手毛秘。
我建議先閱讀和學(xué)習(xí)足夠多的動態(tài)規(guī)劃的例子，以便對解決 DP 問題的一般模式有個扎實的理解阻课。
視頻:
Skiena 的視頻可能會有點難跟上熔脂，有時候他用白板寫的字會比較小，難看清楚柑肴。
Skiena: CSE373 2012 - 課程 22 - 動態(tài)規(guī)劃應(yīng)用 (video)
單獨的 DP 問題 (每一個視頻都很短):
Yale 課程筆記:
Coursera 課程:
組合（Combinatorics） (n 中選 k 個) & 概率（Probability）
可汗學(xué)院:
課程設(shè)置:
視頻 - 41 (每一個都短小精悍):
NP, NP-完全和近似算法
知道最經(jīng)典的一些 NP 完全問題旬薯，比如旅行商問題和背包問題,
而且能在面試官試圖忽悠你的時候識別出他們晰骑。
知道 NP 完全是什么意思.
Simonson:
Skiena:
[CSE373 2012 - 課程 23 - 介紹 NP-完全性 IV (video)](https://youtu.be/KiK5TVgXbFg?list=PLOtl7M3y
