當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

坚持完成这套学习手册，你就可以去 Google 面试了

發布時間：2025/7/25 编程问答 14 豆豆

生活随笔收集整理的這篇文章主要介紹了坚持完成这套学习手册，你就可以去 Google 面试了小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

from: http://geek.csdn.net/news/detail/107064

本文為掘金投稿，譯文出自：掘金翻譯計劃
原文地址：Google Interview University
原文作者：John Washam
譯者：Aleen，Newton，bobmayuze，Jaeger，sqrthree
友情提醒：文章較長，需耐心閱讀。

這是？

這是我為了從 Web 開發者（自學、非計算機科學學位）蛻變至 Google 軟件工程師所制定的計劃，其內容歷時數月。

這一長列表是從 Google 的指導筆記 中萃取出來并進行擴展。因此，有些事情你必須去了解一下。我在列表的底部添加了一些額外項，用于解決面試中可能會出現的問題。這些額外項大部分是來自于 Steve Yegge 的“得到在 Google 工作的機會”。而在 Google 指導筆記的逐字間，它們有時也會被反映出來。

這是？
為何要用到它？
如何使用它
擁有一名 Googler 的心態
我得到了工作嗎？
跟隨著我
不要自以為自己足夠聰明
關于 Google
相關視頻資源
面試過程 & 通用的面試準備
為你的面試選擇一種語言
在你開始之前
你所看不到的
日常計劃
必備知識
算法復雜度 / Big-O / 漸進分析法
數據結構
- 數組（Arrays）
- 鏈表（Linked Lists）
- 堆棧（Stack）
- 隊列（Queue）
- 哈希表（Hash table）
更多的知識
- 二分查找（Binary search）
- 按位運算（Bitwise operations）
樹（Trees）
- 樹 —— 筆記 & 背景
- 二叉查找樹（Binary search trees）：BSTs
- 堆（Heap） / 優先級隊列（Priority Queue） / 二叉堆（Binary Heap）
- 字典樹（Tries）
- 平衡查找樹（Balanced search trees）
- N 叉樹（K 叉樹、M 叉樹）
排序
圖（Graphs）
更多知識
- 遞歸
- 動態規劃
- 組合 & 概率
- NP, NP-完全和近似算法
- 緩存
- 進程和線程
- 系統設計、可伸縮性、數據處理
- 論文
- 測試
- 調度
- 實現系統例程
- 字符串搜索和操作
終面
書籍
編碼練習和挑戰
當你臨近面試時
你的簡歷
當面試來臨的時候
問面試官的問題
當你獲得了夢想的職位

—————- 下面的內容是可選的 —————-

附加的學習
- Unicode
- 字節順序
- Emacs and vi(m)
- Unix 命令行工具
- 信息資源 (視頻)
- 奇偶校驗位 & 漢明碼 (視頻)
- 系統熵值（系統復雜度）
- 密碼學
- 壓縮
- 網絡 (視頻)
- 計算機安全
- 釋放緩存
- 并行/并發編程
- 設計模式
- 信息傳輸, 序列化, 和隊列化的系統
- 快速傅里葉變換
- 布隆過濾器
- van Emde Boas 樹
- 更深入的數據結構
- 跳表
- 網絡流
- 不相交集 & 聯合查找
- 快速處理數學
- 樹堆 (Treap)
- 線性規劃
- 幾何：凸包（Geometry, Convex hull）
- 離散數學
- 機器學習
- Go 語言
一些主題的額外內容
視頻系列
計算機科學課程

為何要用到它？

我一直都是遵循該計劃去準備 Google 的面試。自 1997 年以來，我一直從事于 Web 程序的構建、服務器的構建及創業型公司的創辦。對于只有著一個經濟學學位，而不是計算機科學學位（CS degree）的我來說，在職業生涯中所取得的都非常成功。然而，我想在 Google 工作，并進入大型系統中，真正地去理解計算機系統、算法效率、數據結構性能、低級別編程語言及其工作原理。可一項都不了解的我，怎么會被 Google 所應聘呢？

當我創建該項目時，我從一個堆棧到一個堆都不了解。那時的我，完全不了解 Big-O 、樹，或如何去遍歷一個圖。如果非要我去編寫一個排序算法的話，我只能說我所寫的肯定是很糟糕。一直以來，我所用的任何數據結構都是內建于編程語言當中。至于它們在背后是如何運作，對此我一概不清楚。此外，以前的我并不需要對內存進行管理，最多就只是在一個正在執行的進程拋出了“內存不足”的錯誤后，采取一些權變措施。而在我的編程生活中，也甚少使用到多維數組，可關聯數組卻成千上萬。而且，從一開始到現在，我都還未曾自己實現過數據結構。

