Coding Interview University

原先我为了成为一个软件工程师而建立这份简单的学习主题清单， 但这份清单随着时间而膨胀成今天这样。在做完这份清单上的每个目标后，我成为了 Amazon 的软件开发工程师! 你或许不需要像我一样学习这么多。但是，让你成为一位称职工程师所需要的知识都在这里了。

我每天自学8~12小时，这样持续了好几个月。这是我的故事：为什么我为了 Google 面试而自学了8个月。

在这份清单内的主题会让你拥有足够的知识去面对几乎每家软件公司的技术面试，包括科技巨头：Amazon、Facebook、Google，以及 Microsoft。

祝你好运!

这是？

这是我为了从 web 开发者（自学、非计算机科学学位）蜕变至 Google 软件工程师所制定的计划，其内容历时数月。

这份清单适用于 新手软件工程师，或者想从软件/网站开发转向软件工程（需要计算机科学知识）的人员。如果你有多年的经验，并且声称拥有多年的软件工程经验，并且期待一次更艰难的面试。

如果你具有多年的软件/网页开发经验，请注意，大型软件公司（例如 Google，Amazon，Facebook 和 Microsoft）将软件工程视为不同于软件/网页开发，并且它们需要计算机科学知识。

如果你想成为可靠性工程师或运维工程师，请从可选列表（网络，安全）中学习更多。

---

目录

• 这是？
• 为何要用到它？
• 如何使用它
• 不要觉得自己不够聪明
• 相关视频资源
• 面试过程 & 通用的面试准备
• 为你的面试选择一种语言
• 书单
• 在你开始之前
• 没有包含的内容
• 必备知识
• 日常计划
• 算法复杂度 / Big-O / 渐进分析法
• 数据结构
  • 数组（Arrays）
  • 链表（Linked Lists）
  • 堆栈（Stack）
  • 队列（Queue）
  • 哈希表（Hash table）
• 更多的知识
  • 二分查找（Binary search）
  • 按位运算（Bitwise operations）
• 树（Trees）
  • 树 —— 笔记 & 背景
  • 二叉查找树（Binary search trees）：BSTs
  • 堆（Heap） / 优先级队列（Priority Queue） / 二叉堆（Binary Heap）
  • 平衡查找树（Balanced search trees）（基本概念，非细节）
  • 遍历：前序、中序、后序、BFS、DFS
• 排序
  • 选择排序（selection）
  • 插入排序（insertion）
  • 堆排序（heapsort）
  • 快速排序（quicksort）
  • 归并排序（merge sort）
• 图（Graphs）
  • 有向图（directed）
  • 无向图（undirected）
  • 邻接矩阵（adjacency matrix）
  • 邻接表（adjacency list）
  • 遍历：广度优先(BFS), 深度优先(DFS)
• 更多知识
  • 递归
  • 动态规划
  • 面向对象编程
  • 设计模式
  • 组合 & 概率
  • NP, NP-完全和近似算法
  • 缓存
  • 进程和线程
  • 测试
  • 调度
  • 字符串搜索和操作
  • 字典树（Tries）
  • 浮点数
  • Unicode
  • 字节顺序
  • 网络
• 系统设计、可伸缩性、数据处理（如果你有4+年经验）
• 终面
• 编程问题练习
• 编程练习和挑战
• 当你临近面试时
• 你的简历
• 当面试来临的时候
• 问面试官的问题
• 当你获得了梦想的职位

---------------- 下面的内容是可选的 ----------------

• 额外书籍
• 附加学习
  • 编译器
  • Emacs and vi(m)
  • Unix 命令行工具
  • 信息论
  • 奇偶校验位 & 汉明码 (视频)
  • 系统熵值
  • 密码学
  • 压缩
  • 计算机安全
  • 垃圾回收
  • 并行编程
  • 消息传递，序列化和队列化的系统
  • A*搜索算法
  • 快速傅里叶变换
  • 布隆过滤器
  • HyperLogLog
  • 局部敏感哈希
  • van Emde Boas 树
  • 增强数据结构
  • 平衡查找树
    • AVL 树
    • 伸缩树（Splay tree）
    • 红黑树
    • 2-3 查找树
    • 2-3-4 树(也称 2-4 树)
    • N-ary (K-ary, M-ary)树
    • B 树
  • k-D 树
  • 跳表
  • 网络流
  • 不相交集 & 联合查找
  • 快速处理的数学
  • 树堆 (Treap)
  • 线性规划
  • 几何：凸包（Geometry, Convex hull）
  • 离散数学
  • 机器学习
• 一些主题的额外内容
• 视频系列
• 计算机科学课程
• 论文

---

为何要用到它？

