zdaiot

就业形势一年比一年严峻，去年算法岗已经是诸神黄昏了，今年只会更难，在这总结一下现有的资料。

目前从问师兄师姐情况来说，下面各项论重要性的话，笔试要考编程，也就是数据结构和算法，很重要，笔试不过甚至没有面试资格。而面试80%到90%问项目和比赛，10%问基础专业知识。所以重点在于好的简历和编程能力。

数据结构与算法

• 极客时间课程（已经“看完”，用于刷题时回看补充基础知识）
• 剑指Offer刷题（66道题，一天三道，至少两遍）
• LeetCode高频题和每日刷题计划（精选算法200道，刷完剑指offer后一天三道）

专业知识

以下内容大部分转载从图(Graph)到图卷积(Graph Convolution)：漫谈图神经网络模型 (一)。觉得这篇文章写得很好，先摘抄过来，用于日后添加个人理解。

历史脉络

在开始正文之前，笔者先带大家回顾一下图神经网络的发展历史。不过，因为图神经网络的发展分支非常之多，笔者某些叙述可能并不全面，一家之言仅供各位读者参考：

1. 图神经网络的概念最早在2005年提出。2009年Franco博士在其论文 [2]中定义了图神经网络的理论基础，笔者呆会要讲的第一种图神经网络也是基于这篇论文。
2. 最早的GNN主要解决的还是如分子结构分类等严格意义上的图论问题。但实际上欧式空间(比如像图像 Image)或者是序列(比如像文本 Text)，许多常见场景也都可以转换成图(Graph)，然后就能使用图神经网络技术来建模。
3. 2009年后图神经网络也陆续有一些相关研究，但没有太大波澜。直到2013年，在图信号处理(Graph Signal Processing)的基础上，Bruna(这位是LeCun的学生)在文献 [3]中首次提出图上的基于频域(Spectral-domain)和基于空域(Spatial-domain)的卷积神经网络。
4. 其后至今，学界提出了很多基于空域的图卷积方式，也有不少学者试图通过统一的框架将前人的工作统一起来。而基于频域的工作相对较少，只受到部分学者的青睐。
5. 值得一提的是，图神经网络与图表示学习(Represent Learning for Graph)的发展历程也惊人地相似。2014年，在word2vec [4]的启发下，Perozzi等人提出了DeepWalk [5]，开启了深度学习时代图表示学习的大门。更有趣的是，就在几乎一样的时间，Bordes等人提出了大名鼎鼎的TransE [6]，为知识图谱的分布式表示(Represent Learning for Knowledge Graph)奠定了基础。

图神经网络(Graph Neural Network)

半监督学习可以利用“少”的有标记样本和“多”的无标记样本改善分类器的性能，在一定程度上提高学习能力，成为当前机器学习研究领域的热点问题。

半监督学习机理

下图给出了一个缺少概念标记的未标记数据为何能够帮助学习器学习的简单例子。用“+”表示正样本、“-”表示负样本、“.”表示未标记样本。现在需要预测“*”这个样本的标记。当仅利用有标记样本进行学习(如图 1.2(a)所示)时，会很自然地将该样本判为正样本；但若考虑大量未标记样本(如图 1.2(b)所示)的分布，则可以发现待预测样本和有标记的负样本同属于一个簇，由于处于同一个簇中样本的性质应该相似，因此将该样本预测为负样本应更加合理。从此例可以看出，未标记样本提供的分布信息能够帮助和指导学习过程。

半监督学习假设

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

作者整理了数据结构和算法中必知必会的30个代码实现。我先把这些都记录下来，之后按照会对这些实现，并放在github上。

Day 1：数组和链表

关于数组和链表的几个必知必会的代码实现

数组

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

实战测试题（一）

假设猎聘网有 10 万名猎头顾问，每个猎头顾问都可以通过做任务（比如发布职位），来积累积分，然后通过积分来下载简历。假设你是猎聘网的一名工程师，如何在内存中存储这 10 万个猎头 ID 和积分信息，让它能够支持这样几个操作：

• 根据猎头的 ID 快速查找、删除、更新这个猎头的积分信息；
• 查找积分在某个区间的猎头 ID 列表；
• 查询积分从小到大排在第 x 位的猎头 ID 信息；
• 查找按照积分从小到大排名在第 x 位到第 y 位之间的猎头 ID 列表。

相关章节

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

要想游刃有余地解决今后实际开发要面对的问题，光是熟知每种数据结构和算法的功能、特点、时间空间复杂度，还是不够的。毕竟工程上的问题不是算法题。

• 算法题的背景、条件、限制都非常明确，只需要在规定的输入、输出下，找最优解就可以了。
• 工程上的问题往往都比较开放，在选择数据结构和算法的时候，往往需要综合各种因素，比如编码难度、维护成本、数据特征、数据规模等，最终选择一个工程的最合适解，而非理论上的最优解。

实际软件开发中，如何权衡各种因素，合理地选择使用哪种数据结构和算法，作者总结了六条经验。

时间、空间复杂度不能跟性能划等号

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

短网址服务是常用的服务。例如下面两个长度不同的网址，都可以跳转到作者的一个Github开源项目里。第二个是通过新浪提供的短网址服务生成的。

1
2

原始网址：https://github.com/wangzheng0822/ratelimiter4j
短网址：http://t.cn/EtR9QEG

这样简单的功能，是如何实现的呢？底层都依赖了哪些数据结构和算法呢？

短网址服务整体介绍

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

微服务，就是把复杂的大应用，解耦拆分成几个小的应用。这样做的好处有很多。比如，这样有利于团队组织架构的拆分，毕竟团队越大协作的难度越大；再比如，每个应用都可以独立运维，独立扩容，独立上线，各个应用之间互不影响。不用像原来那样，一个小功能上线，整个大应用都要重新发布。

不过，有利就有弊。大应用拆分成微服务之后，服务之间的调用关系变得更复杂，平台的整体复杂熵升高，出错的概率、debug 问题的难度都高了好几个数量级。所以，为了解决这些问题，服务治理便成了微服务的一个技术重点。

所谓服务治理，简单点讲，就是管理微服务，保证平台整体正常、平稳地运行。服务治理涉及的内容比较多，比如鉴权、限流、降级、熔断、监控告警等等。这些服务治理功能的实现，底层依赖大量的数据结构和算法。

本节，就以其中的鉴权和限流这两个功能，看看它们的实现过程中都要用到哪些数据结构和算法。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

Disruptor 是一种内存消息队列。从功能上讲，它其实有点儿类似 Kafka。不过，它是线程之间用于消息传递的队列。因为它非常优秀的性能，在 Apache Storm、Camel、Log4j 2 等很多知名项目中都有广泛应用。

那么Disruptor 是如何做到如此高性能的？其底层依赖了哪些数据结构和算法？

基于循环队列的“生产者 - 消费者模型”

在“生产者 - 消费者模型”中，“生产者”生产数据，并且将数据放到一个中心存储容器中。之后，“消费者”从中心存储容器中，取出数据消费。

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

从本节开始进入到实战环节，主要通过一些开源项目、经典系统，介绍如何将数据结构和算法应用到项目中。

本节主要看下经典数据库 Redis 中的常用数据类型，底层都是用哪种数据结构实现的？

Redis 数据库介绍

Redis 是一种键值（Key-Value）数据库。相对于关系型数据库（比如 MySQL），Redis 也被叫作非关系型数据库。