就是這樣的我，在經過該學習計劃后，已然對被 Google 所雇傭充滿信心。這是一個漫長的計劃，以至于花費了我數月的時間。若您早已熟悉大部分的知識，那么也許能節省大量的時間。

如何使用它

下面所有的東西都只是一個概述。因此，你需要由上而下逐一地去處理它。

在學習過程中，我是使用 GitHub 特殊的語法特性 markdown flavor 去檢查計劃的進展，包括使用任務列表。(注：因極客頭條的 markdown 并不支持此語法，因此在下方做了刪除處理)

更多關于 Github-flavored markdown 的詳情

擁有一名 Googler 的心態

把一個（或兩個）印有“future Googler”的圖案打印出來，并用你誓要成功的眼神盯著它。

我得到了工作嗎？

我還沒去應聘。

因為我離完成學習（完成該瘋狂的計劃列表）還需要數天的時間，并打算在下周開始用一整天的時間，以編程的方式去解決問題。當然，這將會持續數周的時間。然后，我才通過使用在二月份所得到的一個介紹資格，去正式應聘 Google（沒錯，是二月份時就得到的）。

感謝 JP 的這次介紹。

跟隨著我

目前我仍在該計劃的執行過程中，如果你想跟隨我腳步去學習的話，可以登進我在 GoogleyAsHeck.com 上所寫的博客。

下面是我的聯系方式：

Twitter: @googleyasheck
Twitter: @StartupNextDoor
Google+: +Googleyasheck
LinkedIn: johnawasham

不要自以為自己足夠聰明

Google 的工程師都是才智過人的。但是，就算是工作在 Google 的他們，仍然會因為自己不夠聰明而感到一種不安。
天才程序員的神話

關于 Google

面向學生 —— Google 的職業生涯：技術開發指導
Google 檢索的原理：
- Google 檢索的發展史（視頻）
- Google 檢索的原理 —— 故事篇
- Google 檢索的原理
- Google 檢索的原理 —— Matt Cutts（視頻）
- Google 是如何改善其檢索算法（視頻）
系列文章：
- Google 檢索是如何處理移動設備
- Google 為了尋找大眾需求的秘密研究
- Google 檢索將成為你的下一個大腦
- Demis Hassabis 的心靈直白
書籍：Google 公司是如何運作的
由 Google 通告所制作 —— 2016年10月（視頻）

面試過程 & 通用的面試準備

視頻：
- 如何在 Google 工作 —— 考生指導課程（視頻）
- Google 招聘者所分享的技術面試小竅門（視頻）
- 如何在 Google 工作：技術型簡歷的準備（視頻）
文章：
- 三步成為 Googler
- 得到在 Google 的工作機會
  - 所有他所提及的事情都列在了下面
- （早已過期）如何得到 Google 的一份工作，面試題，應聘過程
- 手機設備屏幕的問題
附加的（雖然 Google 不建議，但我還是添加在此）：
- ABC：永遠都要去編程（Always Be Coding）
- 四步成為 Google 里一名沒有學位的員工
- 共享白板（Whiteboarding）
- Google 是如何看待應聘、管理和公司文化
- 程序開發面試中有效的白板（Whiteboarding）
- 震撼開發類面試第一集：
  - Gayle L McDowell —— 震撼開發類面試（視頻）
  - 震撼開發類面試 —— 作者 Gayle Laakmann McDowell（視頻）
- 如何在世界四強企業中獲得一份工作：
  - “如何在世界四強企業中獲得一份工作 —— Amazon、Facebook、Google 和 Microsoft”（視頻）
- 面試 Google 失敗

為你的面試選擇一種語言

在這，我就以下話題寫一篇短文 —— 重點：為在 Google 的面試選擇一種語言

在大多數公司的面試當中，你可以在編程這一環節，使用一種自己用起來較為舒適的語言去完成編程。但在 Google，你只有三種固定的選擇：

C++
Java
Python

有時你也可以使用下面兩種，但需要事先查閱說明。因為，說明中會有警告：

JavaScript
Ruby

你需要對你所選擇的語言感到非常舒適且足夠了解。

更多關于語言選擇的閱讀：

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

在此查看相關語言的資源

由于，我正在學習C、C++ 和 Python。因此，在下面你會看到部分關于它們的學習資料。相關書籍請看文章的底部。

在你開始之前

該列表已經持續更新了很長的一段時間，所以，我們的確很容易會對其失去控制。

這里列出了一些我所犯過的錯誤，希望您不要重滔覆轍。

1. 你不可能把所有的東西都記住

就算我查看了數小時的視頻，并記錄了大量的筆記。幾個月后的我，仍然會忘卻其中大部分的東西。所以，我翻閱了我的筆記，并將可回顧的東西制作成抽認卡（flashcard）（請往下看）

2. 使用抽認卡