当我开始这个项目时，我不知道堆和栈的区别，不了解时间复杂度（Big-O）、树，或如何去遍历一个图。如果非要我去编写一个排序算法的话，我只能说我所写的肯定是很糟糕。一直以来，我所用的任何数据结构都是内建于编程语言当中。至于它们在背后是如何运作，对此我一概不清楚。此外，以前的我并不需要对内存进行管理，最多就只是在一个正在执行的进程抛出了“内存不足”的错误后，才会去找解决方法。在我的编程生涯中，虽然我有用过多维数组，也用过关联数组成千上万次，但我从来没有自己实现过数据结构。

这是一个漫长的计划，以至于花费了我数月的时间。若你早已熟悉大部分的知识，那么也许能节省大量的时间。

如何使用它

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

在学习过程中，我使用 GitHub 特殊语法的 markdown 去检查计划的进展，包括使用包含任务进度的任务列表。

创建一个新的分支，以便你可以像这样去勾选计划的进展：直接往方括号中填写一个字符 x 即可：[x]。

Fork一个分支，并跟随以下的指令

通过单击 Fork 按钮来 fork GitHub 仓库：jwasham/coding-interview-university

克隆项目到本地

git checkout -b progress

git remote add jwasham https://github.com/jwasham/coding-interview-university

git fetch --all

在你完成了一些修改后，在框框中打 x

git add .

git commit -m "Marked x"

git rebase jwasham/main

git push --set-upstream origin progress

git push --force

更多关于 Github-flavored markdown 的详情

不要觉得自己不够聪明

• 大多数成功的软件工程师都非常聪明，但他们都有一种觉得自己不够聪明的不安全感。
• 天才程序员的神话
• 不要单打独斗：面对技术中的隐形怪物

相关视频资源

部分视频只能通过在 Coursera 或者 Edx 课程上注册登录才能观看。这些视频被称为网络公开课程（MOOC）。有时候某些课程需要等待好几个月才能获取，这期间你无法观看这些课程的影片。

很感谢你能帮我把网络公开课程的视频链接转换成公开的，可持续访问的视频源，比如 YouTube 视频，以代替那些在线课程的视频。此外，一些大学的讲座视频也是我所青睐的。

面试过程 & 通用的面试准备

• ABC：不要停止编程（Always Be Coding）
• 白板编程（Whiteboarding）
• 揭秘技术招聘
• 如何在科技四强企业中获得一份工作：
  • “如何在科技四强企业中获得一份工作 —— Amazon、Facebook、Google 和 Microsoft”（视频）
• 解密开发类面试第一集：
  • Gayle L McDowell —— 解密开发类面试（视频）
  • 解密开发类面试 —— 作者 Gayle Laakmann McDowell（视频）
• 解密 Facebook 编码面试：
  • 方法
  • 问题演练
• 准备课程：
  • 软件工程师面试发布（收费课程）：
    • 从前 Google 面试官身上学习如何准备自己，让自己能够应付软件工程师的面试。
  • Python 数据结构，算法和面试（收费课程）：
    • Python 面试准备课程，内容涉及数据结构，算法，模拟面试等。
  • Python 的数据结构和算法简介（Udacity 免费课程）：
    • 免费的 Python 数据结构和算法课程。
  • 数据结构和算法纳米学位！（Udacity 收费纳米学位）：
    • 获得超过100种数据结构和算法练习以及指导的动手练习，专门导师帮助你在面试和职场中做好准备。
  • 探究行为面试（Educative 免费课程）：
    • 很多时候，不是你的技术能力会阻碍你获得理想的工作，而是你在行为面试中的表现。

为你的面试选择一种语言

你可以在编程这一环节，使用一种自己用起来较为舒适的语言去完成编程，但对于大公司，你只有三种固定的选择：

• 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/

在此查看相关语言的资源

由于我正在学习C、C++ 和 Python，因此在下面你会看到部分关于它们的学习资料。相关书籍请看文章的底部。

书单

为了节省你的时间，以下是比我使用过的更缩减的书单。

面试准备

• Programming Interviews Exposed: Coding Your Way Through the Interview, 4th Edition
  • 附有 C++ 和 Java 解答
  • 这是在练习 Cracking the Coding Interview 之前一个很好的热身
  • 不太困难，大多数问题可能比你在面试中看到的要容易（根据我的阅读）
• Cracking the Coding Interview, 6th Edition
  • 附有 Java 答案

如果你有额外的时间：

选择以下之一：

• Elements of Programming Interviews (C++ version)
• Elements of Programming Interviews in Python
• Elements of Programming Interviews (Java version)
  • 书
  • 配套项目──书中每个问题的方法和测试用例

编程语言精选

你需要选择面试语言（请参见上文）。

这是我按语言给出的建议。我没有所有语言的资源，欢迎贡献。

如果你通读其中之一，你应该具备了开始解决编程问题所需的所有数据结构和算法知识。除非你需要复习，否则你可以跳过此项目中的所有视频讲座。

额外编程语言的精选资源

C++

我没有读过这两本书，但是它们颇受好评，作者是 Sedgewick，他非常厉害。

• Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching
• Algorithms in C++ Part 5: Graph Algorithms
• Open Data Structures in C++
  • 丰富而详细的数据结构和算法集合
  • 非常适合初学者

