编程面试大学

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

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

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

这是？

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

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

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

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

为何要用到它？

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

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

如何使用它

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

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

• 更多关于 Github-flavored Markdown 的详情

如果你不想使用 Git

在该页面上，单击顶部附近的 Code 按钮，然后单击“Download ZIP”。解压文件，就可以使用文本文件了。

如果你打开一个代码编辑器，你会看到所有格式都很好。

如果你不介意 Git

1. 通过单击 Fork 按钮来 fork GitHub 仓库：https://github.com/jwasham/coding-interview-university

   

2. 克隆项目到本地：

   git clone [email protected]:<your_github_username>/coding-interview-university.git
   cd coding-interview-university
   git checkout -b progress
   git remote add jwasham https://github.com/jwasham/coding-interview-university
   git fetch --all
   

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

   git add .
   git commit -m "Marked x"
   git rebase jwasham/main
   git push --set-upstream origin progress
   git push --force
   

不要觉得自己不够聪明

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

相关视频资源

部分视频只能通过在 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 年的情况
       • 每秒读多少数据
    3. 抽象设计:
       • 分层 (服务, 数据, 缓存)
       • 基础设施: 负载均衡, 消息
       • 粗略的概括任何驱动整个服务的关键算法
       • 考虑瓶颈并指出解决方案
  • 练习:
    • 设计一个 CDN 网络
    • 设计一个随机唯一 ID 生成系统
    • 设计一个在线多人卡牌游戏
    • 设计一个键值数据库
    • 设计一个图片分享系统
    • 设计一个推荐系统
    • 设计一个短域名生成系统
    • 设计一个缓存系统

终面

这一部分有一些短视频，你可以快速的观看和复习大多数重要概念。
这对经常性的巩固很有帮助。

• [ ] 2-3分钟的简短主题视频系列（23个视频）
  • 视频
