面试的是BAT某家机器学习岗

1.可以用于任务分配的算法

贪心，动态规划，分支限界法，拍卖算法以及一些人工智能算法（蚁群，遗传等）

特点是什么？有什么优缺点？

2.回归分析有哪些？说一下他们的原理以及特点，优缺点。

1， 线性回归 

线性回归的因变量是连续变量，自变量可以是连续变量，也可以是分类变量。如果只有一个自变量，且只有两类，那这个回归就等同于t检验。如果只有一个自变量，且有三类或更多类，那这个回归就等同于方差分析。如果有2个自变量，一个是连续变量，一个是分类变量，那这个回归就等同于协方差分析。所以线性回归一定要认准一点，因变量一定要是连续变量。当然还有其它条件，比如独立性、线性、等方差性、正态性。。

2， logistic回归，与线性回归并成为两大回归，应用范围一点不亚于线性回归，甚至有青出于蓝之势。因为logistic回归太好用了，而且太有实际意义了。解释起来直接就可以说，如果具有某个危险因素，发病风险增加2.3倍，听起来多么地让人通俗易懂。线性回归相比之下其实际意义就弱了。logistic回归与线性回归恰好相反，因变量一定要是分类变量，不可能是连续变量。分类变量既可以是二分类，也可以是多分类，多分类中既可以是有序，也可以是无序。二分类logistic回归有时候根据研究目的又分为条件logistic回归和非条件logistic回归。条件logistic回归用于配对资料的分析，非条件logistic回归用于非配对资料的分析，也就是直接随机抽样的资料。无序多分类logistic回归有时候也成为多项logit模型，有序logistic回归有时也称为累积比数logit模型。 

3， cox回归，cox回归的因变量就有些特殊，因为他的因变量必须同时有2个，一个代表状态，必须是分类变量，一个代表时间，应该是连续变量。只有同时具有这两个变量，才能用cox回归分析。cox回归主要用于生存资料的分析，生存资料至少有两个结局变量，一是死亡状态，是活着还是死亡？二是死亡时间，如果死亡，什么时间死亡？如果活着，从开始观察到结束时有多久了？所以有了这两个变量，就可以考虑用cox回归分析。

4， poisson回归，poisson回归相比就不如前三个用的广泛了。但实际上，如果你能用logistic回归，通常也可以用poission回归，poisson回归的因变量是个数，也就是观察一段时间后，发病了多少人？或者死亡了多少人？等等。其实跟logistic回归差不多，因为logistic回归的结局是是否发病，是否死亡，也需要用到发病例数、死亡例数。大家仔细想想，其实跟发病多少人，死亡多少人一个道理。只是poission回归名气不如logistic回归大，所以用的人也不如logistic回归多。但不要因此就觉得poisson回归没有用。

5， probit回归，在医学里真的是不大用，最关键的问题就是probit这个词太难理解了，通常翻译为概率单位。probit函数其实跟logistic函数十分接近，二者分析结果也十分接近。可惜的是，probit回归的实际含义真的不如logistic回归容易理解，由此导致了它的默默无名，但据说在社会学领域用的似乎更多一些。

6，负二项回归。所谓负二项指的是一种分布，其实跟poission回归、logistic回归有点类似，poission回归用于服从poission分布的资料，logistic回归用于服从二项分布的资料，负二项回归用于服从负二项分布的资料。说起这些分布，大家就不愿意听了，多么抽象的名词，我也很头疼。如果简单点理解，二项分布你可以认为就是二分类数据，poission分布你可以认为是计数资料，也就是个数，而不是像身高等可能有小数点，个数是不可能有小数点的。负二项分布呢，也是个数，只不过比poission分布更苛刻，如果你的结局是个数，而且结局可能具有聚集性，那可能就是负二项分布。简单举例，如果调查流感的影响因素，结局当然是流感的例数，如果调查的人有的在同一个家庭里，由于流感具有传染性，那么同一个家里如果一个人得流感，那其他人可能也被传染，因此也得了流感，那这就是具有聚集性，这样的数据尽管结果是个数，但由于具有聚集性，因此用poission回归不一定合适，就可以考虑用负二项回归。既然提到这个例子，我在上一篇文章说了，用于logistic回归的数据通常也能用poission回归，就像上面案例，我们可以把结局作为二分类，每个人都有两个状态，得流感或者不得流感，这是个二分类结局，那就可以用logistic回归。但是这里的数据存在聚集性怎么办呢，幸亏logistic回归之外又有了更多的扩展，你可以用多水平logistic回归模型，也可以考虑广义估计方程。这两种方法都可以处理具有层次性或重复测量资料的二分类因变量。