如果你有更好的 C++ 书籍，请告诉我。我正在搜集全面的资源。

Java

• 算法（Sedgewick 和 Wayne）
  • 包含课程内容（和Sedgewick！）的视频
    • 第一部分
    • 第二部分

或者：

• Java 数据结构和算法
  • 作者：Goodrich、Tamassia、Goldwasser
  • 用作 UC Berkeley 的 CS 入门课程的可选教材
  • 请参阅下面有关 Python 版本的我的读书报告，这本书涵盖了相同的主题

Python

• Python数据结构和算法
  • 作者：Goodrich、Tamassia、Goldwasser
  • 我非常喜爱这本书，它包含了所有东西
  • 很 Python 的代码
  • 我的读书报告：startupnextdoor.com/book-report-data-structures-and-algorithms-in-python
• Open Data Structures in Python

在你开始之前

该列表已经持续更新了很长的一段时间，所以，我们的确很容易会对其失去控制。

这里列出了一些我所犯过的错误，希望你不要重滔覆辙。

1. 你不可能把所有的东西都记住

就算我观看了数小时的视频，并记录了大量的笔记，几个月后的我，仍然会忘却其中大部分的东西。所以，我花了3天翻阅我的笔记，并制作成抽认卡（flashcard）帮助我复习：

请阅读以下的文章以免重蹈覆辙:

记住计算机科学知识。

有人推荐给我的课程（但我还沒看过）：学习如何学习。

2. 使用抽认卡

为了解决善忘的问题，我制作了一个抽认卡的网页，用于添加两种抽认卡：一般的及带有代码的。每种卡都会有不同的格式设计。

而且，我还以移动设备为先去设计这些网页，以使得在任何地方，我都能通过我的手机及平板去回顾知识。

你也可以免费制作属于你自己的抽认卡网站：

• 抽认卡页面的代码仓库
• 我的抽认卡数据库 ── 旧 1200 张
• 我的抽认卡数据库 ── 新 1800 张

有一点需要记住的是，我做事有点过头，以至于卡片都覆盖到所有的东西上，从汇编语言和 Python 的细枝末节，到机器学习和统计都被覆盖到卡片上。而这种做法，对于要求来说是多余的。

在抽认卡上做笔记： 若你第一次发现你知道问题的答案时，先不要急着把其标注成“已知”。反复复习这张抽认卡，直到每次都能答对后才是真正学会了这个问题。反复地问答可帮助你深刻记住该知识点。

这里有个替代我抽认卡的网站 Anki，很多人向我推荐过它。这个网站用同一个字卡重复出现的方式让你牢牢地记住知识。这个网站非常容易使用，支持多平台，并且有云端同步功能。在 iOS 平台上收费25美金，其他平台免费。

这是我用 Anki 这个网站里的格式所储存的抽认卡资料库: ankiweb.net/shared/info/25173560 （感谢 @xiewenya）

3. 复习，复习，再复习

我留有一组 ASCII 码表、OSI 堆栈、Big-O 记号及更多的抽认卡，以便在空余的时候可以学习。

编程累了就休息半个小时，并去复习你的抽认卡。

4. 专注

在学习的过程中，往往会有许多令人分心的事占据着我们宝贵的时间。因此，专注和集中注意力是非常困难的。放点纯音乐能帮上一些忙。

没有包含的内容

有一些熟悉且普遍的技术在此未被谈及到：

• SQL
• Javascript
• HTML、CSS 和其他前端技术

日常计划

部分问题可能会花费一天的时间去学习，而有些则会花费多天。当然，有些学习并不需要我们懂得如何实现。

因此，每一天我都会在下面所列出的列表中选择一项，并观看相关的视频。然后，使用以下的一种语言去实现：

• C —— 使用结构体和函数，该函数会接受一个结构体指针 * 及其他数据作为参数。
• C++ —— 不使用内建的数据类型。
• C++ —— 使用内建的数据类型，如使用 STL 的 std::list 来作为链表。
• Python —— 使用内建的数据类型（为了持续练习 Python），并编写一些测试去保证自己代码的正确性。有时，只需要使用断言函数 assert() 即可。
• 此外，你也可以使用 Java 或其他语言。以上只是我的个人偏好而已。

你不需要学会所有的编程语言，你只需要专注在一种编程语言上。

为何要在这些语言上分别实现一次？

• 练习，练习，练习，直至我厌倦它，并正确无误地实现出来。（若有部分边缘条件没想到时，我会用书写的形式记录下来并去记忆）
• 在纯原生的条件下工作（不需垃圾回收机制的帮助下，手动分配/释放内存（除了 Python））
• 利用语言内建的数据类型，之后在实际工作的时候才能得心应手（在生产环境中，我不会去实现自己的链表）

就算我没有时间去每一项都这么做，但我也会尽我所能。

在这里你可以查看到我的代码：

• C
• C++
• Python

你不需要记住每一个算法的内部原理。

