coding-interview-university

Google Interview University - 一套完整的学习手册帮助自己准备 Google 的面试

这是？

这是我为了从 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 叉树）
• Sorting
• Graphs
• Even More Knowledge
  • Recursion
  • Dynamic Programming
  • Combinatorics (n choose k) & Probability
  • NP, NP-Complete and Approximation Algorithms
  • Caches
  • Processes and Threads
  • System Design, Scalability, Data Handling
  • Papers
  • Testing
  • Scheduling
  • Implement system routines
  • String searching & manipulations
• Final Review
• Books
• Coding exercises/challenges
• Once you're closer to the interview
• Your Resume
• Be thinking of for when the interview comes
• Have questions for the interviewer
• Once You've Got The Job

---------------- Everything below this point is optional ----------------

• Additional Learning
  • Unicode
  • Endianness
  • Emacs and vi(m)
  • Unix command line tools
  • Information theory
  • Parity & Hamming Code
  • Entropy
  • Cryptography
  • Compression
  • Networking
  • Computer Security
  • Garbage collection
  • Parallel Programming
  • Design patterns
  • Messaging, Serialization, and Queueing Systems
  • Fast Fourier Transform
  • Bloom Filter
  • van Emde Boas Trees
  • Augmented Data Structures
  • Skip lists
  • Network Flows
  • Disjoint Sets & Union Find
  • Math for Fast Processing
  • Treap
  • Linear Programming
  • Geometry, Convex hull
  • Discrete math
  • Machine Learning
  • Go
• Additional Detail on Some Subjects
• 视频系列
• 计算机科学课程

---

为何要用到它？

我一直都是遵循该计划去准备 Google 的面试。自 1997 年以来，我一直从事于 web 程序的构建、服务器的构建及创业型公司的创办。对于只有着一个经济学学位，而不是计算机科学学位（CS degree）的我来说，在职业生涯中所取得的都非常成功。然而，我想在 Google 工作，并进入大型系统中，真正地去理解计算机系统、算法效率、数据结构性能、低级别编程语言及其工作原理。可一项都不了解的我，怎么会被 Google 所应聘呢？

当我创建该项目时，我从一个堆栈到一个堆都不了解。那时的我，完全不了解 Big-O 、树，或如何去遍历一个图。如果非要我去编写一个排序算法的话，我只能说我所写的肯定是很糟糕。一直以来，我所用的任何数据结构都是内建于编程语言当中。至于它们在背后是如何运作，对此我一概不清楚。此外，以前的我并不需要对内存进行管理，最多就只是在一个正在执行的进程抛出了“内存不足”的错误后，采取一些权变措施。而在我的编程生活中，也甚少使用到多维数组，可关联数组却成千上万。而且，从一开始到现在，我都还未曾自己实现过数据结构。

就是这样的我，在经过该学习计划后，已然对被 Google 所雇佣充满信心。这是一个漫长的计划，以至于花费了我数月的时间。若您早已熟悉大部分的知识，那么也许能节省大量的时间。

如何使用它

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

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

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

更多关于 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月（视频）

相关视频资源

部分视频只能通过在 Coursera、Edx 或 Lynda.com class 上注册登录才能观看。这些视频被称为网络公开课程（MOOC）。即便是免费观看，部分课程可能会由于不在时间段内而无法获取。因此，你需要多等待几个月。

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

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

• [ ] 视频：

  • 如何在 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)

更多的知识

• 二分查找（Binary search）

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

• 按位运算（Bitwise operations）

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

树（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

• [ ] Notes:

  • Implement sorts & know best case/worst case, average complexity of each:
    • no bubble sort - it's terrible - O(n^2), except when n <= 16
  • stability in sorting algorithms ("Is Quicksort stable?")
    • Sorting Algorithm Stability
    • Stability In Sorting Algorithms
    • Stability In Sorting Algorithms
    • Sorting Algorithms - Stability
  • Which algorithms can be used on linked lists? Which on arrays? Which on both?
    • I wouldn't recommend sorting a linked list, but merge sort is doable.
    • Merge Sort For Linked List

• For heapsort, see Heap data structure above. Heap sort is great, but not stable.

• [ ] Bubble Sort (video)

• [ ] Analyzing Bubble Sort (video)

• [ ] Insertion Sort, Merge Sort (video)

• [ ] Insertion Sort (video)

• [ ] Merge Sort (video)

• [ ] Quicksort (video)

• [ ] Selection Sort (video)

• [ ] Stanford lectures on sorting:

  • Lecture 15 | Programming Abstractions (video)
  • Lecture 16 | Programming Abstractions (video)

• [ ] Shai Simonson, Aduni.org:

  • Algorithms - Sorting - Lecture 2 (video)
  • Algorithms - Sorting II - Lecture 3 (video)

