算法

讲一下Dijkstra算法

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。
它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止

基本思想

1. 通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。
2. 此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
3. 初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 … 重复该操作，直到遍历完所有顶点。

操作步骤

1. 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为”起点s到该顶点的距离”[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。
2. 从U中选出”距离最短的顶点k”，并将顶点k加入到S中；同时，从U中移除顶点k。
3. 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。
4. 重复步骤(2)和(3)，直到遍历完所有顶点。

单纯的看上面的理论可能比较难以理解，下面通过实例来对该算法进行说明。

图解

注意：这里的B(23)应该是B(13)，图有问题。

计算64位二进制整数1的个数

反复除2取余数

10万亿个文件，按照文件名称排序

外排序

　　传统的排序算法一般指内排序算法，针对的是数据可以一次全部载入内存中的情况。但是面对海量数据，即数据不可能一次全部载入内存，需要用到外排序的方法。外排序采用分块的方法（分而治之），首先将数据分块，对块内数据按选择一种高效的内排序策略进行排序。然后采用归并排序的思想对于所有的块进行排序，得到所有数据的一个有序序列。

　　例如，考虑一个1G文件，可用内存100M的排序方法。首先将文件分成10个100M，并依次载入内存中进行排序，最后结果存入硬盘。得到的是10个分别排序的文件。接着从每个文件载入9M的数据到输入缓存区，输出缓存区大小为10M。对输入缓存区的数据进行归并排序，输出缓存区写满之后写在硬盘上，缓存区清空继续写接下来的数据。对于输入缓存区，当一个块的9M数据全部使用完，载入该块接下来的9M数据，一直到所有的9个块的所有数据都已经被载入到内存中被处理过。最后我们得到的是一个1G的排序好的存在硬盘上的文件。

1TB数据使用32GB内存如何排序

1. 把磁盘上的1TB数据分割为40块（chunks），每份25GB。（注意，要留一些系统空间！）
2. 顺序将每份25GB数据读入内存，使用quick sort算法排序。
3. 把排序好的数据（也是25GB）存放回磁盘。
4. 循环40次，现在，所有的40个块都已经各自排序了。（剩下的工作就是如何把它们合并排序！）
5. 从40个块中分别读取25G/40=0.625G入内存（40 input buffers）。
6. 执行40路合并，并将合并结果临时存储于2GB 基于内存的输出缓冲区中。当缓冲区写满2GB时，写入硬盘上最终文件，并清空输出缓冲区；当40个输入缓冲区中任何一个处理完毕时，写入该缓冲区所对应的块中的下一个0.625GB，直到全部处理完成。

继续优化

磁盘I/O通常是越少越好（最好完全没有），那么如何降低磁盘I/O操作呢？

• 关键就在第5和第6步中的40路输入缓冲区，我们可以先做8路merge sort，把每8个块合并为1路，然后再做5-to-1的合并操作。
• 再深入思考一下，如果有多余的硬件，如何继续优化呢？有三个方向可以考虑：
• 使用并发：如多磁盘（并发I/O提高）、多线程、使用异步I/O、使用多台主机集群计算。
• 提升硬件性能：如更大内存、更高RPM的磁盘、升级为SSD、Flash、使用更多核的CPU。
• 提高软件性能：比如采用radix sort、压缩文件（提高I/O效率）等。

手撕K路归并

#二路归并排序def MergeSort(list):    if len(list) <= 1:        return list    num = len(list) // 2    left = MergeSort(list[:num])    right = MergeSort(list[num:])    return Merge(left,right)def Merge(left,right):    l,r = 0, 0    result = []    while l < len(left) and r < len(right):        if left[l] < right[r]:            result = left[l]            l += 1        else:            result = right[r]            r += 1    result += left[l:]    result += right[r:]    return result

负载均衡算法有哪些

负载均衡在大型网站中应用已经是十分普遍了，它在大型网站中处理高并发请求扮演着十分重要的角色。那么负载均衡算法又有哪些呢，一下是一些常见的负载均衡算法：

轮询法（ROUND ROBIN）

轮询法基本上算是最简单的负载均衡算法了，它的思想就是不管啥情况，对所有的服务器节点全部按顺序来，将请求按照顺序轮流地分配到各个服务器上。这种算法会使每台服务器处理的请求是相同的，所以适合用于服务器硬件条件基本都相同的场景。

加权轮询法（WEIGHT ROBIN）

在轮询算法的基础上添加了权重的条件，刚才提到轮询算法对所有服务器“一视同仁”，那么加权轮询算法无疑就是对各个服务器有了“高低贵贱之分”，没办法，服务器的处理水平不同，只能是让那些强悍的机器优先并多处理些请求，比较弱的机器嘛就让它稍稍压力小一点。

随机法（RANDOM）

随机算法也是一种适用场景比较多的负载均衡算法，这种算法基本思想也很简单，随机生成一个数字（或者随机挑一个IP地址）出来，然后挑到谁就去谁家，当然，如果随机数是等概况生成的，那时间长了，基本上跟轮询算法也没啥区别了，当然区别最主要的还是在顺序，随机么就没那么严格的顺序了。

加权随机法（WEIGHT RANDOM）

加权随机法是在随机法的基础上加了加权的条件，随机法时间长了，基本上跟一般轮询算法就没啥区别了，刚才也提到了，如果服务器的配置都差不多，那也就算了，但是如果服务器处理能力差异比较大，那水平高的和水平低的服务器都给这么多任务，那对于高配置来讲就有点浪费，对于低配置的服务器来讲却有点吃不消，所以在这种配置差异性比较大的情况下，加权的工作还是十分必要的。加权随机算法就是适用于这样的场景。

最小连接法（LEAST CONNECTIONS）

这个算法思想也很简单，顾名思义，哪个服务器的连接少，就分配给哪个服务器新的请求，合情合理，但是这种算法的缺点就是，跟我们上面分析的几种算法一个意思，一个比较弱的服务器和一个比较彪悍的服务器，本来就是前者连接要少，后者要大，如果非得谁的少新请求给谁，那就是弱服务器的连接要等于强服务器的连接，无疑这样会让弱服务器吃不消，或者让强服务器造成资源浪费，所以在这里依然可以用加权的方法来解决这个问题——加权最小连接法。

源地址哈希法（HASH）

Hash法对于大部分码农来讲并不陌生，当年《数据机构》课程上这一节依然能够栩栩如生地浮现在脑海中。源地址哈希法就是可以把客户端的IP地址拿出来，然后计算出IP地址的hash值，hash值是一个很大的正整数，那么问题来了，怎么才能映射到相对应的服务器了，答案很简单：serverPosition=hashCode%serverListSize。

数据结构

完全二叉树

完全二叉树是一种特殊的二叉树，满足以下要求：

1. 所有叶子节点都出现在 k 或者 k-1 层，而且从 1 到 k-1 层必须达到最大节点数；
2. 第 k 层可以不是满的，但是第 k 层的所有节点必须集中在最左边。 需要注意的是不要把完全二叉树和“满二叉树”搞混了，完全二叉树不要求所有树都有左右子树，但它要求：
3. 任何一个节点不能只有左子树没有右子树
4. 叶子节点出现在最后一层或者倒数第二层，不能再往上

当我们用数组实现一个完全二叉树时，叶子节点可以按从上到下、从左到右的顺序依次添加到数组中，然后知道一个节点的位置，就可以轻松地算出它的父节点、孩子节点的位置。

二叉查找树

二叉查找树（BST：Binary Search Tree）是一种特殊的二叉树，它改善了二叉树节点查找的效率。二叉查找树有以下性质：

对于任意一个节点 n，

• 其左子树（left subtree）下的每个后代节点（descendant node）的值都小于节点 n 的值；
• 其右子树（right subtree）下的每个后代节点的值都大于节点 n 的值。

所谓节点 n 的子树，可以将其看作是以节点 n 为根节点的树。子树的所有节点都是节点 n 的后代，而子树的根则是节点 n 本身。

也就是说，二叉查找树中，左子树都比节点小，右子树都比节点大，递归定义。

根据二叉排序树这个特点我们可以知道：二叉排序树的中序遍历一定是从小到大的。

平衡二叉树

平衡二叉树的提出就是为了保证树不至于太倾斜，尽量保证两边平衡。因此它的定义如下：

1. 平衡二叉树要么是一棵空树
2. 要么保证左右子树的高度之差不大于 1
3. 子树也必须是一颗平衡二叉树

也就是说，树的两个左子树的高度差别不会太大。

红黑树

前面我们已经说过，红黑树，本质上来说就是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

但它是如何保证一棵n个结点的红黑树的高度始终保持在h = logn的呢？这就引出了红黑树的5条性质：

1）每个结点要么是红的，要么是黑的。  2）根结点是黑的。  3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。  4）如果一个结点是红的，那么它的俩个儿子都是黑的。  5）对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

正是红黑树的这5条性质，使得一棵n个结点是红黑树始终保持了logn的高度，从而也就解释了上面我们所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论的原因。

如下图所示，即是一颗红黑树(下图引自wikipedia：http://t.cn/hgvH1l)：

普通二叉树删除过程

删除节点为叶子节点

删除节点只有一个子节点：只有一个左子节点和只有一个右子节点

删除节点有两个子节点：这种情况比较复杂，需要寻找后继节点，即比要删除的节点的关键值次高的节点是它的后继节点。说得简单一些，后继节点就是比要删除的节点的关键值要大的节点集合中的最小值。（右子节点的左后代）

如果后继节点是刚好是要删除节点的右子节点

如果后继节点为要删除节点的右子节点的左后代

哈希表

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

1.开发定址法

　　如果遇到冲突的时候怎么办呢？就找hash表剩下空余的空间，找到空余的空间然后插入。就像你去商店买东西，发现东西卖光了，怎么办呢？找下一家有东西卖的商家买呗

2.链地址法

　　上面所说的开发定址法的原理是遇到冲突的时候查找顺着原来哈希地址查找下一个空闲地址然后插入，但是也有一个问题就是如果空间不足，那他无法处理冲突也无法插入数据，因此需要装填因子(插入数据/空间)<=1。

优先队列

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。通常采用堆数据结构来实现。

操作系统

并发与并行

并发：交替做不同事情的能力
并行：同时做不同事情的能力
专业术语：
并发：不同的代码块交替执行
并行：不同的代码块同时执行

并发和并行的意义：

并发和并行都可以处理“多任务”，二者的主要区别在于是否是“同时进行”多个的任务。

但是 涉及到任务分解（有先后依赖的任务就不能做到并行）、任务运行（可能要考虑互斥、锁、共享等）、结果合并

进程与线程

进程是资源分配的最小单位，线程是程序执行的最小单位。
进程有自己的独立的地址空间， 线程共享进程中的数据，使用相同的地址空间。
进程自己通信方式主要使用特别的方式来进行通信。线程之间的通信非常的方便， 同一进程下的线程共享全局变量、静态变量等数据。
多进程程序更加的健壮，其中一个进程死掉了并不影响其他的进程，多线程中只要有一个线程死掉，那么整个进程也死掉了。

进程之间进行通信常用的有几种方式：管道，消息队列， 信号量， 共享内存

线程同步通常有4中方式： 临界区、事件、互斥量、信号量。

孤儿进程，僵尸进程

孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么这些子进程将成为孤儿进程。孤儿进程将被 init 进程（进程号为 1）所收养，并由 init 进程对它们完成状态收集工作。由于孤儿进程会被 init 进程收养，所以孤儿进程不会对系统造成危害。

僵尸进程：一个子进程的进程描述符在子进程退出时不会释放，只有当父进程通过 wait() 或 waitpid() 获取了子进程信息后才会释放。如果子进程退出，而父进程并没有调用 wait() 或 waitpid()，那么子进程的进程描述符仍然保存在系统中，这种进程称之为僵尸进程。

文件描述符

内核通过文件描述符访问文件。

一个文件如何组织存放到硬盘上

不知道

你知道的文件系统

没研究过

死锁

导致死锁的原因：
1.因为系统资源不足
2.进程运行推进顺序不合适
3.资源分配不当
导致死锁的四个必要条件：
1.一次一个进程只能访问一个资源， 其他进程不能访问已分配的资源。
2.当一个进程等待其他进程时， 继续占有已分配的资源时
3.不能强行抢占进程已有的资源
4.存在一个封闭的进程链， 导致每一个进程都占有下一个进程所需的资源

银行家算法

计算机网络

OSI七层模型

五层模型

TCP/IP协议栈

不知道，有很多，UDP、TCP、HTTP、HTTPS、DNS、DHCP

time-wait的作用

• 确保最后一个确认报文能够到达。如果 B 没收到 A 发送来的确认报文，那么就会重新发送连接释放请求报文，A 等待一段时间就是为了处理这种情况的发生。

• 等待一段时间是为了让本连接持续时间内所产生的所有报文都从网络中消失，使得下一个新的连接不会出现旧的连接请求报文。

  HTTP

状态码

状态码 类别 含义

1XX Informational（信息性状态码） 接收的请求正在处理

2XX Success（成功状态码） 请求正常处理完毕

3XX Redirection（重定向状态码） 需要进行附加操作以完成请求

4XX Client Error（客户端错误状态码） 服务器无法处理请求

5XX Server Error（服务器错误状态码） 服务器处理请求出错

三次握手

第一次握手：主机A发送位码为syn＝1,随机产生seq number=x的数据包到服务器，客户端进入SYN_SEND状态，等待服务器的确认；主机B由SYN=1知道，A要求建立联机；

第二次握手：主机B收到请求后要确认联机信息，向A发送ack number(主机A的seq+1),syn=1,ack=1,随机产生seq=y的包,此时服务器进入SYN_RECV状态;

第三次握手：主机A收到后检查ack number是否正确，即第一次发送的seq number+1,以及位码ack是否为1，若正确，主机A会再发送ack number(主机B的seq+1),ack=1，主机B收到后确认seq值与ack=1则连接建立成功。客户端和服务器端都进入ESTABLISHED状

态，完成TCP三次握手。

TCP位码,有6种标示:SYN(synchronous建立联机) ACK(acknowledgement 确认) PSH(push传送) FIN(finish结束) RST(reset重置) URG(urgent紧急)

Sequence number(顺序号码) Acknowledge number(确认号码)

四次挥手

POST传文件，怎么知道是不是传输完了

不知道

TCP，UDP区别

tcp是传输控制协议，其提供面向连接、可靠的字节流服务，通信双方必须依照三次握手协议连接之后才能传输数据， tcp提供了超时重传、 丢弃重复数据、检验数据流量控制等功能。
UDP是用户数据包协议， 它提供了一个简单的不可靠的面向无连接的服务，在双方未连接时也能传输数据因而速度特别快。

请求重传机制

TCP的重传机制有两种：超时重传和快速重传。

超时重传

说白了就是在请求包发出去的时候，开启一个计时器，当计时器达到时间之后，没有收到ACK，则就进行重发请求的操作，一直重发直到达到重发上限次数或者收到ACK。

快速重传

当接收方收到的数据包是不正常的序列号，那么接收方会重复把应该收到的那一条ACK重复发送，这个时候，如果发送方收到连续3条的同一个序列号的ACK，那么就会启动快速重传机制，把这个ACK对应的发送包重新发送一次。

路由的两种方式（rip, ospf），怎么实现

RIP 是一种基于距离向量的路由选择协议。距离是指跳数，直接相连的路由器跳数为 1。跳数最多为 15，超过 15 表示不可达。RIP 按固定的时间间隔仅和相邻路由器交换自己的路由表，经过若干次交换之后，所有路由器最终会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器地址。

开放表示 OSPF 不受某一家厂商控制，而是公开发表的；最短路径优先表示使用了 Dijkstra 提出的最短路径算法SPF。

OSPF 具有以下特点：

• 向本自治系统中的所有路由器发送信息，这种方法是洪泛法。
• 发送的信息就是与相邻路由器的链路状态，链路状态包括与哪些路由器相连以及链路的度量，度量用费用、距离、时延、带宽等来表示。
• 只有当链路状态发生变化时，路由器才会发送信息。

数据库

redis的持久化

1. 快照： 默认使用这种方式，将数据快照存放在特定的二进制文件中。
2. AOF: 将每一条命令都储存， 恢复时再将每一天命令进行运行。

mysql的B+树

事务

数据库事务的4个特性：原子性、持久性、一致性、隔离性

ACID

ACID

1. 原子性（Atomicity）

事务被视为不可分割的最小单元，事务的所有操作要么全部提交成功，要么全部失败回滚。

回滚可以用回滚日志来实现，回滚日志记录着事务所执行的修改操作，在回滚时反向执行这些修改操作即可。

2. 一致性（Consistency）

数据库在事务执行前后都保持一致性状态。在一致性状态下，所有事务对一个数据的读取结果都是相同的。3. 隔离性（Isolation）

一个事务所做的修改在最终提交以前，对其它事务是不可见的。

4. 持久性（Durability）

一旦事务提交，则其所做的修改将会永远保存到数据库中。即使系统发生崩溃，事务执行的结果也不能丢失。

使用重做日志来保证持久性。

分布式了解什么

更多的机子，处理更多的数据。

数据库如何建索引

数据库索引对于非主键索引使用B树， 对于主键索引使用B+树

对于建立索引的列， mysql的查询效率会提高很多。

设计模式

文件并发访问量很高的时候，怎么保证可用性

限流

设计一个负载均衡算法，实现每个用户随机访问不同服务器，不能重复

源地址hash，因为hash值小概率出现重复

设计一个系统，限制单个用户每5分钟只能访问100次接口

令牌桶算法，知道有这么一回事，但是没有仔细研究过

说一下怎么实现nginx的反向代理功能

不太了解，反向代理服务器架设在服务器端，通过缓冲经常被请求的页面来缓解服务器的工作量，将客户机请求转发给内部网络上的目标服务器；并将从服务器上得到的结果返回给Internet上请求连接的客户端，此时代理服务器与目标主机一起对外表现为一个服务器。

项目

项目中为什么用消息队列，哪些场景用到了消息队列

解耦、异步、削峰。