在一个白板上写代码，而不要直接在计算机上编写。在测试完部分简单的输入后，到计算机上再测试一遍。

必备知识

• 学习C语言

  • C 语言无处不在。在学习的过程中，你会在书籍，讲座，视频等任何地方看到它的身影
  • C程序设计语言，第二版
    • 这是一本简短的书，但是它将使你更好地使用 C 语言，并且如果你稍加练习，就会很快熟练。理解 C 可帮助你了解程序和内存的工作方式
    • 问题答案

• 计算机是如何处理一段程序：

  • CPU 是如何执行代码（视频）
  • 计算机如何计算（视频）
  • 寄存器和内存（视频）
  • 中央处理单元（视频）
  • 指令和程序（视频）

算法复杂度 / 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”（视频）
• TopCoder（包括递归关系和主定理）：
  • 计算性复杂度：第一部
  • 计算性复杂度：第二部
• 速查表（Cheat sheet）

数据结构

• 数组（Arrays）

  • 实现一个可自动调整大小的动态数组。
  • 介绍：
    • 数组（视频）
    • UC Berkeley CS61B - 线性数组和多维数组（视频）（从15分32秒开始）
    • 数组的基础知识（视频）
    • 多维数组（视频）
    • 动态数组（视频）
    • 不规则数组（视频）
    • 不规则数组（视频）
    • 调整数组的大小（视频）
  • 实现一个动态数组（可自动调整大小的可变数组）：
    • 练习使用数组和指针去编码，并且指针是通过计算去跳转而不是使用索引
    • 通过分配内存来新建一个原生数据型数组
      • 可以使用 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 —— 链表（一）（视频）
    • 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)

更多的知识

• 二分查找（Binary search）

  • 二分查找（视频）
  • 二分查找（视频）
  • 详情
  • 实现：
    • 二分查找（在一个已排序好的整型数组中查找）
    • 迭代式二分查找

• 按位运算（Bitwise operations）

  • Bits 速查表 ── 你需要知道大量2的幂数值（从2^1 到 2^16 及 2^32）
  • 好好理解位操作符的含义：&、|、^、~、>>、<<
    • 字码（words）
    • 好的介绍：
      位操作（视频）
    • C 语言编程教程 2-10：按位运算（视频）
    • 位操作
    • 按位运算
    • Bithacks
    • 位元抚弄者（The Bit Twiddler）
    • 交互式位元抚弄者（The Bit Twiddler Interactive）
    • 位操作技巧（Bit Hacks）（视频）
    • 练习位操作
  • 一补数和补码
    • 二进制：利 & 弊（为什么我们要使用补码）（视频）
    • 一补数（1s Complement）
    • 补码（2s Complement）
  • 计算置位（Set Bits）
    • 计算一个字节中置位（Set Bits）的四种方式（视频）
    • 计算比特位
    • 如何在一个 32 位的整型中计算置位（Set Bits）的数量
  • 交换值：
    • 交换（Swap）
  • 绝对值：
    • 绝对整型（Absolute Integer）

树（Trees）

• 树 —— 笔记 & 背景

  • 系列：树（视频）
  • 基本的树形结构
  • 遍历
  • 操作算法
  • BFS（广度优先检索，breadth-first search）和 DFS（深度优先检索，depth-first search）
    • BFS 笔记
      • 层序遍历（使用队列的 BFS 算法）
      • 时间复杂度： O(n)
      • 空间复杂度：
        • 最好情况：O(1)
        • 最坏情况：O(n/2)=O(n)
    • DFS 笔记：
      • 时间复杂度：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() —— 拿到一个未排序的数组，然后使用大顶堆或者小顶堆进行就地排序

排序（Sorting）

• 笔记:

  • 实现各种排序，知道每种排序的最坏、最好和平均的复杂度分别是什么场景:
    • 不要用冒泡排序 - 效率太差 - 时间复杂度 O(n^2), 除非 n <= 16
  • 排序算法的稳定性 ("快排是稳定的么?")
    • 排序算法的稳定性
    • 排序算法的稳定性
    • 排序算法的稳定性
    • 排序算法 - 稳定性
  • 哪种排序算法可以用链表？哪种用数组？哪种两者都可？
    • 并不推荐对一个链表排序，但归并排序是可行的.
    • 链表的归并排序

• 关于堆排序，请查看前文堆的数据结构部分。堆排序很强大，不过是非稳定排序。

• Sedgewick ── 归并排序（5个视频）

  • 1. 归并排序
  • 2. 自下而上的归并排序
  • 3. 排序复杂度
  • 4. 比较器
  • 5. 稳定性

• Sedgewick ── 快速排序（4个视频）

  • 1. 快速排序
  • 2. 选择
  • 3. 重复键值
  • 4. 系统排序

• 冒泡排序（视频）

• 冒泡排序分析（视频）

• 插入排序 & 归并排序（视频）

• 插入排序（视频）

• 归并排序（视频）