7，weibull回归，有时中文音译为威布尔回归。weibull回归估计你可能就没大听说过了，其实这个名字只不过是个噱头，吓唬人而已。上一篇说过了，生存资料的分析常用的是cox回归，这种回归几乎统治了整个生存分析。但其实夹缝中还有几个方法在顽强生存着，而且其实很有生命力，只是国内大多不愿用而已。weibull回归就是其中之一。cox回归为什么受欢迎呢，因为它简单，用的时候不用考虑条件（除了等比例条件之外），大多数生存数据都可以用。而weibull回归则有条件限制，用的时候数据必须符合weibull分布。怎么，又是分布？！估计大家头又大了，是不是想直接不往下看了，还是用cox回归吧。不过我还是建议看下去。为什么呢？相信大家都知道参数检验和非参数检验，而且可能更喜欢用参数检验，如t检验，而不喜欢用非参数检验，如秩和检验。那这里的weibull回归和cox回归基本上可以说是分别对应参数检验和非参数检验。参数检验和非参数检验的优缺点我也在前面文章里通俗介绍了，如果数据符合weibull分布，那么直接套用weibull回归当然是最理想的选择，他可以给出你最合理的估计。如果数据不符合weibull分布，那如果还用weibull回归，那就套用错误，肯定结果也不会真实到哪儿去。所以说，如果你能判断出你的数据是否符合weibull分布，那当然最好的使用参数回归，也就是weibull回归。但是如果你实在没什么信心去判断数据分布，那也可以老老实实地用cox回归。cox回归可以看作是非参数的，无论数据什么分布都能用，但正因为它什么数据都能用，所以不可避免地有个缺点，每个数据用的都不是恰到好处。weibull回归就像是量体裁衣，把体形看做数据，衣服看做模型，weibull回归就是根据你的体形做衣服，做出来的肯定对你正合身，对别人就不一定合身了。cox回归呢，就像是到商场去买衣服，衣服对很多人都合适，但是对每个人都不是正合适，只能说是大致合适。至于到底是选择麻烦的方式量体裁衣，还是图简单到商场直接去买现成的，那就根据你的喜好了，也根据你对自己体形的了解程度，如果非常熟悉，当然就量体裁衣了。如果不大了解，那就直接去商场买大众化衣服吧。

8，主成分回归。主成分回归是一种合成的方法，相当于主成分分析与线性回归的合成。主要用于解决自变量之间存在高度相关的情况。这在现实中不算少见。比如你要分析的自变量中同时有血压值和血糖值，这两个指标可能有一定的相关性，如果同时放入模型，会影响模型的稳定，有时也会造成严重后果，比如结果跟实际严重不符。当然解决方法很多，最简单的就是剔除掉其中一个，但如果你实在舍不得，毕竟这是辛辛苦苦调查上来的，删了太可惜了。如果舍不得，那就可以考虑用主成分回归，相当于把这两个变量所包含的信息用一个变量来表示，这个变量我们称它叫主成分，所以就叫主成分回归。当然，用一个变量代替两个变量，肯定不可能完全包含他们的信息，能包含80%或90%就不错了。但有时候我们必须做出抉择，你是要100%的信息，但是变量非常多的模型？还是要90%的信息，但是只有1个或2个变量的模型？打个比方，你要诊断感冒，是不是必须把所有跟感冒有关的症状以及检查结果都做完？还是简单根据几个症状就大致判断呢？我想根据几个症状大致能能确定90%是感冒了。不用非得100%的信息不是吗？模型也是一样，模型是用于实际的，不是空中楼阁。既然要用于实际，那就要做到简单。对于一种疾病，如果30个指标能够100%确诊，而3个指标可以诊断80%，我想大家会选择3个指标的模型。这就是主成分回归存在的基础，用几个简单的变量把多个指标的信息综合一下，这样几个简单的主成分可能就包含了原来很多自变量的大部分信息。这就是主成分回归的原理。