為了解決善忘的問題，我制作了一些關于抽認卡的頁面，用于添加兩種抽認卡：正常的及帶有代碼的。每種卡都會有不同的格式設計。

而且，我還以移動設備為先去設計這些網頁，以使得在任何地方的我，都能通過我的手機及平板去回顧知識。

你也可以免費制作屬于你自己的抽認卡網站：

抽認卡頁面的代碼倉庫
我的抽認卡數據庫：有一點需要記住的是，我做事有點過頭，以至于把卡片都覆蓋到所有的東西上。從匯編語言和 Python 的細枝末節，乃至到機器學習和統計都被覆蓋到卡片上。而這種做法，對于 Google 的要求來說，卻是多余。

在抽認卡上做筆記： 若你第一次發現你知道問題的答案時，先不要急著把其標注成“已懂”。你需要做的，是去查看一下是否有同樣的抽認卡，并在你真正懂得如何解決問題之前，多問自己幾次。重復地問答可幫助您深刻記住該知識點。

3. 回顧，回顧，回顧

我留有一組 ASCII 碼表、OSI 堆棧、Big-O 記號及更多的小抄紙，以便在空余的時候可以學習。

每編程半個小時就要休息一下，并去回顧你的抽認卡。

4. 專注

在學習的過程中，往往會有許多令人分心的事占據著我們寶貴的時間。因此，專注和集中注意力是非常困難的。

你所看不到的

由于，這個巨大的列表一開始是作為我個人從 Google 面試指導筆記所形成的一個事件處理列表。因此，有一些我熟悉且普遍的技術在此都未被談及到：

SQL
Javascript
HTML、CSS 和其他前端技術

日常計劃

部分問題可能會花費一天的時間去學習，而部分則會花費多天。當然，有些學習并不需要我們懂得如何實現。

因此，每一天我都會在下面所列出的列表中選擇一項，并查看相關的視頻。然后，使用以下的一種語言去實現：

C —— 使用結構體和函數，該函數會接受一個結構體指針 * 及其他數據作為參數。 C++ —— 不使用內建的數據類型。 C++ —— 使用內建的數據類型，如使用 STL 的 std::list 來作為鏈表。 Python —— 使用內建的數據類型（為了持續練習 Python），并編寫一些測試去保證自己代碼的正確性。有時，只需要使用斷言函數 assert() 即可。此外，你也可以使用 Java 或其他語言。以上只是我的個人偏好而已。

為何要在這些語言上分別實現一次？

因為可以練習，練習，練習，直至我厭倦它，并完美地實現出來。（若有部分邊緣條件沒想到時，我會用書寫的形式記錄下來并去記憶）因為可以在純原生的條件下工作（不需垃圾回收機制的幫助下，分配/釋放內存（除了 Python））因為可以利用上內建的數據類型，以使得我擁有在現實中使用內建工具的經驗（在生產環境中，我不會去實現自己的鏈表）

就算我沒有時間去每一項都這么做，但我也會盡我所能的。

在這里，你可以查看到我的代碼：

C
C++
Python

你不需要記住每一個算法的內部原理。

在一個白板上寫代碼，而不要直接在計算機上編寫。在測試完部分簡單的輸入后，到計算機上再測試一遍。

必備知識

計算機是如何處理一段程序：
- CPU 是如何執行代碼（視頻）
- 機器碼指令（視頻）
編譯器
- 編譯器是如何在 ~1 分鐘內工作（視頻）
- Hardvard CS50 —— 編譯器（視頻）
- C++（視頻）
- 掌握編譯器的優化（C++）（視頻）
浮點數是如何存儲的：
- 簡單的 8-bit：浮點數的表達形式　—— 1（視頻 —— 在計算上有一個錯誤 —— 詳情請查看視頻的介紹）
- 32 bit：IEEE754 32-bit 浮點二進制（視頻）

算法復雜度 / Big-O / 漸進分析法

并不需要實現
Harvard CS50 —— 漸進表示（視頻）
Big O 記號（通用快速教程）（視頻）
Big O 記號（以及 Omega 和 Theta）—— 最佳數學解釋（視頻）
Skiena 算法：
- 視頻
- 幻燈片
對于算法復雜度分析的一次詳細介紹
增長階數（Orders of Growth）（視頻）
漸進性（Asymptotics）（視頻）
UC Berkeley Big O（視頻）
UC Berkeley Big Omega（視頻）
平攤分析法（Amortized Analysis）（視頻）
舉證“Big O”（視頻）
高級編程（包括遞歸關系和主定理）：
- 計算性復雜度：第一部
- 計算性復雜度：第二部
速查表（Cheat sheet）

如果部分課程過于學術性，你可直接跳到文章底部，去查看離散數學的視頻以獲取相關背景知識。

數據結構