• 快排（视频）

• 选择排序（视频）

• 归并排序代码：

  • 使用外部数组（C语言）
  • 使用外部数组（Python语言）
  • 对原数组直接排序（C++）

• 快速排序代码：

  • 实现（C语言）
  • 实现（C语言）
  • 实现（Python语言）

• 实现:

  • 归并：平均和最差情况的时间复杂度为 O(n log n)。
  • 快排：平均时间复杂度为 O(n log n)。
  • 选择排序和插入排序的最坏、平均时间复杂度都是 O(n^2)。
  • 关于堆排序，请查看前文堆的数据结构部分。

• 有兴趣的话，还有一些补充，但并不是必须的:

  • Sedgewick──基数排序 (6个视频)
    • 1. Java 中的字符串
    • 2. 键值索引计数（Key Indexed Counting）
    • 3. Least Significant Digit First String Radix Sort
    • 4. Most Significant Digit First String Radix Sort
    • 5. 3中基数快速排序
    • 6. 后继数组（Suffix Arrays）
  • 基数排序
  • 基数排序（视频）
  • 基数排序, 计数排序 (线性时间内)（视频）
  • 随机算法: 矩阵相乘, 快排, Freivalds' 算法（视频）
  • 线性时间内的排序（视频）

总结一下，这是15种排序算法的可视化表示。如果你需要有关此主题的更多详细信息，请参阅“一些主题的额外内容”中的“排序”部分。

图（Graphs）

图论能解决计算机科学里的很多问题，所以这一节会比较长，像树和排序的部分一样。

• 笔记:

  • 有4种基本方式在内存里表示一个图:
    • 对象和指针
    • 邻接矩阵
    • 邻接表
    • 邻接图
  • 熟悉以上每一种图的表示法，并了解各自的优缺点
  • 广度优先搜索和深度优先搜索：知道它们的计算复杂度和设计上的权衡以及如何用代码实现它们
  • 遇到一个问题时，首先尝试基于图的解决方案，如果没有再去尝试其他的。

• MIT（视频）：

  • 广度优先搜索
  • 深度优先搜索

• Skiena 教授的课程 - 很不错的介绍:

  • CSE373 2012 - 课程 11 - 图的数据结构（视频）
  • CSE373 2012 - 课程 12 - 广度优先搜索（视频）
  • CSE373 2012 - 课程 13 - 图的算法（视频）
  • CSE373 2012 - 课程 14 - 图的算法 (1)（视频）
  • CSE373 2012 - 课程 15 - 图的算法 (2)（视频）
  • CSE373 2012 - 课程 16 - 图的算法 (3)（视频）

• 图 (复习和其他):

  • 6.006 单源最短路径问题（视频）
  • 6.006 Dijkstra 算法（视频）
  • 6.006 Bellman-Ford 算法（视频）
  • 6.006 Dijkstra 效率优化（视频）
  • Aduni: 图的算法 I - 拓扑排序，最小生成树，Prim 算法 - 第六课（视频）
  • Aduni: 图的算法 II - 深度优先搜索, 广度优先搜索, Kruskal 算法, 并查集数据结构 - 第七课（视频）
  • Aduni: 图的算法 III: 最短路径 - 第八课（视频）
  • Aduni: 图的算法. IV: 几何算法介绍 - 第九课（视频）
  • CS 61B 2014 (从 58:09 开始)（视频）
  • CS 61B 2014: 加权图（视频）
  • 贪心算法: 最小生成树（视频）
  • 图的算法之强连通分量 Kosaraju 算法（视频）

• 完整的 Coursera 课程:

  • 图的算法（视频）

• 我会实现:

  • DFS 邻接表 (递归)
  • DFS 邻接表 (栈迭代)
  • DFS 邻接矩阵 (递归)
  • DFS 邻接矩阵 (栈迭代)
  • BFS 邻接表
  • BFS 邻接矩阵
  • 单源最短路径问题 (Dijkstra)
  • 最小生成树
  • 基于 DFS 的算法 (根据上文 Aduni 的视频):
    • 检查环 (我们会先检查是否有环存在以便做拓扑排序)
    • 拓扑排序
    • 计算图中的连通分支
    • 列出强连通分量
    • 检查双向图

可以从 Skiena 的书（参考下面的书推荐小节）和面试书籍中学习更多关于图的实践。

更多知识

• 递归（Recursion）

  • Stanford 大学关于递归 & 回溯的课程:
    • 课程 8 | 抽象编程（视频）
    • 课程 9 | 抽象编程（视频）
    • 课程 10 | 抽象编程（视频）
    • 课程 11 | 抽象编程（视频）
  • 什么时候适合使用
  • 尾递归会更好么?
    • 什么是尾递归以及为什么它如此糟糕?
    • 尾递归（视频）