9，岭回归。岭回归的名称由来我也没有查过，可能是因为它的图形有点像岭。不要纠结于名称。岭回归也是用于处理自变量之间高度相关的情形。只是跟主成分回归的具体估计方法不同。线性回归的计算用的是最小二乘估计法，当自变量之间高度相关时，最小二乘回归估计的参数估计值会不稳定，这时如果在公式里加点东西，让它变得稳定，那就解决了这一问题了。岭回归就是这个思想，把最小二乘估计里加个k，改变它的估计值，使估计结果变稳定。至于k应该多大呢？可以根据岭迹图来判断，估计这就是岭回归名称的由来。你可以选非常多的k值，可以做出一个岭迹图，看看这个图在取哪个值的时候变稳定了，那就确定k值了，然后整个参数估计不稳定的问题就解决了。

10，偏最小二乘回归。偏最小二乘回归也可以用于解决自变量之间高度相关的问题。但比主成分回归和岭回归更好的一个优点是，偏最小二乘回归可以用于例数很少的情形，甚至例数比自变量个数还少的情形。听起来有点不可思议，不是说例数最好是自变量个数的10倍以上吗？怎么可能例数比自变量还少，这还怎么计算？可惜的是，偏最小二乘回归真的就有这么令人发指的优点。所以，如果你的自变量之间高度相关、例数又特别少、而自变量又很多（这么多无奈的毛病），那就现在不用发愁了，用偏最小二乘回归就可以了。它的原理其实跟主成分回归有点像，也是提取自变量的部分信息，损失一定的精度，但保证模型更符合实际。因此这种方法不是直接用因变量和自变量分析，而是用反映因变量和自变量部分信息的新的综合变量来分析，所以它不需要例数一定比自变量多。偏最小二乘回归还有一个很大的优点，那就是可以用于多个因变量的情形，普通的线性回归都是只有一个因变量，而偏最小二乘回归可用于多个因变量和多个自变量之间的分析。因为它的原理就是同时提取多个因变量和多个自变量的信息重新组成新的变量重新分析，所以多个因变量对它来说无所谓。

3.介绍SVM原理，核函数等

SVM方法是通过一个非线性映射p，把样本空间映射到一个高维乃至无穷维的特征空间中（Hilbert空间），使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性可分的问题．简单地说，就是升维和线性化．升维，就是把样本向高维空间做映射，一般情况下这会增加计算的复杂性，甚至会引起“维数灾难”，因而人们很少问津．但是作为分类、回归等问题来说，很可能在低维样本空间无法线性处理的样本集，在高维特征空间中却可以通过一个线性超平面实现线性划分（或回归）．一般的升维都会带来计算的复杂化，SVM方法巧妙地解决了这个难题：应用核函数的展开定理，就不需要知道非线性映射的显式表达式；由于是在高维特征空间中建立线性学习机，所以与线性模型相比，不但几乎不增加计算的复杂性，而且在某种程度上避免了“维数灾难”．这一切要归功于核函数的展开和计算理论．

选择不同的核函数，可以生成不同的SVM，常用的核函数有以下4种：

⑴线性核函数K(x,y)=x·y；

⑵多项式核函数K(x,y)=[(x·y)+1]^d；