數組（Arrays）
- 實現一個可自動調整大小的動態數組。
- 介紹：
  - 數組（視頻）
  - 數組的基礎知識（視頻）
  - 多維數組（視頻）
  - 動態數組（視頻）
  - 不規則數組（視頻）
  - 調整數組的大小（視頻）
- 實現一個動態數組（可自動調整大小的可變數組）：
  - 練習使用數組和指針去編碼，并且指針是通過計算去跳轉而不是使用索引
  - 通過分配內存來新建一個原生數據型數組
    - 可以使用 int 類型的數組，但不能使用其語法特性
    - 從大小為16或更大的數（使用2的倍數 —— 16、32、64、128）開始編寫
  - size() —— 數組元素的個數
  - capacity() —— 可容納元素的個數
  - is_empty()
  - at(index) —— 返回對應索引的元素，且若索引越界則憤然報錯
  - push(item)
  - insert(index, item) —— 在指定索引中插入元素，并把后面的元素依次后移
  - prepend(item) —— 可以使用上面的 insert 函數，傳參 index 為 0
  - pop() —— 刪除在數組末端的元素，并返回其值
  - delete(index) —— 刪除指定索引的元素，并把后面的元素依次前移
  - remove(item) —— 刪除指定值的元素，并返回其索引（即使有多個元素）
  - find(item) —— 尋找指定值的元素并返回其中第一個出現的元素其索引，若未找到則返回 -1
  - resize(new_capacity) // 私有函數
    - 若數組的大小到達其容積，則變大一倍
    - 獲取元素后，若數組大小為其容積的1/4，則縮小一半
- 時間復雜度
  - 在數組末端增加/刪除、定位、更新元素，只允許占 O(1) 的時間復雜度（平攤（amortized）去分配內存以獲取更多空間）
  - 在數組任何地方插入/移除元素，只允許 O(n) 的時間復雜度
- 空間復雜度
  - 因為在內存中分配的空間鄰近，所以有助于提高性能
  - 空間需求 = （大于或等于 n 的數組容積）* 元素的大小。即便空間需求為 2n，其空間復雜度仍然是 O(n)
鏈表（Linked Lists）
- 介紹：
  - 單向鏈表（視頻）
  - CS 61B —— 鏈表（視頻）
- C 代碼（視頻）
  - 并非看完整個視頻，只需要看關于節點結果和內存分配那一部分即可
- 鏈表 vs 數組：
  - 基本鏈表 Vs 數組（視頻）
  - 在現實中，鏈表 Vs 數組（視頻）
- 為什么你需要避免使用鏈表（視頻）
- 的確：你需要關于“指向指針的指針”的相關知識：（因為當你傳遞一個指針到一個函數時，該函數可能會改變指針所指向的地址）該頁只是為了讓你了解“指向指針的指針”這一概念。但我并不推薦這種鏈式遍歷的風格。因為，這種風格的代碼，其可讀性和可維護性太低。
  - 指向指針的指針
- 實現（我實現了使用尾指針以及沒有使用尾指針這兩種情況）：
  - size() —— 返回鏈表中數據元素的個數
  - empty() —— 若鏈表為空則返回一個布爾值 true
  - value_at(index) —— 返回第 n 個元素的值（從0開始計算）
  - push_front(value) —— 添加元素到鏈表的首部
  - pop_front() —— 刪除首部元素并返回其值
  - push_back(value) —— 添加元素到鏈表的尾部
  - pop_back() —— 刪除尾部元素并返回其值
  - front() —— 返回首部元素的值
  - back() —— 返回尾部元素的值
  - insert(index, value) —— 插入值到指定的索引，并把當前索引的元素指向到新的元素
  - erase(index) —— 刪除指定索引的節點
  - value_n_from_end(n) —— 返回倒數第 n 個節點的值
  - reverse() —— 逆序鏈表
  - remove_value(value) —— 刪除鏈表中指定值的第一個元素
- 雙向鏈表
  - 介紹（視頻）
  - 并不需要實現
堆棧（Stack）
- 堆棧（視頻）
- 使用堆棧 —— 后進先出（視頻）
- 可以不實現，因為使用數組來實現并不重要
隊列（Queue）
- 使用隊列 —— 先進先出（視頻）
- 隊列（視頻）
- 原型隊列/先進先出（FIFO）
- 優先級隊列（視頻）
- 使用含有尾部指針的鏈表來實現:
  - enqueue(value) —— 在尾部添加值
  - dequeue() —— 刪除最早添加的元素并返回其值（首部元素）
  - empty()
- 使用固定大小的數組實現：
  - enqueue(value) —— 在可容的情況下添加元素到尾部
  - dequeue() —— 刪除最早添加的元素并返回其值
  - empty()
  - full()