• 动态规划（Dynamic Programming）

  • 在你的面试中或许没有任何动态规划的问题，但能够知道一个题目可以使用动态规划来解决是很重要的。
  • 这一部分会有点困难，每个可以用动态规划解决的问题都必须先定义出递推关系，要推导出来可能会有点棘手。
  • 我建议先阅读和学习足够多的动态规划的例子，以便对解决 DP 问题的一般模式有个扎实的理解。

  • 视频:

    • Skiena 的视频可能会有点难跟上，有时候他用白板写的字会比较小，难看清楚。
    • Skiena: CSE373 2012 - 课程 19 - 动态规划介绍（视频）
    • Skiena: CSE373 2012 - 课程 20 - 编辑距离（视频）
    • Skiena: CSE373 2012 - 课程 21 - 动态规划举例（视频）
    • Skiena: CSE373 2012 - 课程 22 - 动态规划应用（视频）
    • Simonson: 动态规划 0 (starts at 59:18)（视频）
    • Simonson: 动态规划 I - 课程 11（视频）
    • Simonson: 动态规划 II - 课程 12（视频）
    • 单独的 DP 问题 (每一个视频都很短)：动态规划（视频）

  • 耶鲁课程笔记:

    • 动态规划

  • Coursera 课程:

    • RNA 二级结构问题（视频）
    • 动态规划算法（视频）
    • DP 算法描述（视频）
    • DP 算法的运行时间（视频）
    • DP vs 递归实现（视频）
    • 全局成对序列排列（视频）
    • 本地成对序列排列（视频）

• 面向对象编程

  • 可选：UML 2.0系列（视频）
  • SOLID 面向对象编程原则：SOLID 原则（视频）

• 设计模式

  • UML 统一建模语言概览 (视频)
  • 主要有如下的设计模式:
    • 策略模式（strategy）
    • 单例模式（singleton）
    • 适配器模式（adapter）
    • 原型模式（prototype）
    • 装饰器模式（decorator）
    • 访问者模式（visitor）
    • 工厂模式，抽象工厂模式（factory, abstract factory）
    • 外观模式（facade）
    • 观察者模式（observer）
    • 代理模式（proxy）
    • 委托模式（delegate）
    • 命令模式（command）
    • 状态模式（state）
    • 备忘录模式（memento）
    • 迭代器模式（iterator）
    • 组合模式（composite）
    • 享元模式（flyweight）
  • 第六章 (第 1 部分 ) - 设计模式 (视频)
  • 第六章 (第 2 部分 ) - Abstraction-Occurrence, General Hierarchy, Player-Role, Singleton, Observer, Delegation (视频)
  • 第六章 (第 3 部分 ) - Adapter, Facade, Immutable, Read-Only Interface, Proxy（视频）
  • 系列视频（27个）
  • Head First 设计模型
    • 尽管《设计模式：可复用面向对象软件的基础》才是这方面的经典，但是我还是认为Head First对于新手更加友好。
  • 实际操作：设计模式和对入门开发者的建议
  • Design patterns for humans

• 组合（Combinatorics） (n 中选 k 个) & 概率（Probability）

  • 数据技巧: 如何找出阶乘、排列和组合(选择)（视频）
  • 来点学校的东西: 概率（视频）
  • 来点学校的东西: 概率和马尔可夫链（视频）
  • 可汗学院:
    • 课程设置:
      • 概率理论基础
    • 只有视频 - 41 (每一个都短小精悍):
      • 概率解释（视频）

• NP, NP-完全和近似算法

  • 知道最经典的一些 NP 完全问题，比如旅行商问题和背包问题，而且能在面试官试图忽悠你的时候识别出他们。
  • 知道 NP 完全是什么意思.
  • 计算复杂度（视频）
  • Simonson:
    • 贪心算法. II & 介绍 NP-完全性（视频）
    • NP-完全性 II & 归约（视频）
    • NP-完全性 III（视频）
    • NP-完全性 IV（视频）
  • Skiena:
    • CSE373 2012 - 课程 23 - 介绍 NP-完全性 IV（视频）
    • CSE373 2012 - 课程 24 - NP-完全性证明（视频）
    • CSE373 2012 - 课程 25 - NP-完全性挑战（视频）
  • 复杂度: P, NP, NP-完全性, 规约（视频）
  • 复杂度: 近视算法 Algorithms（视频）
  • 复杂度: 固定参数算法（视频）
  • Peter Norvik 讨论旅行商问题的近似最优解:
    • Jupyter 笔记本
  • 《算法导论》（CLRS）的第 1048 - 1140 页。

• 缓存（Cache）

  • LRU 缓存:
    • LRU 的魔力 (100 Days of Google Dev)（视频）
    • 实现 LRU（视频）
    • LeetCode - 146 LRU Cache (C++)（视频）
  • CPU 缓存:
    • MIT 6.004 L15: 存储体系（视频）
    • MIT 6.004 L16: 缓存的问题（视频）

