下面的内容都是可选的。通过学习这些内容，你将会得到更多的有关 CS 的概念，并将为所有的软件工程工作做更好的准备。
额外书籍
你可以从以下的书单挑选你有兴趣的主题来研读。
- UNIX 环境高级编程
- 老，但却很棒
- Linux 命令行大全
- 现代选择
- TCP-IP 详解系列
- Head First 设计模式
- 设计模式入门介绍
- 设计模式：可复用面向对象软件的基础
- 也被称为“四人帮”（Gang of Four(GOF)）
- 经典设计模式书籍
- 算法设计手冊（Skiena）
- 作为复习以及问题辨别
- 这本书中算法的部分难度已经超过面试会出现的
- 本书分为两个部分:
- 数据结构和算法课本
- 优点:
- 跟其他算法课本一样是个很棒的复习素材
- 包含作者以往解决工业及学术上问题的经验的故事
- 含 C 语言代码示例
- 缺点:
- 某些地方跟《算法导论》（CLRS）一样艰深，但在某些主题，算法导论或许是更好的选择。
- 第 7、8、9 章有点难以消化，因为某些地方并没有解释得很清楚，或者根本上我就是个学渣
- 别会错意了，我很喜欢 Skiena 的教学方法以及他的风格。
- 优点:
- 算法目录:
- 这个部分是买这本书的最大原因
- 我即将着手进行这部分，一旦完成这部分我会再更新上来
- 数据结构和算法课本
- 可以在 kindle 上租
- 解答：
- 勘误表
- 算法 (Jeff Erickson)
- 编程卓越之道（第一卷）：深入理解计算机
- 该书于 2004 年出版，虽然有些过时，但是对于简单了解计算机而言，这是一个了不起的资源
- 作者发明了高阶组合语言 HLA，所以提到，并且举了一些 HLA 的例子。里面没有用到很多，但都是很棒的组合语言的例子。
- 这些章节值得阅读，为你提供良好的基础：
- 第 2 章──数字表示
- 第 3 章──二进制算术和位运算
- 第 4 章──浮点表示
- 第 5 章──字符表示
- 第 6 章──内存组织和访问
- 第 7 章──组合数据类型和内存对象
- 第 9 章──CPU 体系结构
- 第 10 章──指令集架构
- 第 11 章──内存体系结构和组织
- 算法导论
- 重要提示：读这本书的价值有限。本书很好地回顾了算法和数据结构，但不会教你如何编写良好的代码。你必须能够有效地编写一个不错的解决方案
- 又称 CLR，有时是 CLRS，因为 Stein 最后才加入
- 计算机体系结构，第六版：定量方法
- 对于更丰富、更时新（2017 年）但较长的处理方式
系统设计、可扩展性和数据处理
如果您有 4 年以上的工作经验，可以预期会遇到系统设计问题。
- 可扩展性和系统设计是一个非常广泛的主题，涵盖了许多内容和资源， 因为在设计一个可以扩展的软件/硬件系统时需要考虑很多因素。 预计需要花费相当多的时间来学习这方面的知识。
- 考虑要点：
- 可扩展性
- 将大数据集归纳为单一值
- 将一个数据集转换为另一个数据集
- 处理海量数据
- 系统设计
- 功能集
- 接口
- 类层次结构
- 在特定约束下设计系统
- 简单性和鲁棒性
- 权衡
- 性能分析和优化
- 可扩展性
- 从这里开始: The System Design Primer
- HiredInTech 的系统设计
- 如何准备回答技术面试中的设计问题？
- 通过 8 个步骤掌握系统设计面试
- 数据库规范化 - 第一范式、第二范式、第三范式和第四范式（视频）
- 系统设计面试 - 这个资源有很多内容。浏览文章和示例。我列出了一些示例在下面。
- 如何在系统设计面试中脱颖而出
- 每个人都应该了解的数字
- 进行上下文切换需要多长时间？
- 跨数据中心的事务（视频）
- CAP 定理的简明英文介绍
- MIT 6.824：分布式系统，2020 年春季（20 个视频）
- 共识算法：
- Paxos - Paxos 协议 - Computerphile（视频）
- Raft - Raft 分布式共识算法简介（视频）
- 一致性哈希
- NoSQL 模式
- 可扩展性：
- 您不需要掌握所有这些内容，只需选择一些您感兴趣的。
- 优秀的概述（视频）
- 短系列：
- 可扩展的 Web 架构和分布式系统
- 分布式计算的谬误解释
- Jeff Dean - 在 Google 构建软件系统以及吸取的教训（视频）
- 架构师为规模而设计的介绍
- 缩放移动游戏以面向全球受众使用 App Engine 和 Cloud Datastore（视频）
- 谷歌是如何进行面向全球基础设施的大规模工程的（视频）
- 算法的重要性
- 分片
- 针对长期目标的工程 - Astrid Atkinson 主题演讲（视频）
- 在 30 分钟内了解 YouTube 7 年的可扩展性经验
- PayPal 如何使用仅 8 台 VM 每天处理数十亿次交易
- 如何在大型数据集中去重
- 通过 Jon Cowie 深入了解 Etsy 的规模和工程文化（视频）
- Amazon 是如何转向自己的微服务架构的
- 压缩还是不压缩，这是 Uber 面临的问题
- 何时应使用近似查询处理？
- 谷歌从单一数据中心到故障转移再到本地多家数据中心架构的转变
- 为每天处理数百万请求的图像优化技术
- Patreon 架构简介
- 如何在 Instagram 庞大的推荐引擎中决定您将看到谁？
- 现代缓存设计
- 在 Facebook 规模下进行直播视频流
- 在亚马逊 AWS 上如何扩展到 1100 万以上的用户
- 全面了解 Netflix 整个堆栈
- 延迟无处不在，而且它会让您丧失销售机会 - 如何应对
- Instagram 的动力：数百个实例，几十种技术
- Salesforce 架构 - 如何处理每天 13 亿次交易
- ESPN 规模上的架构 - 每秒操作 10 万次“嘟嘟噜嘟嘟噜”
- 在下面的“消息、序列化和队列系统”部分查看一些将服务连接在一起的技术信息
- Twitter:
- 欲知更多信息，请参阅Video Series 部分中的“Mining Massive Datasets”视频系列
- 练习系统设计过程：以下是一些建议您在纸上尝试的想法，每个想法都有一些关于如何在现实世界中处理的文档：
- 复习: The System Design Primer
- HiredInTech 的系统设计
- 速查表
- 流程：
- 理解问题和范围：
- 定义用例，与面试官的帮助
- 提出额外的功能
- 移除面试官认为超出范围的项目
- 假设需要高可用性，并将其添加为用例
- 考虑限制：
- 询问每月有多少个请求
- 询问每秒有多少个请求（他们可能会主动提供或让您计算）
- 估计读取与写入的百分比
- 保持估计时考虑 80/20 法则
- 每秒写入多少数据
- 在 5 年内所需的总存储量
- 每秒读取多少数据
- 抽象设计：
- 层（服务、数据、缓存）
- 基础架构：负载均衡、消息传递
- 驱动服务的任何关键算法的粗略概述
- 考虑瓶颈并确定解决方案
- 理解问题和范围：
- 练习：
附加学习
我把它们加进来是为了让你成为更全方位的软件工程师，并且留意一些技术以及算法，让你拥有更大的工具箱。
编译器
Emacs and vi(m)
- 熟悉基于 unix 的代码编辑器
- vi(m):
- emacs:
Unix 命令行工具
信息论 (视频)
- Khan Academy 可汗学院
- 更多有关马尔可夫的内容:
- 关于更多信息，请参照下方 MIT 6.050J 信息和系统复杂度的内容。
奇偶校验位 & 汉明码 (视频)
系统熵值（Entropy）
- 请参考下方视频
- 观看之前，请先确定观看了信息论的视频
- 信息理论, 克劳德·香农, 熵值, 系统冗余, 数据比特压缩 (视频)
密码学
压缩
- 观看之前，请先确定观看了信息论的视频
- Computerphile (视频)：
- 数据压缩的艺术
- (可选) 谷歌开发者：GZIP 还差远了呢!
计算机安全
垃圾回收
并行编程
消息传递，序列化和队列系统
- Thrift
- 协议缓冲
- gRPC
- Redis
- Amazon 的 SQS 系统 (队列)
- Amazon 的 SNS 系统 (pub-sub)
- RabbitMQ
- Celery
- ZeroMQ
- ActiveMQ
- Kafka
- MessagePack
- Avro
A*搜索算法
快速傅里叶变换
布隆过滤器
- 给定布隆过滤器 m 比特位和 k 个哈希函数，插入和成员检测都会是 O(k)。
- 布隆过滤器（视频）
- 布隆过滤器 | 数据挖掘 | Stanford University（视频）
- 教程
- 如何写一个布隆过滤器应用
HyperLogLog
局部敏感哈希
- 用于确定文件的相似性
- MD5 或 SHA 的反义词，用于确定 2 个文档/字符串是否完全相同
- Simhashing（希望如此）变得简单
van Emde Boas 树
增强数据结构
平衡查找树（Balanced search trees）
-
掌握至少一种平衡查找树（并懂得如何实现）：
-
“在各种平衡查找树当中，AVL 树和 2-3 树已经成为了过去，而红黑树（red-black trees）看似变得越来越受人青睐。 这种令人特别感兴趣的数据结构，亦称伸展树（splay tree）。 它可以自我管理，且会使用轮换来移除任何访问过根节点的键。” —— Skiena
-
因此，在各种各样的平衡查找树当中，我选择了伸展树来实现。 虽然，通过我的阅读，我发现在面试中并不会被要求实现一棵平衡查找树。 但是，为了胜人一筹，我们还是应该看看如何去实现。在阅读了大量关于红黑树的代码后， 我才发现伸展树的实现确实会使得各方面更为高效。
- 伸展树：插入、查找、删除函数的实现，而如果你最终实现了红黑树，那么请尝试一下：
- 跳过删除函数，直接实现搜索和插入功能
-
我希望能阅读到更多关于 B 树的资料，因为它也被广泛地应用到大型的数据集当中。
-
AVL 树
- 实际中： 我能告诉你的是，该种树并无太多的用途，但我能看到有用的地方在哪里： AVL 树是另一种平衡查找树结构。其可支持时间复杂度为 O(log n) 的查询、插入及删除。 它比红黑树严格意义上更为平衡，从而导致插入和删除更慢，但遍历却更快。正因如此，才彰显其结构的魅力。 只需要构建一次，就可以在不重新构造的情况下读取， 适合于实现诸如语言字典（或程序字典，如一个汇编程序或解释程序的操作码）。
- MIT AVL 树 / AVL 树的排序（视频）
- AVL 树（视频）
- AVL 树的实现（视频）
- 分离与合并
- [Review] AVL Trees (playlist) in 19 minutes (video)
-
伸展树
- 实际中： 伸展树一般用于缓存、内存分配者、路由器、垃圾回收者、数据压缩、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）
- 二分查找及红黑树的介绍
- [Review] Red-Black Trees (playlist) in 30 minutes (video)
-
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 指块的大小、即缓存行的大小）
- [Review] B-Trees (playlist) in 26 minutes (video)
k-D 树
- 非常适合在矩形或更高维度的对象中查找点数
- 最适合 k 近邻
- kNN K-d 树算法（视频）
跳表
- “有一种非常迷幻的数据类型” - Skiena
- 随机化: 跳表 (视频)
- 更生动详细的解释
网络流
不相交集 & 联合查找
快速处理的数学
树堆 (Treap)
- 一个二叉搜索树和一个堆的组合
- 树堆
- 数据结构：树堆的讲解（视频）
- 集合操作的应用(Applications in set operations)
线性规划（Linear Programming）（视频）
几何：凸包（Geometry, Convex hull）（视频）
离散数学
一些主题的额外内容
我添加了这些内容来加强上面已经提出的一些观点，但是不想把它们放在上面，因为那样会太多。 对于一个主题来说，过度处理很容易。 你希望在本世纪被雇佣吗？
-
SOLID
-
Bob Martin SOLID Principles of Object Oriented and Agile Design (视频)
-
S - 单一职责原则 | 每个对象负责一个单一职责 | Single responsibility to each Object
-
O - 开闭原则 | 在生产级别上，对象应准备好进行扩展，但不进行修改
-
L - 里氏替换原则 | 基类和派生类遵循‘是一个’原则
-
I - 接口隔离原则 | 客户端不应被强制实现不使用的接口
-
D -依赖反转原则 | 在对象的组合中减少依赖
-
Union-Find
-
动态规划的更多内容 (视频)
-
图形处理进阶 (视频)
-
MIT 概率论 (过于数学，进度缓慢，但这对于数学的东西却是必要之恶) (视频):
-
字符串匹配
-
Rabin-Karp（视频）
-
Knuth-Morris-Pratt (KMP)：
-
Boyer–Moore 字符串搜索算法
-
- 刚开始时很棒，但是当它超过 KMP 时，它变得比需要复杂得多
- 很好的字典树解释
- 可以跳过
-
排序
-
斯坦福大学关于排序算法的视频:
-
Shai Simonson 视频，Aduni.org:
-
Steven Skiena 关于排序的视频:
-
NAND 到 Tetris: 从第一原理构建现代计算机
视频系列
坐下来，尽情享受。
计算机科学课程
算法实现
论文
- 喜欢经典的论文？
- 1978: 通信顺序处理
- 2003: The Google 文件系统
- 2012 年被 Colossus 取代了
- 2004: MapReduce: Simplified Data Processing on Large Clusters
- 大多被云数据流取代了?
- 2006 年：Bigtable：结构化数据的分布式存储系统
- 2006 年：针对松散耦合的分布式系统的 Chubby Lock 服务
- 2007 年：Dynamo：亚马逊的高可用键值存储
- Dynamo 论文启动了 NoSQL 革命
- 2007: 每个程序员都应该知道的内存知识 (非常长，作者建议跳过某些章节来阅读)
- 2012: AddressSanitizer: 快速的内存访问检查器:
- 2013: Spanner: Google 的分布式数据库:
- 2015: Google 的持续流水线
- 2015: 大规模高可用性：构建 Google 广告数据基础设施
- 2015: 开发人员如何搜索代码：一个案例研究
- 更多论文： 1,000 篇论文