- 花銷：
  - 在糟糕的實現情況下，使用鏈表所實現的隊列，其入列和出列的時間復雜度將會是 O(n)。因為，你需要找到下一個元素，以致循環整個隊列
  - enqueue：O(1)（平攤（amortized）、鏈表和數組 [探測（probing）]）
  - dequeue：O(1)（鏈表和數組）
  - empty：O(1)（鏈表和數組）
哈希表（Hash table）
- 視頻：
  - 鏈式哈希表（視頻）
  - Table Doubling 和 Karp-Rabin（視頻）
  - Open Addressing 和密碼型哈希（Cryptographic Hashing）（視頻）
  - PyCon 2010：The Mighty Dictionary（視頻）
  - （進階）隨機取樣（Randomization）：全域哈希（Universal Hashing）& 完美哈希（Perfect Hashing）（視頻）
  - （進階）完美哈希（Perfect hashing）（視頻）
- 在線課程：
  - 哈希函數的掌握（視頻）
  - 使用哈希表（視頻）
  - 哈希表的支持（視頻）
  - 哈希表的語言支持（視頻）
  - 基本哈希表（視頻）
  - 數據結構（視頻）
  - 電話薄問題（Phone Book Problem）（視頻）
  - 分布式哈希表：
    - Dropbox 中的瞬時上傳及存儲優化（視頻）
    - 分布式哈希表（視頻）
- 使用線性探測的數組去實現
  - hash(k, m) —— m 是哈希表的大小
  - add(key, value) —— 如果 key 已存在則更新值
  - exists(key)
  - get(key)
  - remove(key)

樹（Trees）

樹 —— 筆記 & 背景
- 系列：基本樹（視頻）
- 系列：樹（視頻）
- 基本的樹形結構
- 遍歷
- 操作算法
- BFS（廣度優先檢索，breadth-first search）
  - MIT（視頻）
  - 層序遍歷（使用隊列的 BFS 算法）
    - 時間復雜度： O(n)
    - 空間復雜度：
      - 最好情況： O(1)
      - 最壞情況：O(n/2)=O(n)
- DFS（深度優先檢索，depth-first search）
  - MIT（視頻）
  - 筆記：
    - 時間復雜度：O(n)
    - 空間復雜度：
      - 最好情況：O(log n) - 樹的平均高度
      - 最壞情況：O(n)
  - 中序遍歷（DFS：左、節點本身、右）
  - 后序遍歷（DFS：左、右、節點本身）
  - 先序遍歷（DFS：節點本身、左、右）
二叉查找樹（Binary search trees）：BSTs
- 二叉查找樹概覽（視頻）
- 系列（視頻）
  - 從符號表開始到 BST 程序
- 介紹（視頻）
- MIT（視頻）
- C/C++:
  - 二叉查找樹 —— 在 C/C++ 中實現（視頻）
  - BST 的實現 —— 在堆棧和堆中的內存分配（視頻）
  - 在二叉查找樹中找到最小和最大的元素（視頻）
  - 尋找二叉樹的高度（視頻）
  - 二叉樹的遍歷 —— 廣度優先和深度優先策略（視頻）
  - 二叉樹：層序遍歷（視頻）
  - 二叉樹的遍歷：先序、中序、后序（視頻）
  - 判斷一棵二叉樹是否為二叉查找樹（視頻）
  - 從二叉查找樹中刪除一個節點（視頻）
  - 二叉查找樹中序遍歷的后繼者（視頻）
- 實現：
  - insert // 往樹上插值
  - get_node_count // 查找樹上的節點數
  - print_values // 從小到大打印樹中節點的值
  - delete_tree
  - is_in_tree // 如果值存在于樹中則返回 true
  - get_height // 返回節點所在的高度（如果只有一個節點，那么高度則為1）
  - get_min // 返回樹上的最小值
  - get_max // 返回樹上的最大值
  - is_binary_search_tree
  - delete_value
  - get_successor // 返回給定值的后繼者，若沒有則返回-1
堆（Heap） / 優先級隊列（Priority Queue） / 二叉堆（Binary Heap）
- 可視化是一棵樹，但通常是以線性的形式存儲（數組、鏈表）
- 堆
- 介紹（視頻）
- 無知的實現（視頻）
- 二叉樹（視頻）
- 關于樹高的討論（視頻）
- 基本操作（視頻）
- 完全二叉樹（視頻）
- 偽代碼（視頻）
- 堆排序 —— 跳到起點（視頻）
- 堆排序（視頻）
- 構建一個堆（視頻）
- MIT：堆與堆排序（視頻）
- CS 61B Lecture 24：優先級隊列（視頻）
- 構建線性時間復雜度的堆（大頂堆）
- 實現一個大頂堆：
  - insert
  - sift_up —— 用于插入元素
  - get_max —— 返回最大值但不移除元素
  - get_size() —— 返回存儲的元素數量
  - is_empty() —— 若堆為空則返回 true
  - extract_max —— 返回最大值并移除
  - sift_down —— 用于獲取最大值元素
  - remove(i) —— 刪除指定索引的元素
  - heapify —— 構建堆，用于堆排序
  - heap_sort() —— 拿到一個未排序的數組，然后使用大頂堆進行就地排序
    - 注意：若用小頂堆可節省操作，但導致空間復雜度加倍。（無法做到就地）