• 进程（Processe）和线程（Thread）

  • 计算机科学 162 - 操作系统 (25 个视频):
    • 视频 1-11 是关于进程和线程
    • 操作系统和系统编程（视频）
  • 进程和线程的区别是什么?
  • 涵盖了:
    • 进程、线程、协程
      • 进程和线程的区别
      • 进程
      • 线程
      • 锁
      • 互斥
      • 信号量
      • 监控
      • 他们是如何工作的
      • 死锁
      • 活锁
    • CPU 活动, 中断, 上下文切换
    • 现代多核处理器的并发式结构
    • 分页（paging），分段（segmentation）和虚拟内存（视频）
    • 中断（视频）
    • 进程资源需要（内存：代码、静态存储器、栈、堆、文件描述符、I/O）
    • 线程资源需要（在同一个进程内和其他线程共享以上（除了栈）的资源，但是每个线程都有独立的程序计数器、栈计数器、寄存器和栈）
    • Fork 操作是真正的写时复制（只读），直到新的进程写到内存中，才会生成一份新的拷贝。
    • 上下文切换
      • 操作系统和底层硬件是如何初始化上下文切换的？
  • C++ 的线程 (系列 - 10 个视频)
  • Python 的并发 (视频):
    • 线程系列
    • Python 线程
    • 理解 Python 的 GIL (2010)
      • 参考
    • David Beazley - Python 协程 - PyCon 2015
    • Keynote David Beazley - 兴趣主题 (Python 异步 I/O)
    • Python 中的互斥

• 测试

  • 涵盖了:
    • 单元测试是如何工作的
    • 什么是模拟对象
    • 什么是集成测试
    • 什么是依赖注入
  • James Bach 讲敏捷软件测试（视频）
  • James Bach 软件测试公开课（视频）
  • Steve Freeman - 测试驱动的开发（视频）
    • slides
  • Python：测试驱动的 Web 开发
  • 依赖注入:
    • 视频
    • 测试之道
  • 如何编写测试

• 调度

  • 在操作系统中是如何运作的
  • 在操作系统部分的视频里有很多资料

• 字符串搜索和操作

  • Sedgewick──后缀数组（Suffix Arrays）（视频）
  • Sedgewick──子字符串搜寻（视频）
    • 1. 子字符串搜寻导论
    • 2. 子字符串搜寻──暴力法
    • 3. KMP算法
    • 4. Boyer-Moore算法
    • 5. Rabin-Karp算法
  • 文本的搜索模式（视频）

如果你需要有关此主题的更多详细信息，请参阅“一些主题的额外内容”中的“字符串匹配”部分。

• 字典树（Tries）

  • 需要注意的是，字典树各式各样。有些有前缀，而有些则没有。有些使用字符串而不使用比特位来追踪路径。
  • 阅读代码，但不实现。
  • Sedgewick──字典树（3个视频）
    • 1. R Way字典树
    • 2. 三元搜索树
    • 3. 基于字符串的操作
  • 数据结构笔记及编程技术
  • 短课程视频：
    • 对字典树的介绍（视频）
    • 字典树的性能（视频）
    • 实现一棵字典树（视频）
  • 字典树：一个被忽略的数据结构
  • TopCoder —— 使用字典树
  • 标准教程（现实中的用例）（视频）
  • MIT，高阶数据结构，字符串（视频中间有点困难）（视频）

• 浮点数

  • 简单8位：浮点数的表示形式-1（视频──计算中存在错误，请参见视频说明）
  • 32位：IEEE754 32位浮点二进制（视频）

• Unicode

  • 每一个软件开发者的绝对最低限度，必须要知道的关于 Unicode 和字符集知识
  • 关于处理文本需要的编码和字符集，每个程序员绝对需要知道的知识

• 字节序（Endianness）

  • 大/小端序
  • 大端序 Vs 小端序（视频）
  • 由里入内的大端序与小端序（视频）
    • 对于内核开发非常具有技术性，如果大多数的内容听不懂也没关系。
    • 前半部就已经足够了。

• 网络（视频）

  • 如果你具有网络经验或想成为可靠性工程师或运维工程师，期待你的问题
  • 知道这些有益无害，多多益善!
  • 可汗学院
  • UDP 和 TCP：网络传输协议中的数据压缩（视频）
  • TCP/IP 和 OSI 模型解释！（视频）
  • 互联网上的数据包传输。网络和 TCP/IP 教程。（视频）
  • HTTP（视频）
  • SSL 和 HTTPS（视频）
  • SSL/TLS（视频）
  • HTTP 2.0（视频）
  • 视频系列（21个视频）
  • 子网络解密 - 第五部分 经典内部域名指向 CIDR 标记（视频）
  • 套接字（Sockets）：
    • Java──套接字──介绍（视频）
    • 套接字编程（视频）

系统设计、可伸缩性、数据处理

如果你已经拥有了4年以上的编程经验，那你可以来看看有关系统设计的问题