• [ ] Steven Skiena lectures on sorting:

  • lecture begins at 26:46 (video)
  • lecture begins at 27:40 (video)
  • lecture begins at 35:00 (video)
  • lecture begins at 23:50 (video)

• [ ] UC Berkeley:

  • CS 61B Lecture 29: Sorting I (video)
  • CS 61B Lecture 30: Sorting II (video)
  • CS 61B Lecture 32: Sorting III (video)
  • CS 61B Lecture 33: Sorting V (video)

• [ ] - Merge sort code:

  • Using output array
  • In-place

• [ ] - Quick sort code:

  • Implementation
  • Implementation

• [ ] Implement:

  • Mergesort: O(n log n) average and worst case
  • Quicksort O(n log n) average case
  • Selection sort and insertion sort are both O(n^2) average and worst case
  • For heapsort, see Heap data structure above.

• [ ] For curiosity - not required:

  • Radix Sort
  • Radix Sort (video)
  • Radix Sort, Counting Sort (linear time given constraints) (video)
  • Randomization: Matrix Multiply, Quicksort, Freivalds' algorithm (video)
  • Sorting in Linear Time (video)

Graphs

Graphs can be used to represent many problems in computer science, so this section is long, like trees and sorting were.

• Notes from Yegge:

  • There are three basic ways to represent a graph in memory:
    • objects and pointers
    • matrix
    • adjacency list
  • Familiarize yourself with each representation and its pros & cons
  • BFS and DFS - know their computational complexity, their tradeoffs, and how to implement them in real code
  • When asked a question, look for a graph-based solution first, then move on if none.