⑶径向基函数K(x,y)=exp(-|x-y|^2/d^2）

⑷二层神经网络核函数K(x,y)=tanh(a(x·y)+b）．

4.说一下贝叶斯原理，贝叶斯分类过程和贝叶斯局限性

原理的话自己解释，看肯定就是基于贝叶斯公式，

1.贝叶斯决策的优点

（1）贝叶斯决策能对信息的价值或是否需要采集新的信息做出科学的判断.（2）它能对调查结果的可能性加以数量化的评价,而不是像一般的决策方法那样,对调查结果或者是完全相信,或者是完全不相信.

（3）如果说任何调查结果都不可能完全准确,先验知识或主观概率也不是完全可以相信的,那么贝叶斯决策则巧妙地将这两种信息有机地结合起来了.

（4）它可以在决策过程中根据具体情况下不断地使用,使决策逐步完善和更加科学.

2.贝叶斯决策的局限性：

（1）它需要的数据多,分析计算比较复杂,特别在解决复杂问题时,这个矛盾就更为突出.

（2）有些数据必须使用主观概率,有些人不太相信,这也妨碍了贝叶斯决策方法的推广使用.

5.Java多态，Map,和垃圾回收

态就是指程序中定义的引用变量所指向的具体类型和通过该引用变量发出的方法调用在编程时并不确定，而是在程序运行期间才确定，即一个引用变量倒底会指向哪个类的实例对象，该引用变量发出的方法调用到底是哪个类中实现的方法，必须在由程序运行期间才能决定。因为在程序运行时才确定具体的类，这样，不用修改源程序代码，就可以让引用变量绑定到各种不同的类实现上，从而导致该引用调用的具体方法随之改变，即不修改程序代码就可以改变程序运行时所绑定的具体代码，让程序可以选择多个运行状态，这就是多态性。

多态的好处

多态的出现大大的提高程序的扩展性。

Map:

将键映射到值的对象。一个映射不能包含重复的键；每个键最多只能映射到一个值。此接口取代 Dictionary 类，后者完全是一个抽象类，而不是一个接口。

Map 接口提供三种collection 视图，允许以键集、值集或键-值映射关系集的形式查看某个映射的内容。映射顺序 定义为迭代器在映射的 collection 视图上返回其元素的顺序。某些映射实现可明确保证其顺序，如 TreeMap 类；另一些映射实现则不保证顺序，如HashMap 类。

垃圾回收：

ava  语言中一个显著的特点就是引入了java回收机制，是c++程序员最头疼的内存管理的问题迎刃而解，它使得java程序员在编写程序的时候不在考虑内存管理。由于有个垃圾回收机制，java中的额对象不在有“作用域”的概念，只有对象的引用才有“作用域”。垃圾回收可以有效的防止内存泄露，有效的使用空闲的内存；

内存泄露：指该内存空间使用完毕后未回收，在不涉及复杂数据结构的一般情况下，java的内存泄露表现为一个内存对象的生命周期超出了程序需要它的时间长度，我们有是也将其称为“对象游离”；

垃圾回收机制的算法

java语言规范没有明确的说明JVM 使用哪种垃圾回收算法，但是任何一种垃圾回收算法一般要做两件基本事情：（1）发现无用的信息对象；（2）回收将无用对象占用的内存空间。使该空间可被程序再次使用。

1。引用计数法（Reference Counting Collector）

引用计数算法是垃圾回收器中的早起策略，在这种方法中，堆中的每个对象实例都有一个引用计数器，点一个对象被创建时，且该对象实例分配给一个变量，该变量计数设置为1 ，当任何其他变量赋值为这个对象的引用时，计数加1 ，（a=b ，则b引用的对象实例计数器+1）但当一个对象实例的某个引用超过了生命周期或者被设置为一个新值时，对象实例的引用计数器减1，任何引用计数器为0 的对象实例可以当做垃圾收集。 当一个对象的实例被垃圾收集是，它引用的任何对象实例的引用计数器减1.

6.堆排序：

1.堆

堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：

Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]

即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。

堆分为大顶堆和小顶堆，满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆，满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。

2.堆排序的思想

利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。

其基本思想为(大顶堆)：

1)将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无须区；

2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];

3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

操作过程如下：

1)初始化堆：将R[1..n]构造为堆；

2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。

因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。

7.TCP三次握手：

（1）第一次握手：Client将标志位SYN置为1，随机产生一个值seq=J，并将该数据包发送给Server，Client进入SYN_SENT状态，等待Server确认。

（2）第二次握手：Server收到数据包后由标志位SYN=1知道Client请求建立连接，Server将标志位SYN和ACK都置为1，ack=J+1，随机产生一个值seq=K，并将该数据包发送给Client以确认连接请求，Server进入SYN_RCVD状态。

（3）第三次握手：Client收到确认后，检查ack是否为J+1，ACK是否为1，如果正确则将标志位ACK置为1，ack=K+1，并将该数据包发送给Server，Server检查ack是否为K+1，ACK是否为1，如果正确则连接建立成功，Client和Server进入ESTABLISHED状态，完成三次握手，随后Client与Server之间可以开始传输数据了。