• 系统设计以及可伸缩性，要把软硬件的伸缩性设计的足够好有很多的东西要考虑，所以这是个包含非常多内容和资源的大主题。要花费相当多的时间在这个主题上。
• 考量：
  • 伸缩性
    • 把大数据集提取为单一值
    • 大数据集转换
    • 处理大量的数据集
  • 系统
    • 功能集
    • 接口
    • 类层次结构
    • 在特定的约束下设计系统
    • 轻量和健壮性
    • 权衡和折衷
    • 性能分析和优化

• 从这里开始：系统设计入门

• HiredInTech：系统设计

• 该如何为技术面试里设计方面的问题做准备?

• 在系统设计面试前必须知道的 8 件事

• 算法设计

• 数据库范式 - 1NF, 2NF, 3NF and 4NF（视频）

• 系统设计面试 - 这一部分有很多的资源浏览一下我放在下面的文章和例子。

• 如何在系统设计面试中脱颖而出

• 每个人都该知道的一些数字

• 上下文切换操作会耗费多少时间?

• 跨数据中心的事务（视频）

• 简明 CAP 理论介绍

• 共识算法：

  • Paxos：Paxos协议──Computerphile（视频）
  • Raft: Raft 分布式共识算法简介（视频）
    • 易于阅读的论文
    • [信息图]

• 一致性哈希

• NoSQL 模式

• 可伸缩性:

  • 你不需要知道所有这些。只需挑选一些你感兴趣的东西即可。
  • 很棒的概述（视频）
  • 简短系列:
    • 克隆
    • 数据库
    • 缓存
    • 异步
  • 可伸缩的 Web 架构和分布式系统
  • 错误的分布式系统解释
  • 实用编程技术
    • extra: Google Pregel 图形处理
  • Jeff Dean - 在 Goolge 构建软件系统（视频）
  • 可伸缩系统架构设计介绍
  • 使用 App Engine 和云存储扩展面向全球用户的手机游戏架构实践（视频）
  • How Google Does Planet-Scale Engineering for Planet-Scale Infra（视频）
  • 算法的重要性
  • 分片（Sharding）
  • Facebook 系统规模扩展实践 (2012), "为 10 亿用户构建"（视频）
  • Long Game 工程实践 - Astrid Atkinson Keynote（视频）
  • 30 分钟看完 YouTuBe 7 年系统扩展经验
    • 视频
  • PayPal 如何用 8 台虚拟机扛住 10 亿日交易量系统
  • 如何对大数据集去重
  • Etsy 的扩展和工程文化探究 Jon Cowie（视频）
  • 是什么造就了 Amazon 自己的微服务架构
  • 压缩还是不压缩，是 Uber 面临的问题
  • 异步 I/O Tarantool 队列
  • 什么时候应该用近似查询处理?
  • Google 从单数据中心到故障转移, 到本地多宿主架构的演变
  • Spanner
  • Egnyte: 构建和扩展 PB 级分布式系统架构的经验教训
  • 机器学习驱动的编程: 新世界的新编程方式
  • 日服务数百万请求的图像优化技术
  • Patreon 架构
  • Tinder: 推荐引擎是如何决定下一个你将会看到谁的?
  • 现代缓存设计
  • Facebook 实时视频流扩展
  • 在 Amazon AWS 上把服务扩展到 1100 万量级的新手教程
  • 对延时敏感的应用是否应该使用 Docker?
  • 360 度解读 Netflix 技术栈
  • 延迟无处不在 - 如何搞定它？
  • 无服务器架构
  • 是什么驱动着 Instagram: 上百个实例、几十种技术
  • Cinchcast 架构 - 每天处理 1500 小时的音频
  • Justin.Tv 实时视频播放架构
  • Playfish's 社交游戏架构 - 每月五千万用户增长
  • 猫途鹰架构 - 40 万访客, 200 万动态页面访问, 30TB 数据
  • PlentyOfFish 架构
  • Salesforce 架构 - 如何扛住 13 亿日交易量
  • ESPN's 架构扩展
  • 下面“消息传递，序列化和队列系统”部分的内容会提到什么样的技术能把各种服务整合到一起
  • Twitter:
    • O'Reilly MySQL CE 2011: Jeremy Cole, "Big and Small Data at @Twitter"（视频）
    • 时间线的扩展
  • 更多内容可以查看视频系列部分的“大规模数据挖掘”视频系列。

• 系统设计问题练习：下面有一些指导原则，每一个都有相关文档以及在现实中该如何处理。

  • 复习: 系统设计入门
  • HiredInTech 的系统设计
  • 备忘单
  • 流程:
    1. 理解问题和范围:
       • 在面试官的帮助下定义用例
       • 提出附加功能的建议
       • 去掉面试官认定范围以外的内容
       • 假定高可用是必须的，而且要作为一个用例
    2. 考虑约束:
       • 问一下每月请求量
       • 问一下每秒请求量 (他们可能会主动提到或者让你算一下)
       • 评估读写所占的百分比
       • 评估的时候牢记 2/8 原则
       • 每秒写多少数据
       • 总的数据存储量要考虑超过 5 年的情况
       • 每秒读多少数据