• [ ] Skiena Lectures - great intro:

  • CSE373 2012 - Lecture 11 - Graph Data Structures (video)
  • CSE373 2012 - Lecture 12 - Breadth-First Search (video)
  • CSE373 2012 - Lecture 13 - Graph Algorithms (video)
  • CSE373 2012 - Lecture 14 - Graph Algorithms (con't) (video)
  • CSE373 2012 - Lecture 15 - Graph Algorithms (con't 2) (video)
  • CSE373 2012 - Lecture 16 - Graph Algorithms (con't 3) (video)

• [ ] Graphs (review and more):

  • 6.006 Single-Source Shortest Paths Problem (video)
  • 6.006 Dijkstra (video)
  • 6.006 Bellman-Ford (video)
  • 6.006 Speeding Up Dijkstra (video)
  • Aduni: Graph Algorithms I - Topological Sorting, Minimum Spanning Trees, Prim's Algorithm - Lecture 6 (video)
  • Aduni: Graph Algorithms II - DFS, BFS, Kruskal's Algorithm, Union Find Data Structure - Lecture 7 (video)
  • Aduni: Graph Algorithms III: Shortest Path - Lecture 8 (video)
  • Aduni: Graph Alg. IV: Intro to geometric algorithms - Lecture 9 (video)
  • CS 61B 2014 (starting at 58:09) (video)
  • CS 61B 2014: Weighted graphs (video)
  • Greedy Algorithms: Minimum Spanning Tree (video)
  • Strongly Connected Components Kosaraju's Algorithm Graph Algorithm (video)

• Full Coursera Course:

  • Algorithms on Graphs (video)

• Yegge: If you get a chance, try to study up on fancier algorithms:

  • Dijkstra's algorithm - see above - 6.006
  • A*
    • A Search Algorithm
    • A* Pathfinding Tutorial (video)
    • A* Pathfinding (E01: algorithm explanation) (video)

• I'll implement:

  • DFS with adjacency list (recursive)
  • DFS with adjacency list (iterative with stack)
  • DFS with adjacency matrix (recursive)
  • DFS with adjacency matrix (iterative with stack)
  • BFS with adjacency list
  • BFS with adjacency matrix
  • single-source shortest path (Dijkstra)
  • minimum spanning tree
  • DFS-based algorithms (see Aduni videos above):
    • check for cycle (needed for topological sort, since we'll check for cycle before starting)
    • topological sort
    • count connected components in a graph
    • list strongly connected components
    • check for bipartite graph

You'll get more graph practice in Skiena's book (see Books section below) and the interview books

Even More Knowledge

• Recursion

  • Stanford lectures on recursion & backtracking:
    • Lecture 8 | Programming Abstractions (video)
    • Lecture 9 | Programming Abstractions (video)
    • Lecture 10 | Programming Abstractions (video)
    • Lecture 11 | Programming Abstractions (video)
  • when it is appropriate to use it
  • how is tail recursion better than not?
    • What Is Tail Recursion Why Is It So Bad?
    • Tail Recursion (video)

• 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.
  • I suggest looking at many examples of DP problems until you have a solid understanding of the pattern involved.
  • Videos:
    • the Skiena videos can be hard to follow since he sometimes uses the whiteboard, which is too small to see
    • Skiena: CSE373 2012 - Lecture 19 - Introduction to Dynamic Programming (video)
    • Skiena: CSE373 2012 - Lecture 20 - Edit Distance (video)
    • Skiena: CSE373 2012 - Lecture 21 - Dynamic Programming Examples (video)
    • Skiena: CSE373 2012 - Lecture 22 - Applications of Dynamic Programming (video)
    • Simonson: Dynamic Programming 0 (starts at 59:18) (video)
    • Simonson: Dynamic Programming I - Lecture 11 (video)
    • Simonson: Dynamic programming II - Lecture 12 (video)
    • List of individual DP problems (each is short): Dynamic Programming (video)
  • Yale Lecture notes:
    • Dynamic Programming
  • Coursera:
    • The RNA secondary structure problem (video)
    • A dynamic programming algorithm (video)
    • Illustrating the DP algorithm (video)
    • Running time of the DP algorithm (video)
    • DP vs. recursive implementation (video)
    • Global pairwise sequence alignment (video)
    • Local pairwise sequence alignment (video)

• Combinatorics (n choose k) & Probability

  • Math Skills: How to find Factorial, Permutation and Combination (Choose) (video)
  • Make School: Probability (video)
  • Make School: More Probability and Markov Chains (video)
  • Khan Academy:
    • Course layout:
      • Basic Theoretical Probability
    • Just the videos - 41 (each are simple and each are short):
      • Probability Explained (video)

• NP, NP-Complete and Approximation Algorithms

  • Know about the most famous classes of NP-complete problems, such as traveling salesman and the knapsack problem, and be able to recognize them when an interviewer asks you them in disguise.
  • Know what NP-complete means.
  • Computational Complexity (video)
  • Simonson:
    • Greedy Algs. II & Intro to NP Completeness (video)
    • NP Completeness II & Reductions (video)
    • NP Completeness III (Video)
    • NP Completeness IV (video)
  • Skiena:
    • CSE373 2012 - Lecture 23 - Introduction to NP-CompletenessNP Completeness IV (video)
    • CSE373 2012 - Lecture 24 - NP-Completeness Proofs (video)
    • CSE373 2012 - Lecture 25 - NP-Completeness Challenge (video)
  • Complexity: P, NP, NP-completeness, Reductions (video)
  • Complexity: Approximation Algorithms (video)
  • Complexity: Fixed-Parameter Algorithms (video)
  • Peter Norvik discusses near-optimal solutions to traveling salesman problem:
    • Jupyter Notebook
  • Pages 1048 - 1140 in CLRS if you have it.

• Caches

  • LRU cache:
    • The Magic of LRU Cache (100 Days of Google Dev) (video)
    • Implementing LRU (video)
    • LeetCode - 146 LRU Cache (C++) (video)
  • CPU cache:
    • MIT 6.004 L15: The Memory Hierarchy (video)
    • MIT 6.004 L16: Cache Issues (video)

• Processes and Threads

  • Computer Science 162 - Operating Systems (25 videos):
    • for precesses and threads see videos 1-11
    • Operating Systems and System Programming (video)
  • What Is The Difference Between A Process And A Thread?
  • Covers:
    • Processes, Threads, Concurrency issues
      • difference between processes and threads
      • processes
      • threads
      • locks
      • mutexes
      • semaphores
      • monitors
      • how they work
      • deadlock
      • livelock
    • CPU activity, interrupts, context switching
    • Modern concurrency constructs with multicore processors
    • Process resource needs (memory: code, static storage, stack, heap, and also file descriptors, i/o)
    • Thread resource needs (shares above (minus stack) with other threads in same process but each has its own pc, stack counter, registers and stack)
    • Forking is really copy on write (read-only) until the new process writes to memory, then it does a full copy.
    • Context switching
      • How context switching is initiated by the operating system and underlying hardware
  • threads in C++ (series - 10 videos)
  • concurrency in Python (videos):
    • Short series on threads
    • Python Threads
    • Understanding the Python GIL (2010)
      • reference
    • David Beazley - Python Concurrency From the Ground Up: LIVE! - PyCon 2015
    • Keynote David Beazley - Topics of Interest (Python Asyncio)
    • Mutex in Python

  Scalability and System Design are very large topics with many topics and resources, since there is a lot to consider when designing a software/hardware system that can scale. Expect to spend quite a bit of time on this.

• System Design, Scalability, Data Handling

  • Considerations from Yegge:
    • scalability
      • Distill large data sets to single values
      • Transform one data set to another
      • Handling obscenely large amounts of data
    • system design
      • features sets
      • interfaces
      • class hierarchies
      • designing a system under certain constraints
      • simplicity and robustness
      • tradeoffs
      • performance analysis and optimization
  • START HERE: System Design from HiredInTech
  • How Do I Prepare To Answer Design Questions In A Technical Inverview?
  • 8 Things You Need to Know Before a System Design Interview
  • Algorithm design
  • Database Normalization - 1NF, 2NF, 3NF and 4NF (video)
  • System Design Interview - There are a lot of resources in this one. Look through the articles and examples. I put some of them below.
  • How to ace a systems design interview
  • Numbers Everyone Should Know
  • How long does it take to make a context switch?
  • Transactions Across Datacenters (video)
  • A plain english introduction to CAP Theorem
  • Paxos Consensus algorithm:
    • short video
    • extended video with use case and multi-paxos
    • paper
  • Consistent Hashing
  • NoSQL Patterns
  • Optional: UML 2.0 Series (vido)
  • OOSE: Software Dev Using UML and Java (21 videos):
    • Can skip this if you have a great grasp of OO and OO design practices.
    • OOSE: Software Dev Using UML and Java
  • SOLID OOP Principles:
    • Bob Martin SOLID Principles of Object Oriented and Agile Design (video)
    • SOLID Design Patterns in C# (video)
    • SOLID Principles (video)
    • S - Single Responsibility Principle | Single responsibility to each Object
      • more flavor
    • O - Open/Closed Principal | On production level Objects are ready for extension for not for modification
      • more flavor
    • L - Liskov Substitution Principal | Base Class and Derived class follow ‘IS A’ principal
      • more flavor
    • I - Interface segregation principle | clients should not be forced to implement interfaces they don't use
      • Interface Segregation Principle in 5 minutes (video)
      • more flavor
    • D -Dependency Inversion principle | Reduce the dependency In composition of objects.
      • Why Is The Dependency Inversion Principle And Why Is It Important
      • more flavor
  • Scalability:
    • Great overview (video)
    • Short series:
      • Clones
      • Database
      • Cache
      • Asynchronism
    • Scalable Web Architecture and Distributed Systems
    • Fallacies of Distributed Computing Explained
    • Pragmatic Programming Techniques
      • extra: Google Pregel Graph Processing
    • Jeff Dean - Building Software Systems At Google and Lessons Learned (video)
    • Introduction to Architecting Systems for Scale
    • Scaling mobile games to a global audience using App Engine and Cloud Datastore (video)
    • How Google Does Planet-Scale Engineering for Planet-Scale Infra (video)
    • The Importance of Algorithms
    • Sharding
    • Scale at Facebook (2009)
    • Scale at Facebook (2012), "Building for a Billion Users" (video)
    • Engineering for the Long Game - Astrid Atkinson Keynote(video)
    • 7 Years Of YouTube Scalability Lessons In 30 Minutes
      • video
    • How PayPal Scaled To Billions Of Transactions Daily Using Just 8VMs
    • How to Remove Duplicates in Large Datasets
    • A look inside Etsy's scale and engineering culture with Jon Cowie (video)
    • What Led Amazon to its Own Microservices Architecture
    • To Compress Or Not To Compress, That Was Uber's Question
    • Asyncio Tarantool Queue, Get In The Queue
    • When Should Approximate Query Processing Be Used?
    • Google's Transition From Single Datacenter, To Failover, To A Native Multihomed Architecture
    • Spanner
    • Egnyte Architecture: Lessons Learned In Building And Scaling A Multi Petabyte Distributed System
    • Machine Learning Driven Programming: A New Programming For A New World
    • The Image Optimization Technology That Serves Millions Of Requests Per Day
    • A Patreon Architecture Short
    • Tinder: How Does One Of The Largest Recommendation Engines Decide Who You'll See Next?
    • Design Of A Modern Cache
    • Live Video Streaming At Facebook Scale
    • A Beginner's Guide To Scaling To 11 Million+ Users On Amazon's AWS
    • How Does The Use Of Docker Effect Latency?
    • Does AMP Counter An Existential Threat To Google?
    • A 360 Degree View Of The Entire Netflix Stack
    • Latency Is Everywhere And It Costs You Sales - How To Crush It
    • Serverless (very long, just need the gist)
    • What Powers Instagram: Hundreds of Instances, Dozens of Technologies
    • Cinchcast Architecture - Producing 1,500 Hours Of Audio Every Day
    • Justin.Tv's Live Video Broadcasting Architecture
    • Playfish's Social Gaming Architecture - 50 Million Monthly Users And Growing
    • TripAdvisor Architecture - 40M Visitors, 200M Dynamic Page Views, 30TB Data
    • PlentyOfFish Architecture
    • Salesforce Architecture - How They Handle 1.3 Billion Transactions A Day
    • ESPN's Architecture At Scale - Operating At 100,000 Duh Nuh Nuhs Per Second
    • See "Messaging, Serialization, and Queueing Systems" way below for info on some of the technologies that can glue services together
    • Twitter:
      • O'Reilly MySQL CE 2011: Jeremy Cole, "Big and Small Data at @Twitter" (video)
      • Timelines at Scale
    • For even more, see "Mining Massive Datasets" video series in the Video Series section.
  • Practicing the system design process: Here are some ideas to try working through on paper, each with some documentation on how it was handled in the real world:
    • review: System Design from HiredInTech
    • cheat sheet
    • flow:
      1. Understand the problem and scope:
         • define the use cases, with interviewer's help
         • suggest additional features
         • remove items that interviewer deems out of scope
         • assume high availability is required, add as a use case
      2. Think about constraints:
         • ask how many requests per month
         • ask how many requests per second (they may volunteer it or make you do the math)
         • estimate reads vs. writes percentage
         • keep 80/20 rule in mind when estimating
         • how much data written per second
         • total storage required over 5 years
         • how much data read per second
      3. Abstract design:
         • layers (service, data, caching)
         • infrastructure: load balancing, messaging
         • rough overview of any key algorithm that drives the service
         • consider bottlenecks and determine solutions
    • Exercises:
      • Design a CDN network: old article
      • Design a random unique ID generation system
      • Design an online multiplayer card game
      • Design a key-value database
      • Design a function to return the top k requests during past time interval
      • Design a picture sharing system
      • Design a recommendation system
      • Design a URL-shortener system: copied from above
      • Design a cache system

• Papers

  • These are Google papers and well-known papers.
  • Reading all from end to end with full comprehension will likely take more time than you have. I recommend being selective on papers and their sections.
  • 1978: Communicating Sequential Processes
    • implemented in Go
    • Love classic papers?
  • 2003: The Google File System
    • replaced by Colossus in 2012
  • 2004: MapReduce: Simplified Data Processing on Large Clusters
    • mostly replaced by Cloud Dataflow?
  • 2007: What Every Programmer Should Know About Memory (very long, and the author encourages skipping of some sections)
  • 2012: Google's Colossus
    • paper not available
  • 2012: AddressSanitizer: A Fast Address Sanity Checker:
    • paper
    • video
  • 2013: Spanner: Google’s Globally-Distributed Database:
    • paper
    • video
  • 2014: Machine Learning: The High-Interest Credit Card of Technical Debt
  • 2015: Continuous Pipelines at Google
  • 2015: High-Availability at Massive Scale: Building Google’s Data Infrastructure for Ads
  • 2015: TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
  • 2015: How Developers Search for Code: A Case Study
  • 2016: Borg, Omega, and Kubernetes

• Testing

  • To cover:
    • how unit testing works
    • what are mock objects
    • what is integration testing
    • what is dependency injection
  • Agile Software Testing with James Bach (video)
  • Open Lecture by James Bach on Software Testing (video)
  • Steve Freeman - Test-Driven Development (that’s not what we meant) (video)
    • slides
  • TDD is dead. Long live testing.
  • Is TDD dead? (video)
  • Video series (152 videos) - not all are needed (video)
  • Test-Driven Web Development with Python
  • Dependency injection:
    • video
    • Tao Of Testing
  • How to write tests

• Scheduling

  • in an OS, how it works
  • can be gleaned from Operating System videos

• Implement system routines

  • understand what lies beneath the programming APIs you use
  • can you implement them?

• String searching & manipulations

  • Search pattern in text (video)
  • Rabin-Karp (videos):
    • Rabin Karps Algorithm
    • Precomputing
    • Optimization: Implementation and Analysis
    • Table Doubling, Karp-Rabin
    • Rolling Hashes, Amortized Analysis
  • Knuth-Morris-Pratt (KMP):
    • Pratt Algorithm
    • Tutorial: The Knuth-Morris-Pratt (KMP) String Matching Algorithm
  • Boyer–Moore string search algorithm
    • Boyer-Moore String Search Algorithm
    • Advanced String Searching Boyer-Moore-Horspool Algorithms (video)
  • Coursera: Algorithms on Strings

---

Final Review

This section will have shorter videos that can you watch pretty quickly to review most of the important concepts.
It's nice if you want a refresher often.
(More items will be added here)

General:

• Series of 2-3 minutes short subject videos (23 videos)
  • Videos
• Series of 2-5 minutes short subject videos - Michael Sambol (18 videos):
  • Videos

Sorts:

• Merge Sort: https://www.youtube.com/watch?v=GCae1WNvnZM

Books

Mentioned in Google Coaching

Read and do exercises:

• [ ] The Algorithm Design Manual (Skiena)

  • Book (can rent on kindle):
    • Algorithm Design Manual
  • Half.com is a great resource for textbooks at good prices.
  • Answers:
    • Solutions
    • Solutions
  • Errata

  Once you've understood everything in the daily plan, and read and done exercises from the the books above, read and do exercises from the books below. Then move to coding challenges (further down below)

Read first:

• Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition

Read second (recommended by many, but not in Google coaching docs):

• Cracking the Coding Interview, 6th Edition
  • If you see people reference "The Google Resume", it was a book replaced by "Cracking the Coding Interview".

Additional books

These were not suggested by Google but I added because I needed the background knowledge

• [ ] C Programming Language, Vol 2

  • answers to questions

• [ ] C++ Primer Plus, 6th Edition

• [ ] The Unix Programming Environment

• [ ] Programming Pearls

• [ ] Algorithms and Programming: Problems and Solutions

If you have time

• [ ] Introduction to Algorithms

  • Half.com is a great resource for textbooks at good prices.

• [ ] Elements of Programming Interviews

  • all code is in C++, if you're looking to use C++ in your interview
  • good book on problem solving in general.

Coding exercises/challenges

Once you've learned your brains out, put those brains to work. Take coding challenges every day, as many as you can.

Programming Question Prep:

• Great intro (copied from System Design section): Algorithm design:
• How to Find a Solution
• How to Dissect a Topcoder Problem Statement
• Mathematics for Topcoders

• [ ] Dynamic Programming – From Novice to Advanced

• MIT Interview Materials

• Exercises for getting better at a given language

Programming:

• LeetCode
• TopCoder
• Project Euler (math-focused)
• Codewars
• HackerRank
• Codility
• InterviewCake

• InterviewBit

• Mock interviewers from big companies

Once you're closer to the interview

• Cracking The Coding Interview Set 2 (videos):
  • Cracking The Code Interview
  • Cracking the Coding Interview - Fullstack Speaker Series
  • Ask Me Anything: Gayle Laakmann McDowell (author of Cracking the Coding Interview)

Your Resume

• Ten Tips for a (Slightly) Less Awful Resume
• Great stuff at the back of Cracking The Coding Interview

Be thinking of for when the interview comes

Think of about 20 interview questions you'll get, along the lines of the items below.
Have 2-3 answers for each
Have a story, not just data, about something you accomplished

• Why do you want this job?
• What's a tough problem you've solved?
• Biggest challenges faced?
• Best/worst designs seen?
• Ideas for improving an existing Google product.
• How do you work best, as an individual and as part of a team?
• Which of your skills or experiences would be assets in the role and why?
• What did you most enjoy at [job x / project y]?
• What was the biggest challenge you faced at [job x / project y]?
• What was the hardest bug you faced at [job x / project y]?
• What did you learn at [job x / project y]?
• What would you have done better at [job x / project y]?

Have questions for the interviewer

Some of mine (I already may know answer to but want their opinion or team perspective):

• How large is your team?
• What is your dev cycle look like? Do you do waterfall/sprints/agile?
• Are rushes to deadlines common? Or is there flexibility?
• How are decisions made in your team?
• How many meetings do you have per week?
• Do you feel your work environment helps you concentrate?
• What are you working on?
• What do you like about it?
• What is the work life like?

Once You've Got The Job

Congratulations!

• 10 things I wish I knew on my first day at Google

Keep learning.

You're never really done.

---

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

Everything below this point is optional. These are my recommendations, not Google's.
By studying these, you'll get greater exposure to more CS concepts, and will be better prepared for
any software engineering job.

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

---

Additional Learning

• Unicode

  • The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets
  • What Every Programmer Absolutely, Positively Needs To Know About Encodings And Character Sets To Work With Text

• Endianness

  • Big And Little Endian
  • Big Endian Vs Little Endian (video)
  • Big And Little Endian Inside/Out (video)
    • Very technical talk for kernel devs. Don't worry if most is over your head.
    • The first half is enough.

• Emacs and vi(m)

  • suggested by Yegge, from an old Amazon recruiting post: Familiarize yourself with a unix-based code editor
  • vi(m):
    • Editing With vim 01 - Installation, Setup, and The Modes (video)
    • VIM Adventures
    • set of 4 videos:
      • The vi/vim editor - Lesson 1
      • The vi/vim editor - Lesson 2
      • The vi/vim editor - Lesson 3
      • The vi/vim editor - Lesson 4
    • Using Vi Instead of Emacs
  • emacs:
    • Basics Emacs Tutorial (video)
    • set of 3 (videos):
      • Emacs Tutorial (Beginners) -Part 1- File commands, cut/copy/paste, cursor commands
      • Emacs Tutorial (Beginners) -Part 2- Buffer management, search, M-x grep and rgrep modes
      • Emacs Tutorial (Beginners) -Part 3- Expressions, Statements, ~/.emacs file and packages
    • Evil Mode: Or, How I Learned to Stop Worrying and Love Emacs (video)
    • Writing C Programs With Emacs
    • (maybe) Org Mode In Depth: Managing Structure (video)

• Unix command line tools

  • suggested by Yegge, from an old Amazon recruiting post. I filled in the list below from good tools.
  • bash
  • cat
  • grep
  • sed
  • awk
  • curl or wget
  • sort
  • tr
  • uniq
  • strace
  • tcpdump

• Information theory (videos)

  • Khan Academy
  • more about Markov processes:
    • Core Markov Text Generation
    • Core Implementing Markov Text Generation
    • Project = Markov Text Generation Walk Through
  • See more in MIT 6.050J Information and Entropy series below.

• Parity & Hamming Code (videos)

  • Intro
  • Parity
  • Hamming Code:
    • Error detection
    • Error correction
  • Error Checking

• Entropy

  • also see videos below
  • make sure to watch information theory videos first
  • Information Theory, Claude Shannon, Entropy, Redundancy, Data Compression & Bits (video)

• Cryptography

  • also see videos below
  • make sure to watch information theory videos first
  • Khan Academy Series
  • Cryptography: Hash Functions
  • Cryptography: Encryption

• Compression

  • make sure to watch information theory videos first
  • Computerphile (videos):
    • Compression
    • Entropy in Compression
    • Upside Down Trees (Huffman Trees)
    • EXTRA BITS/TRITS - Huffman Trees
    • Elegant Compression in Text (The LZ 77 Method)
    • Text Compression Meets Probabilities
  • Compressor Head videos
  • (optional) Google Developers Live: GZIP is not enough!

• Networking (videos)

  • Khan Academy
  • UDP and TCP: Comparison of Transport Protocols
  • TCP/IP and the OSI Model Explained!
  • Packet Transmission across the Internet. Networking & TCP/IP tutorial.
  • HTTP
  • SSL and HTTPS
  • SSL/TLS
  • HTTP 2.0
  • Video Series (21 videos)
  • Subnetting Demystified - Part 5 CIDR Notation

• Computer Security

  • MIT (23 videos)
    • Introduction, Threat Models
    • Control Hijacking Attacks
    • Buffer Overflow Exploits and Defenses
    • Privilege Separation
    • Capabilities
    • Sandboxing Native Code
    • Web Security Model
    • Securing Web Applications
    • Symbolic Execution
    • Network Security
    • Network Protocols
    • Side-Channel Attacks

• Garbage collection

  • Garbage collection (Java); Augmenting data str (video)
  • Compilers (video)
  • GC in Python (video)
  • Deep Dive Java: Garbage Collection is Good!
  • Deep Dive Python: Garbage Collection in CPython (video)

• Parallel Programming

  • Coursera (Scala)
  • Efficient Python for High Performance Parallel Computing (video)

• Design patterns

  • Quick UML review (video)
  • Learn these patterns:
    • strategy
    • singleton
    • adapter
    • prototype
    • decorator
    • visitor
    • factory, abstract factory
    • facade
    • observer
    • proxy
    • delegate
    • command
    • state
    • memento
    • iterator
    • composite
    • flyweight
  • Chapter 6 (Part 1) - Patterns (video)
  • Chapter 6 (Part 2) - Abstraction-Occurrence, General Hierarchy, Player-Role, Singleton, Observer, Delegation (video)
  • Chapter 6 (Part 3) - Adapter, Facade, Immutable, Read-Only Interface, Proxy (video)
  • Series of videos (27 videos)
  • Head First Design Patterns
    • I know the canonical book is "Design Patterns: Elements of Reusable Object-Oriented Software", but Head First is great for beginners to OO.
  • Handy reference: 101 Design Patterns & Tips for Developers

• Messaging, Serialization, and Queueing Systems

  • Thrift
    • Tutorial
  • Protocol Buffers
    • Tutorials
  • gRPC
    • gRPC 101 for Java Developers (video)
  • Redis
    • Tutorial
  • Amazon SQS (queue)
  • Amazon SNS (pub-sub)
  • RabbitMQ
    • Get Startet
  • Celery
    • First Steps With Celery
  • ZeroMQ
    • Intro - Read The Manual
  • ActiveMQ
  • Kafka
  • MessagePack
  • Avro

• Fast Fourier Transform

  • What is a Fourier transform? What is it used for?
  • What is the Fourier Transform? (video)
  • Divide & Conquer: FFT (video)
  • Understanding The FFT

• Bloom Filter

  • Given a Bloom filter with m bits and k hashing functions, both insertion and membership testing are O(k)
  • Bloom Filters
  • Bloom Filters | Mining of Massive Datasets | Stanford University
  • Tutorial
  • How To Write A Bloom Filter App

• van Emde Boas Trees

  • Divide & Conquer: van Emde Boas Trees (video)
  • MIT Lecture Notes

• Augmented Data Structures

  • CS 61B Lecture 39: Augmenting Data Structures

• Skip lists

  • "These are somewhat of a cult data structure" - Skiena
  • Randomization: Skip Lists (video)
  • For animations and a little more detail

• Network Flows

  • Ford-Fulkerson in 5 minutes (video)
  • Ford-Fulkerson Algorithm (video)
  • Network Flows (video)

• Disjoint Sets & Union Find

  • Disjoint Set
  • UCB 61B - Disjoint Sets; Sorting & selection (video)
  • Coursera (not needed since the above video explains it great):
    • Overview
    • Naive Implementation
    • Trees
    • Union By Rank
    • Path Compression
    • Analysis Options

• Math for Fast Processing

  • Integer Arithmetic, Karatsuba Multiplication (video)
  • The Chinese Remainder Theorem (used in cryptography) (video)

• Treap

  • Combination of a binary search tree and a heap
  • Treap
  • Data Structures: Treaps explained (video)
  • Applications in set operations

• Linear Programming (videos)

  • Linear Programming
  • Finding minimum cost
  • Finding maximum value

• Geometry, Convex hull (videos)

  • Graph Alg. IV: Intro to geometric algorithms - Lecture 9
  • Geometric Algorithms: Graham & Jarvis - Lecture 10
  • Divide & Conquer: Convex Hull, Median Finding

• Discrete math

  • see videos below

• Machine Learning

  • Why ML?
    • How Google Is Remaking Itself As A Machine Learning First Company
    • Large-Scale Deep Learning for Intelligent Computer Systems (video)
    • Deep Learning and Understandability versus Software Engineering and Verification by Peter Norvig
  • Google's Cloud Machine learning tools (video)
  • Google Developers' Machine Learning Recipes (Scikit Learn & Tensorflow) (video)
  • Tensorflow (video)
  • Tensorflow Tutorials
  • Practical Guide to implementing Neural Networks in Python])http://www.analyticsvidhya.com/blog/2016/04/neural-networks-python-theano/)
  • Courses:
    • Great starter course: Machine Learning
      • videos only
      • see videos 12-18 for a review of linear algebra (14 and 15 are duplicates)
    • Neural Networks for Machine Learning
    • Google's Deep Learning Nanodegree
    • Google/Kaggle Machine Learning Engineer Nanodegree
    • Self-Driving Car Engineer Nanodegree
    • Metis Online Course ($99 for 2 months)
  • Resources:
    • Great book: Data Science from Scratch: First Principles with Python: https://www.amazon.com/Data-Science-Scratch-Principles-Python/dp/149190142X
    • Data School: http://www.dataschool.io/

• Go

  • Videos:
    • Why Learn Go?
    • Go Programming
    • A Tour of Go
  • Books:
    • An Introduction to Programming in Go (read free online)
    • The Go Programming Language (Donovan & Kernighan)
  • Bootcamp

--

Additional Detail on Some Subjects

I added these to reinforce some ideas already presented above, but didn't want to include them
above because it's just too much. It's easy to overdo it on a subject.
You want to get hired in this century, right?

• [ ] More Dynamic Programming (videos)

  • 6.006: Dynamic Programming I: Fibonacci, Shortest Paths
  • 6.006: Dynamic Programming II: Text Justification, Blackjack
  • 6.006: DP III: Parenthesization, Edit Distance, Knapsack
  • 6.006: DP IV: Guitar Fingering, Tetris, Super Mario Bros.
  • 6.046: Dynamic Programming & Advanced DP
  • 6.046: Dynamic Programming: All-Pairs Shortest Paths
  • 6.046: Dynamic Programming (student recitation)

• [ ] Advanced Graph Processing (videos)

  • Synchronous Distributed Algorithms: Symmetry-Breaking. Shortest-Paths Spanning Trees
  • Asynchronous Distributed Algorithms: Shortest-Paths Spanning Trees

• [ ] MIT Probability (mathy, and go slowly, which is good for mathy things) (videos):

  • MIT 6.042J - Probability Introduction
  • MIT 6.042J - Conditional Probability
  • MIT 6.042J - Independence
  • MIT 6.042J - Random Variables
  • MIT 6.042J - Expectation I
  • MIT 6.042J - Expectation II
  • MIT 6.042J - Large Deviations
  • MIT 6.042J - Random Walks

• [ ] Simonson: Approximation Algorithms (video)

视频系列

坐下来享受一下吧。"netflix and skill" :P

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

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

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

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

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

• [ ] 离散数学 (19 个视频)

• [ ] 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 个视频)

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

• [ ] 斯坦福: 编程范例 (17 个视频)

  • C 和 C++ 课程

• [ ] 密码学导论

  • 本系列更多内容 (不分先后顺序)

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

Computer Science Courses

计算机科学课程

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