字典樹（Tries）
- 需要注意的是，字典樹各式各樣。有些有前綴，而有些則沒有。有些使用字符串而不使用比特位來追蹤路徑。
- 閱讀代碼，但不實現。
- 數據結構筆記及編程技術
- 短課程視頻：
  - 對字典樹的介紹（視頻）
  - 字典樹的性能（視頻）
  - 實現一棵字典樹（視頻）
- 字典樹：一個被忽略的數據結構
- 高級編程 —— 使用字典樹
- 標準教程（現實中的用例）（視頻）
- MIT，高階數據結構，使用字符串追蹤路徑（可事半功倍）
平衡查找樹（Balanced search trees）
- 掌握至少一種平衡查找樹（并懂得如何實現）：
- “在各種平衡查找樹當中，AVL 樹和2-3樹已經成為了過去，而紅黑樹（red-black trees）看似變得越來越受人青睞。這種令人特別感興趣的數據結構，亦稱伸展樹（splay tree）。它可以自我管理，且會使用輪換來移除任何訪問過根節點的 key。” —— Skiena
- 因此，在各種各樣的平衡查找樹當中，我選擇了伸展樹來實現。雖然，通過我的閱讀，我發現在 Google 的面試中并不會被要求實現一棵平衡查找樹。但是，為了勝人一籌，我們還是應該看看如何去實現。在閱讀了大量關于紅黑樹的代碼后，我才發現伸展樹的實現確實會使得各方面更為高效。
  - 伸展樹：插入、查找、刪除函數的實現，而如果你最終實現了紅黑樹，那么請嘗試一下：
  - 跳過刪除函數，直接實現搜索和插入功能
- 我希望能閱讀到更多關于 B 樹的資料，因為它也被廣泛地應用到大型的數據庫當中。
- 自平衡二叉查找樹
- AVL 樹
  - 實際中：我能告訴你的是，該種樹并無太多的用途，但我能看到有用的地方在哪里：AVL 樹是另一種平衡查找樹結構。其可支持時間復雜度為 O(log n) 的查詢、插入及刪除。它比紅黑樹嚴格意義上更為平衡，從而導致插入和刪除更慢，但遍歷卻更快。正因如此，才彰顯其結構的魅力。只需要構建一次，就可以在不重新構造的情況下讀取，適合于實現諸如語言字典（或程序字典，如一個匯編程序或解釋程序的操作碼）。
  - MIT AVL 樹 / AVL 樹的排序（視頻）
  - AVL 樹（視頻）
  - AVL 樹的實現（視頻）
  - 分離與合并
- 伸展樹
  - 實際中：伸展樹一般用于緩存、內存分配者、路由器、垃圾回收者、數據壓縮、ropes（字符串的一種替代品，用于存儲長串的文本字符）、Windows NT（虛擬內存、網絡及文件系統）等的實現。
  - CS 61B：伸展樹（Splay trees）（視頻）
  - MIT 教程：伸展樹（Splay trees）：
    - 該教程會過于學術，但請觀看到最后的10分鐘以確保掌握。
    - 視頻
- 2-3查找樹
  - 實際中：2-3樹的元素插入非常快速，但卻有著查詢慢的代價（因為相比較 AVL 樹來說，其高度更高）。
  - 你會很少用到2-3樹。這是因為，其實現過程中涉及到不同類型的節點。因此，人們更多地會選擇紅黑樹。
  - 2-3樹的直感與定義（視頻）
  - 2-3樹的二元觀點
  - 2-3樹（學生敘述）（視頻）
- 2-3-4樹 (亦稱2-4樹)
  - 實際中：對于每一棵2-4樹，都有著對應的紅黑樹來存儲同樣順序的數據元素。在2-4樹上進行插入及刪除操作等同于在紅黑樹上進行顏色翻轉及輪換。這使得2-4樹成為一種用于掌握紅黑樹背后邏輯的重要工具。這就是為什么許多算法引導文章都會在介紹紅黑樹之前，先介紹2-4樹，盡管2-4樹在實際中并不經常使用。
  - CS 61B Lecture 26：平衡查找樹（視頻）
  - 自底向上的2-4樹（視頻）
  - 自頂向下的2-4樹（視頻）