• 2-5分钟的简短主题视频系列──Michael Sambol (38个视频）：
  • 视频
• Sedgewick 视频 ── 算法I
• Sedgewick 视频 ── 算法II

编程问题练习

现在你已经了解了上面所有的计算机科学主题，是时候练习回答编程问题了。

编程问题的实践并不是要记住编程问题的答案。

为什么需要练习编程问题：

• 快速识别问题，以及如何应用正确的数据结构及算法
• 收集问题的要求
• 像在面试中一样谈论问题
• 在白板或纸上而非计算机上编码
• 计算解决方案的时间和空间的复杂性
• 测试你的解决方案

这里有个很棒的入门教学，内容是如何在面试中有条不紊，并且有互动沟通地解决问题。这种能力可以从面试书籍中获得，但我觉得这个也很棒：算法设计画布。

家里没有白板？那讲得通。我是一个怪人，有一个很大的白板。从白板商店买了一个大的绘图板，而不是白板。你可以坐在沙发上练习。这是我的“沙发白板”。我在照片中添加了笔以便进行缩放。如果你使用笔，则希望可以擦除。快速变得凌乱。我用铅笔和橡皮擦。

补充：

• Topcoder的数学
• 动态编程──从新手到高级
• MIT 面试材料

阅读并练习编程问题（按此顺序）：

• 编程面试公开：下一份工作的秘密，第二版
  • C，C ++ 和 Java 的答案
• 破解编码面试，第六版
  • Java 答案

请参阅上方的书单。

编程练习和挑战

一旦你学会了理论基础，就应该把它们拿出来练练。
尽量坚持每天做编码练习，越多越好。

• 如何找到解决方案
• 如何剖析 Topcoder 题目描述

编码面试问题视频：

• IDeserve（88个视频）
• Tushar Roy（5个播放列表）
  • 超级解决问题的方法
• Nick White──LeetCode 解题（187个视频）
  • 良好的解决方案和代码解释
  • 你可以在短时间内看好几个
• FisherCoder──LeetCode 解题

编码练习平台:

• LeetCode
  • 我最喜欢的编码问题网站，值得你准备的1-2个月的订阅费用
  • FisherCoder 的 LeetCode 解题
  • 请参阅上面的 Nick White 视频，以获得简短的代码
• HackerRank
• TopCoder
• InterviewCake
• http://www.geeksforgeeks.org/
• InterviewBit
• Project Euler (数学方向为主)
• Code Exercises
• Scaler Topics

语言学习网站，附带编码挑战：

• Codewars
• Codility
• HackerEarth
• Sphere Online Judge (spoj)
• Codechef

编码挑战项目：

• Python 交互式编码面试挑战

模拟面试：

• Gainlo.co：来自大公司的模拟面试官──我使用了它，它帮助我减轻了电话屏幕和现场面试的压力
• Pramp：模拟来自/与同行的面试──点对点方式练习面试
• Refdash：模拟面试和加急面试──跳过与科技公司的多次面试，帮助求职者快速追踪
• interviewing.io：与高级工程师进行模拟面试──与来自 FAANG（译者注：Facebook, Amazon, Apple, Netflix and Google） 的高级工程师进行匿名算法/系统设计面试。

当你临近面试时

• 搞定代码面试──第二集 (视频):
  • Cracking The Code Interview
  • Cracking the Coding Interview - 全栈系列

你的简历

• 请参阅“破解编码面试”和“编程面试的背面”中的建立准备项。

当面试来临的时候

随着下面列举的问题思考下你可能会遇到的 20 个面试问题，每个问题准备 2-3 种回答。准备点故事，不要只是摆一些你完成的事情的数据，相信我，人人都喜欢听故事。

• 你为什么想得到这份工作？
• 你解决过的最有难度的问题是什么？
• 面对过的最大挑战是什么?
• 见过的最好或者最坏的设计是怎么样的?
• 对某个产品提出改进建议。
• 你作为一个个体同时也是团队的一员，如何达到最好的工作状态?
• 你的什么技能或者经验是你的角色中不可或缺的，为什么？
• 你在某份工作或某个项目中最享受的是什么?
• 你在某份工作或某个项目中面临过的最大挑战是什么?
• 你在某份工作或某个项目中遇到过的最硬的 Bug 是什么样的？
• 你在某份工作或某个项目中学到了什么？
• 你在某份工作或某个项目中哪些地方还可以做的更好？

问面试官的问题

我会问的一些：(可能我已经知道了答案但我想听听面试官的看法或者了解团队的前景):

• 团队多大规模?
• 开发周期是怎样的? 会使用瀑布流/极限编程/敏捷开发么?
• 经常会为截止日期（deadlines）加班么? 或者是有弹性的?
• 团队里怎么做技术选型?
• 每周平均开多少次会?
• 你觉得工作环境有助于员工集中精力吗?
• 目前正在做什么工作?
• 喜欢这些事情吗?
• 工作期限是怎么样的?
• 工作生活怎么平衡?

当你获得了梦想的职位

恭喜你！

继续学习。

活到老，学到老。

*****************************************************************************************************
*****************************************************************************************************

下面的内容都是可选的。
通过学习这些内容，你将会得到更多的有关 CS 的概念，并将为所有的软件工程工作做更好的准备。你将会成为一个更全面的软件工程师。

*****************************************************************************************************
*****************************************************************************************************

额外书籍

你可以从以下的书单挑选你有兴趣的主题来研读。

• UNIX环境高级编程

  • 老，但却很棒

• Linux 命令行大全

  • 现代选择

• TCP-IP详解系列

• Head First 设计模式

  • 设计模式入门介绍

• 设计模式：可复用面向对象软件的基础

  • 也被称为“四人帮”（Gang of Four(GOF)）
  • 经典设计模式书籍

• Linux 和 UNIX 系统管理技术手册（第五版）

• 算法设计手冊（Skiena）

  • 作为复习以及问题辨别
  • 这本书中算法的部分难度已经超过面试会出现的
  • 本书分为两个部分:
    • 数据结构和算法课本
      • 优点:
        • 跟其他算法课本一样是个很棒的复习素材
        • 包含作者以往解决工业及学术上问题的经验的故事
        • 含C语言代码示例
      • 缺点:
        • 某些地方跟《算法导论》（CLRS）一样艰深，但在某些主题，算法导论或许是更好的选择。
        • 第7、8、9章有点难以消化，因为某些地方并没有解释得很清楚，或者根本上我就是个学渣
        • 别会错意了，我很喜欢 Skiena 的教学方法以及他的风格。
    • 算法目录:
      • 这个部分是买这本书的最大原因
      • 我即将着手进行这部分，一旦完成这部分我会再更新上来
  • 可以在 kindle 上租
  • 解答：
    • 解答
    • 解答
  • 勘误表

• 编程卓越之道（第一卷）：深入理解计算机

  • 该书于2004年出版，虽然有些过时，但是对于简单了解计算机而言，这是一个了不起的资源
  • 作者发明了高阶组合语言 HLA，所以提到，并且举了一些HLA的例子。里面没有用到很多，但都是很棒的组合语言的例子。
  • 这些章节值得阅读，为你提供良好的基础：
    • 第2章──数字表示
    • 第3章──二进制算术和位运算
    • 第4章──浮点表示
    • 第5章──字符表示
    • 第6章──内存组织和访问
    • 第7章──组合数据类型和内存对象
    • 第9章──CPU体系结构
    • 第10章──指令集架构
    • 第11章──内存体系结构和组织

• 算法导论

  • 重要提示：读这本书的价值有限。本书很好地回顾了算法和数据结构，但不会教你如何编写良好的代码。你必须能够有效地编写一个不错的解决方案
  • 又称 CLR，有时是 CLRS，因为 Stein 最后才加入

• 计算机体系结构：量化研究方法（第6版）

  • 更丰富、更新（2017年），但篇幅较长

• 编程珠矶

  • 前几章介绍了解决编程问题（非常古老，甚至还用数据磁带）的巧妙解决方案，但这只是一个介绍。这是关于程序设计和体系结构的指南

附加学习

我把它们加进来是为了让你成为更全方位的软件工程师，并且留意一些技术以及算法，让你拥有更大的工具箱。

• 编译器

  • 编译器的工作方式，约1分钟（视频）
  • Harvard CS50-编译器（视频）
  • C ++（视频）
  • 了解编译器优化（C ++）（视频）

• Emacs and vi(m)

  • 熟悉基于 unix 的代码编辑器
  • vi(m):
    • 使用 vim 进行编辑 01 - 安装, 设置和模式 (视频)
    • VIM 的冒险之旅
    • 4 个视频集:
      • vi/vim 编辑器 - 课程 1
      • vi/vim 编辑器 - 课程 2
      • vi/vim 编辑器 - 课程 4
      • vi/vim 编辑器 - 课程 3
    • 使用 Vi 而不是 Emacs
  • emacs:
    • 基础 Emacs 教程 (视频)
    • 3 个视频集:
      • Emacs 教程 (初学者) -第 1 部分- 文件命令, 剪切/复制/粘贴, 自定义命令
      • Emacs 教程 (初学者 -第 2 部分- Buffer 管理, 搜索, M-x grep 和 rgrep 模式
      • Emacs 教程 (初学者 -第 3 部分- 表达式, 声明, ~/.emacs 文件和包机制
    • Evil 模式: 或许, 我是怎样对 Emacs 路人转粉的 (视频)
    • 使用 Emacs 开发 C 程序
    • (或许) 深度组织模式:管理结构 (视频)

• Unix 命令行工具

  • 下列内容包含优秀工具
  • bash
  • cat
  • grep
  • sed
  • awk
  • curl or wget
  • sort
  • tr
  • uniq
  • strace
  • tcpdump

• 信息论 (视频)

  • Khan Academy 可汗学院
  • 更多有关马尔可夫的内容:
    • 马尔可夫内容生成（Core Markov Text Generation）
    • Core Implementing Markov Text Generation马尔可夫内容生成实现
    • 一个马尔可夫内容生成器的项目（Project = Markov Text Generation Walk Through）
  • 关于更多信息，请参照下方 MIT 6.050J 信息和系统复杂度的内容。

• 奇偶校验位 & 汉明码 (视频)

  • 入门
  • 奇偶校验位
  • 汉明码(Hamming Code):
    • 发现错误
    • 修正错误
  • 检查错误

• 系统熵值（Entropy）

  • 请参考下方视频
  • 观看之前，请先确定观看了信息论的视频
  • 信息理论, 克劳德·香农, 熵值, 系统冗余, 数据比特压缩 (视频)

• 密码学

  • 请参考下方视频
  • 观看之前，请先确定观看了信息论的视频
  • 可汗学院
  • 密码学: 哈希函数
  • 密码学: 加密

• 压缩

  • 观看之前，请先确定观看了信息论的视频
  • Computerphile (视频)：
    • 压缩
    • 压缩熵值
    • 由上而下的树 (霍夫曼编码树)
    • 额外比特 - 霍夫曼编码树
    • 优雅的压缩数据 (无损数据压缩方法)
    • Text Compression Meets Probabilities
  • 数据压缩的艺术
  • (可选) 谷歌开发者：GZIP 还差远了呢!

• 计算机安全

  • MIT（23个视频）
    • 威胁模型：入门
    • 控制劫持攻击
    • 缓冲区溢出漏洞攻击和防御
    • 优先权区分
    • 能力
    • 在沙盒中运行原生代码
    • 网络安全模型
    • 网络安全应用
    • 标志化执行
    • 网络安全
    • 网络协议
    • 旁路攻击

• 垃圾回收

  • Python 中的垃圾回收 (视频)
  • 深度解析：论垃圾回收在 JAVA 中的重要性
  • 深度解析：论垃圾回收在 Python 中的重要性(视频)

• 并行编程

  • Coursera (Scala)
  • 用于高性能并行计算的高效Python（视频）

• 消息传递，序列化和队列系统

  • Thrift
    • 教程
  • 协议缓冲
    • 教程
  • gRPC
    • gRPC 对于JAVA开发者的入门教程（视频）
  • Redis
    • 教程
  • Amazon的 SQS 系统 (队列)
  • Amazon的 SNS 系统 (pub-sub)
  • RabbitMQ
    • 入门教程
  • Celery
    • Celery入门
  • ZeroMQ
    • 入门教程
  • ActiveMQ
  • Kafka
  • MessagePack
  • Avro

• A*搜索算法

  • A 搜索算法
  • A* 路径搜索教程（教程）
  • A* 路径搜索（E01：算法解释）（视频）

• 快速傅里叶变换

  • 傅立叶变换的交互式指南
  • 什么是傅立叶变换？论傅立叶变换的用途
  • 什么是傅立叶变换？ (视频)
  • 分而治之：FFT（视频）
  • FTT 是什么

• 布隆过滤器

  • 给定布隆过滤器m比特位和k个哈希函数，插入和成员检测都会是 O(k)。
  • 布隆过滤器（视频）
  • 布隆过滤器 | 数据挖掘 | Stanford University（视频）
  • 教程
  • 如何写一个布隆过滤器应用

• HyperLogLog

  • 如何仅使用1.5KB内存计算十亿个不同的对象

• 局部敏感哈希

  • 用于确定文件的相似性
  • MD5 或 SHA 的反义词，用于确定2个文档/字符串是否完全相同
  • Simhashing（希望如此）变得简单

• van Emde Boas 树

  • 分而治之：van Emde Boas 树 (视频)
  • MIT课堂笔记

• 增强数据结构

  • CS 61B 第 39 课: 增强数据结构

• 平衡查找树（Balanced search trees）

  • 掌握至少一种平衡查找树（并懂得如何实现）：

  • “在各种平衡查找树当中，AVL 树和2-3树已经成为了过去，而红黑树（red-black trees）看似变得越来越受人青睐。这种令人特别感兴趣的数据结构，亦称伸展树（splay tree）。它可以自我管理，且会使用轮换来移除任何访问过根节点的键。” —— Skiena

  • 因此，在各种各样的平衡查找树当中，我选择了伸展树来实现。虽然，通过我的阅读，我发现在面试中并不会被要求实现一棵平衡查找树。但是，为了胜人一筹，我们还是应该看看如何去实现。在阅读了大量关于红黑树的代码后，我才发现伸展树的实现确实会使得各方面更为高效。

    • 伸展树：插入、查找、删除函数的实现，而如果你最终实现了红黑树，那么请尝试一下：
    • 跳过删除函数，直接实现搜索和插入功能

  • 我希望能阅读到更多关于 B 树的资料，因为它也被广泛地应用到大型的数据集当中。

  • 自平衡二叉查找树

  • AVL 树

    • 实际中：我能告诉你的是，该种树并无太多的用途，但我能看到有用的地方在哪里：AVL 树是另一种平衡查找树结构。其可支持时间复杂度为 O(log n) 的查询、插入及删除。它比红黑树严格意义上更为平衡，从而导致插入和删除更慢，但遍历却更快。正因如此，才彰显其结构的魅力。只需要构建一次，就可以在不重新构造的情况下读取，适合于实现诸如语言字典（或程序字典，如一个汇编程序或解释程序的操作码）。
    • MIT AVL 树 / AVL 树的排序（视频）
    • AVL 树（视频）
    • AVL 树的实现（视频）
    • 分离与合并

  • 伸展树

    • 实际中：伸展树一般用于缓存、内存分配者、路由器、垃圾回收者、数据压缩、ropes（字符串的一种替代品，用于存储长串的文本字符）、Windows NT（虚拟内存、网络及文件系统）等的实现。
    • CS 61B：伸展树（Splay trees）（视频）
    • MIT 教程：伸展树（Splay trees）：
      • 该教程会过于学术，但请观看到最后的10分钟以确保掌握。
      • 视频

  • 红黑树

    • 这些是2-3棵树的翻译（请参见下文）。
    • 实际中：红黑树提供了在最坏情况下插入操作、删除操作和查找操作的时间保证。这些时间值的保障不仅对时间敏感型应用有用，例如实时应用，还对在其他数据结构中块的构建非常有用，而这些数据结构都提供了最坏情况下的保障；例如，许多用于计算几何学的数据结构都可以基于红黑树，而目前 Linux 内核所采用的完全公平调度器（the Completely Fair Scheduler）也使用到了该种树。在 Java 8中，Collection HashMap也从原本用Linked List实现，储存特定元素的哈希码，改为用红黑树实现。
    • Aduni —— 算法 —— 课程4（该链接直接跳到开始部分）（视频）
    • Aduni —— 算法 —— 课程5（视频）
    • 黑树（Black Tree）
    • 二分查找及红黑树的介绍

  • 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树（视频）

  • N 叉树（K 叉树、M 叉树）

    • 注意：N 或 K 指的是分支系数（即树的最大分支数）：
    • 二叉树是一种分支系数为2的树
    • 2-3树是一种分支系数为3的树
    • K 叉树

  • B 树

    • 有趣的是：为啥叫 B 仍然是一个神秘。因为 B 可代表波音（Boeing）、平衡（Balanced）或 Bayer（联合创造者）
    • 实际中：B 树会被广泛适用于数据库中，而现代大多数的文件系统都会使用到这种树（或变种)。除了运用在数据库中，B 树也会被用于文件系统以快速访问一个文件的任意块。但存在着一个基本的问题，那就是如何将文件块 i 转换成一个硬盘块（或一个柱面-磁头-扇区）上的地址。
    • B 树
    • B 树数据结构
    • B 树的介绍（视频）
    • B 树的定义及其插入操作（视频）
    • B 树的删除操作（视频）
    • MIT 6.851 —— 内存层次模块（Memory Hierarchy Models）（视频）
      • 覆盖有高速缓存参数无关型（cache-oblivious）B 树和非常有趣的数据结构
      • 头37分钟讲述的很专业，或许可以跳过（B 指块的大小、即缓存行的大小）

• k-D树

  • 非常适合在矩形或更高维度的对象中查找点数
  • 最适合k近邻
  • Kd树（视频）
  • kNN K-d树算法（视频）

• 跳表

  • "有一种非常迷幻的数据类型" - Skiena
  • 随机化: 跳表 (视频)
  • 更生动详细的解释

• 网络流

  • 5分钟简析 Ford-Fulkerson──一步步示例 (视频)
  • Ford-Fulkerson 算法 (视频)
  • 网络流 (视频)

• 不相交集 & 联合查找

  • UCB 61B - 不相交集；排序 & 选择(视频)
  • Sedgewick算法──Union-Find（6视频）

• 快速处理的数学

  • 整数运算, Karatsuba 乘法 (视频)
  • 中国剩余定理 (在密码学中的使用) (视频)

• 树堆 (Treap)

  • 一个二叉搜索树和一个堆的组合
  • 树堆
  • 数据结构：树堆的讲解（视频）
  • 集合操作的应用(Applications in set operations)

• 线性规划（Linear Programming）（视频）

  • 线性规划
  • 寻找最小成本
  • 寻找最大值
  • 用 Python 解决线性方程式──单纯形算法

• 几何：凸包（Geometry, Convex hull）（视频）

  • Graph Alg. IV: 几何算法介绍 - 第 9 课
  • Graham & Jarvis: 几何算法 - 第 10 课
  • 分而治之: 凸包, 中值查找

• 离散数学

  • 查看下面的视频

• 机器学习（Machine Learning）

  • 为什么学习机器学习？
    • 谷歌如何将自己改造成一家「机器学习优先」公司？
    • 智能计算机系统的大规模深度学习 (视频)
    • Peter Norvig：深度学习和理解与软件工程和验证的对比
  • 谷歌云机器学习工具（视频）
  • 谷歌开发者机器学习清单 (Scikit Learn 和 Tensorflow) (视频)
  • Tensorflow (视频)
  • Tensorflow 教程
  • Python 实现神经网络实例教程（使用 Theano）
  • 课程:
    • 很棒的初级课程：机器学习
      • 视频教程
      • 看第 12-18 集复习线性代数（第 14 集和第 15 集是重复的）
    • 机器学习中的神经网络
    • Google 深度学习微学位
    • Google/Kaggle 机器学习工程师微学位
    • 无人驾驶工程师微学位
  • 资源:
    • 书籍：
      • Python 机器学习
      • Data Science from Scratch: First Principles with Python
      • Python 机器学习简介
    • 软件工程师的机器学习
    • Data School：http://www.dataschool.io/

--

一些主题的额外内容

我为前面提到的某些主题增加了一些额外的内容，之所以没有直接添加到前面，是因为这样很容易导致某个主题内容过多。毕竟你想在本世纪找到一份工作，对吧？

• SOLID

  • Bob Martin SOLID面向对象和敏捷设计的原理（视频）
  • S ── 单一责任原则 | 对每个对象的单一责任
    • 更多
  • O ── 开放/封闭原则 | 在生产级别上，可以扩展对象，但不能修改对象
    • 更多
  • L ── Liskov 替换原则 | 基本类别和派生类别遵循“IS A”原则
    • 更多
  • I ── 接口隔离原理 | 不应强迫客户端实现不使用的接口
    • 5分钟了解接口隔离原理（视频）
    • 更多
  • D ── 依赖倒置原理 | 减少对象组合中的依赖性。
    • 依赖倒置原理为何如此重要？
    • 更多

• Union-Find

  • 概览
  • 初级实践
  • 树状结构
  • 合并树状结构
  • 路径压缩
  • 分析选项

• 动态规划的更多内容 (视频)

  • 6.006: 动态规划 I: 斐波那契数列, 最短路径
  • 6.006: 动态规划 II: 文本匹配, 二十一点/黑杰克
  • 6.006: 动态规划 III: 最优加括号方式, 最小编辑距离, 背包问题
  • 6.006: 动态规划 IV: 吉他指法，拓扑，超级马里奥.
  • 6.046: 动态规划: 动态规划进阶
  • 6.046: 动态规划: 所有点对最短路径
  • 6.046: 动态规划: 更多示例

• 图形处理进阶 (视频)

  • 异步分布式算法: 对称性破缺，最小生成树
  • 异步分布式算法: 最小生成树

• MIT 概率论 (过于数学，进度缓慢，但这对于数学的东西却是必要之恶) (视频):

  • MIT 6.042J - 概率论概述
  • MIT 6.042J - 条件概率 Probability
  • MIT 6.042J - 独立
  • MIT 6.042J - 随机变量
  • MIT 6.042J - 期望 I
  • MIT 6.042J - 期望 II
  • MIT 6.042J - 大偏差
  • MIT 6.042J - 随机游走

• Simonson: 近似算法 (视频)

• 字符串匹配

  • Rabin-Karp（视频）
    • Rabin Karps 算法
    • 预计算
    • 优化：实施和分析
    • 表翻倍，Karp-Rabin
    • 滚动哈希，摊销分析
  • Knuth-Morris-Pratt (KMP)：
    • Knuth-Morris-Pratt（KMP）字符串匹配算法
  • Boyer–Moore 字符串搜索算法
    • Boyer–Moore 字符串搜索算法
    • 高级字符串搜索Boyer-Moore-Horspool算法（视频）
  • Coursera：字符串算法
    • 刚开始时很棒，但是当它超过 KMP 时，它变得比需要复杂得多
    • 很好的字典树解释
    • 可以跳过

• 排序

  • 斯坦福大学关于排序算法的视频:

    • 课程 15 | 编程抽象（视频）
    • 课程 16 | 编程抽象（视频）

  • Shai Simonson 视频，Aduni.org:

    • 算法 - 排序 - 第二讲（视频）
    • 算法 - 排序2 - 第三讲（视频）

  • Steven Skiena 关于排序的视频:

    • 课程从 26:46 开始（视频）
    • 课程从 27:40 开始（视频）
    • 课程从 35:00 开始（视频）
    • 课程从 23:50 开始（视频）

视频系列

坐下来享受一下吧。"netflix 和技能" :P

• 个人的动态规划问题列表 (都是短视频)

• x86 架构，汇编，应用程序 (11 个视频)

• MIT 18.06 线性代数，2005 年春季 (35 个视频)

• 绝妙的 MIT 微积分：单变量微积分

• 计算机科学 70, 001 - 2015 年春季 - 离散数学和概率理论

• 离散数学 (19 个视频)

• 离散数学（第一部分），Sarada Herke （5个视频）

• CSE373 - 算法分析 (25 个视频)

  • Skiena 的算法设计手册讲座

• UC Berkeley 61B (2014 年春季): 数据结构 (25 个视频)

• UC Berkeley 61B (2006 年秋季): 数据结构 (39 个视频)

• UC Berkeley 61C：计算机结构 (26 个视频)

• OOSE：使用 UML 和 Java 进行软件开发 (21 个视频)

• UC Berkeley CS 152: 计算机结构和工程 (20 个视频)

• MIT 6.004: 计算结构 (49 视频)

• 卡內基梅隆大学 - 计算机架构讲座 (39 个视频)

• MIT 6.006：算法介绍 (47 个视频)

• MIT 6.033：计算机系统工程 (22 个视频)

• MIT 6.034：人工智能，2010 年秋季 (30 个视频)

• MIT 6.042J：计算机科学数学, 2010 年秋季 (25 个视频)

• MIT 6.046：算法设计与分析 (34 个视频)

• MIT 6.050J：信息和熵, 2008 年春季 (19 个视频)

• MIT 6.851：高等数据结构 (22 个视频)

• MIT 6.854: 高等算法, 2016 年春季 (24 个视频)

• Harvard COMPSCI 224：高级算法（25个视频）

• MIT 6.858：计算机系统安全, 2014 年秋季

• 斯坦福: 编程范例 (27 个视频)

• 密码学导论，Christof Paar

  • 课程网站以及幻灯片和问题集

• 大数据 - 斯坦福大学 (94 个视频)

• 图论，Sarada Herke（67个视频）

计算机科学课程

• 在线 CS 课程目录
• CS 课程目录 (一些是在线讲座)

论文

• 喜欢经典的论文？
• 1978: 通信顺序处理
  • Go 实现
• 2003: The Google 文件系统
  • 2012 年被 Colossus 取代了
• 2004: MapReduce: Simplified Data Processing on Large Clusters
  • 大多被云数据流取代了?
• 2006年：Bigtable：结构化数据的分布式存储系统
  • 深入了解Google BigQuery
• 2006年：针对松散耦合的分布式系统的Chubby Lock服务
• 2007年：Dynamo：亚马逊的高可用键值存储
  • Dynamo论文启动了NoSQL革命
• 2007: 每个程序员都应该知道的内存知识 (非常长，作者建议跳过某些章节来阅读)
• 2010年：Dapper，一个大型分布式系统跟踪基础结构
• 2010年：Dremel：Web规模数据集的交互式分析
• 2012: Google 的 Colossus
  • 没有论文
• 2012: AddressSanitizer: 快速的内存访问检查器:
  • 论文
  • 视频
• 2013: Spanner: Google 的分布式数据库:
  • 论文
  • 视频
• 2014: Machine Learning: The High-Interest Credit Card of Technical Debt
• 2015: Continuous Pipelines at Google
• 2015: 大规模高可用: 构建 Google Ads 的数据基础设施
• 2015: TensorFlow: 异构分布式系统上的大规模机器学习
• 2015: 开发者应该如何搜索代码：用例学习
• 2016: Borg, Omega, and Kubernetes

LICENSE

CC-BY-SA-4.0