- B 樹
  - 有趣的是：為啥叫 B 仍然是一個神秘。因為 B 可代表波音（Boeing）、平衡（Balanced）或 Bayer（聯合創造者）
  - 實際中：B 樹會被廣泛適用于數據庫中，而現代大多數的文件系統都會使用到這種樹（或變種)。除了運用在數據庫中，B 樹也會被用于文件系統以快速訪問一個文件的任意塊。但存在著一個基本的問題，那就是如何將文件塊 i 轉換成一個硬盤塊（或一個柱面-磁頭-扇區）上的地址。
  - B 樹
  - B 樹的介紹（視頻）
  - B 樹的定義及其插入操作（視頻）
  - B 樹的刪除操作（視頻）
  - MIT 6.851 —— 內存層次模塊（Memory Hierarchy Models）（視頻）
    - 覆蓋有高速緩存參數無關型（cache-oblivious）B 樹和非常有趣的數據結構
    - 頭37分鐘講述的很專業，或許可以跳過（B 指塊的大小、即緩存行的大小）
- 紅黑樹
  - 實際中：紅黑樹提供了在最壞情況下插入操作、刪除操作和查找操作的時間保證。這些時間值的保障不僅對時間敏感型應用有用，例如實時應用，還對在其他數據結構中塊的構建非常有用，而這些數據結構都提供了最壞情況下的保障；例如，許多用于計算幾何學的數據結構都可以基于紅黑樹，而目前 Linux 系統所采用的完全公平調度器（the Completely Fair Scheduler）也使用到了該種樹。在 Java 8中，紅黑樹也被用于存儲哈希列表集合中相同的數據，而不是使用鏈表及哈希碼。
  - Aduni —— 算法 —— 課程4（該鏈接直接跳到開始部分）（視頻）
  - Aduni —— 算法 —— 課程5（視頻）
  - 黑樹（Black Tree）
  - 二分查找及紅黑樹的介紹
N 叉樹（K 叉樹、M 叉樹）
- 注意：N 或 K 指的是分支系數（即樹的最大分支數）：
  - 二叉樹是一種分支系數為2的樹
  - 2-3樹是一種分支系數為3的樹
- K 叉樹

排序（Sorting）

筆記:
- 實現各種排序 & 知道每種排序的最壞、最好和平均的復雜度分別是什么場景:
  - 不要用冒泡排序 - 大多數情況下效率感人 - 時間復雜度 O(n^2), 除非 n <= 16
- 排序算法的穩定性 (“快排是穩定的么?”)
  - 排序算法的穩定性
  - 排序算法的穩定性
  - 排序算法的穩定性
  - 排序算法的穩定性
  - 排序算法 - 穩定性
- 哪種排序算法可以用鏈表？哪種用數組？哪種兩者都可？
  - 并不推薦對一個鏈表排序，但歸并排序是可行的.
  - 鏈表的歸并排序
關于堆排序，請查看前文堆的數據結構部分。堆排序很強大，不過是非穩定排序。
冒泡排序 (video)
冒泡排序分析 (video)
插入排序 & 歸并排序 (video)
插入排序 (video)
歸并排序 (video)
快排 (video)
選擇排序 (video)
斯坦福大學關于排序算法的視頻:
- 課程 15 | 編程抽象 (video)
- 課程 16 | 編程抽象 (video)
Shai Simonson 視頻, Aduni.org:
- 算法 - 排序 - 第二講 (video)
- 算法 - 排序2 - 第三講 (video)
Steven Skiena 關于排序的視頻:
- 課程從 26:46 開始 (video)
- 課程從 27:40 開始 (video)
- 課程從 35:00 開始 (video)
- 課程從 23:50 開始 (video)
加州大學伯克利分校（UC Berkeley）大學課程:
- CS 61B 課程 29: 排序 I (video)
- CS 61B 課程 30: 排序 II (video)
- CS 61B 課程 32: 排序 III (video)
- CS 61B 課程 33: 排序 V (video)
- 歸并排序:
- 使用外部數組
- 對原數組直接排序
- 快速排序:
- 實現
- 實現
實現:
- 歸并：平均和最差情況的時間復雜度為 O(n log n)。
- 快排：平均時間復雜度為 O(n log n)。
- 選擇排序和插入排序的最壞、平均時間復雜度都是 O(n^2)。
- 關于堆排序，請查看前文堆的數據結構部分。
有興趣的話，還有一些補充 - 但并不是必須的:
- 基數排序
- 基數排序 (video)
- 基數排序, 計數排序 (線性時間內) (video)
- 隨機算法: 矩陣相乘, 快排, Freivalds’ 算法 (video)
- 線性時間內的排序 (video)

圖（Graphs）

圖論能解決計算機科學里的很多問題，所以這一節會比較長，像樹和排序的部分一樣。

Yegge 的筆記:
- 有 3 種基本方式在內存里表示一個圖:
  - 對象和指針
  - 矩陣
  - 鄰接表
- 熟悉以上每一種圖的表示法，并了解各自的優缺點
- 寬度優先搜索和深度優先搜索 - 知道它們的計算復雜度和設計上的權衡以及如何用代碼實現它們
- 遇到一個問題時，首先嘗試基于圖的解決方案，如果沒有再去嘗試其他的。
Skiena 教授的課程 - 很不錯的介紹:
- CSE373 2012 - 課程 11 - 圖的數據結構 (video)
- CSE373 2012 - 課程 12 - 廣度優先搜索 (video)
- CSE373 2012 - 課程 13 - 圖的算法 (video)
- CSE373 2012 - 課程 14 - 圖的算法 (1) (video)
- CSE373 2012 - 課程 15 - 圖的算法 (2) (video)
- CSE373 2012 - 課程 16 - 圖的算法 (3) (video)
圖 (復習和其他):
- 6.006 單源最短路徑問題 (video)
- 6.006 Dijkstra 算法 (video)
- 6.006 Bellman-Ford 算法(video)
- 6.006 Dijkstra 效率優化 (video)
- Aduni: 圖的算法 I - 拓撲排序, 最小生成樹, Prim 算法 - 第六課 (video)
- Aduni: 圖的算法 II - 深度優先搜索, 廣度優先搜索, Kruskal 算法, 并查集數據結構 - 第七課 (video)
- Aduni: 圖的算法 III: 最短路徑 - 第八課 (video)
- Aduni: 圖的算法. IV: 幾何算法介紹 - 第九課 (video)
- CS 61B 2014 (從 58:09 開始) (video)
- CS 61B 2014: 加權圖 (video)
- 貪心算法: 最小生成樹 (video)
- 圖的算法之強連通分量 Kosaraju 算法 (video)
完整的 Coursera 課程:
- 圖的算法 (video)
Yegge: 如果有機會，可以試試研究更酷炫的算法:
- Dijkstra 算法 - 上文 - 6.006
- A* 算法
  - A* 算法
  - A* 尋路教程 (video)
  - A* 尋路 (E01: 算法解釋) (video)
我會實現:
- DFS 鄰接表 (遞歸)
- DFS 鄰接表 (棧迭代)
- DFS 鄰接矩陣 (遞歸)
- DFS 鄰接矩陣 (棧迭代)
- BFS 鄰接表
- BFS 鄰接矩陣
- 單源最短路徑問題 (Dijkstra)
- 最小生成樹
- 基于 DFS 的算法 (根據上文 Aduni 的視頻):
  - 檢查環 (我們會先檢查是否有環存在以便做拓撲排序)
  - 拓撲排序
  - 計算圖中的連通分支
  - 列出強連通分量
  - 檢查雙向圖

可以從 Skiena 的書（參考下面的書推薦小節）和面試書籍中學習更多關于圖的實踐。

總結

以上是生活随笔為你收集整理的坚持完成这套学习手册，你就可以去 Google 面试了的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： Gabor滤波小结整理
下一篇：如何让机器获得幽默感——Goolge图学

3atv精品不卡视频,97人人超碰国产精品最新,中文字幕av一区二区三区人妻少妇,久久久精品波多野结衣,日韩一区二区三区精品

编程问答

坚持完成这套学习手册，你就可以去 Google 面试了

這是？

目錄

為何要用到它？

如何使用它

擁有一名 Googler 的心態

我得到了工作嗎？

跟隨著我

不要自以為自己足夠聰明

關于 Google

相關視頻資源

面試過程 & 通用的面試準備

為你的面試選擇一種語言

在你開始之前

1. 你不可能把所有的東西都記住

2. 使用抽認卡

3. 回顧，回顧，回顧

4. 專注

你所看不到的

日常計劃

必備知識

算法復雜度 / Big-O / 漸進分析法

數據結構

數組（Arrays）

鏈表（Linked Lists）

堆棧（Stack）

隊列（Queue）

哈希表（Hash table）

更多的知識

二分查找（Binary search）

按位運算（Bitwise operations）

樹（Trees）

樹 —— 筆記 & 背景

二叉查找樹（Binary search trees）：BSTs

堆（Heap） / 優先級隊列（Priority Queue） / 二叉堆（Binary Heap）

字典樹（Tries）

平衡查找樹（Balanced search trees）

N 叉樹（K 叉樹、M 叉樹）

排序（Sorting）

圖（Graphs）

更多知識

遞歸（Recursion）

動態規劃（Dynamic Programming）

組合（Combinatorics） (n 中選 k 個) & 概率（Probability）

NP, NP-完全和近似算法

總結