机器学习面试八股8

131 栈溢出有哪些情况

1）、局部数组过大。当函数内部的数组过大时，有可能导致堆栈溢出。

2）、递归调用层次太多。递归函数在运行时会执行压栈操作，当压栈次数太多时，也会导

致堆栈溢出。

3）指针或数组越界。这种情况最常见，例如进行字符串拷贝，或处理用户输入等等。

132 红黑树

自平衡二叉查找树，用途是实现关联数组。

它可以在 O(log n)时间内做查找，插入和删除，这里的 n 是树中元素的数目。

set, multiset, map, multimap)应用了红黑树的变体

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制

一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

性质 1. 节点是红色或黑色。

性质 2. 根节点是黑色。

性质 3 每个叶节点（NIL 节点，空节点）是黑色的。

性质 4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连

续的红色节点)

性质 5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长

133 对一千万个整数排序,整数范围在[-1000,1000]间,用什么排序最快?

计数排序,计数排序的基本思想为在排序前先统计这组数中其它数小于这个数的个数,其时间

复杂度为 ,其中 n 为整数的个数,k 为所有数的范围

134 堆排序的思想

将待排序的序列构成一个大顶堆,这个时候整个序列的最大值就是堆顶的根节点,将它与末尾

节点进行交换,然后末尾变成了最大值,然后剩余 n-1 个元素重新构成一个堆,这样得到这 n 个

元素的次大值,反复进行以上操作便得到一个有序序列。

135 快速排序的最优情况

链接

快速排序(Quick Sort)使用分治法策略。

它的基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；

其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分

数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序流程：

(1) 从数列中挑出一个基准值。

(2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面 (相同的数可

以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。

(3) 递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。

快速排序是不稳定的算法，它不满足稳定算法的定义。

快速排序的最优情况是 Partition 每次划分的都很均匀,当排序的元素为 n 个,则递归树的深度

为 。在第一次做 Partition 的时候需对所有元素扫描一遍,获得的枢纽元将所有元素一分为二,

不断的划分下去直到排序结束,而在此情况下快速排序的最优时间复杂度为 。

136topK 给出 3 种解法

1）局部淘汰法 – 借助“冒泡排序”获取 TopK

（1）可以避免对所有数据进行排序，只排序部分；

（2）冒泡排序是每一轮排序都会获得一个最大值，则 K 轮排序即可获 TopK。

时间复杂度：排序一轮是 O(N)，则 K 次排序总时间复杂度为：O(KN)。

空间复杂度：O(K)，用来存放获得的 topK，

2）局部淘汰法 – 借助数据结构"堆"获取 TopK

我们使用小顶堆来实现。

取出 K 个元素放在另外的数组中，对这 K 个元素进行建堆。

然后循环从 K 下标位置遍历数据，只要元素大于堆顶，我们就将堆顶赋值为该元素，然后

重新调整为小顶堆。

循环完毕后，K 个元素的堆数组就是我们所需要的 TopK。

时间复杂度：每次对 K 个元素进行建堆，时间复杂度为：O(KlogK)，加上 N-K 次的循环，则

总时间复杂度为 O((K+(N-K))logK)，即 O(NlogK)，

空间复杂度：O(K)，

3）分治法 – 借助”快速排序“方法获取 TopK

思路：

（1）比如有 10 亿的数据，找处 Top1000，我们先将 10 亿的数据分成 1000 份，每份 100 万

条数据。

（2）在每一份中找出对应的 Top 1000，整合到一个数组中，得到 100 万条数据，这样过滤

掉了 999%%的数据。

（3）使用快速排序对这 100 万条数据进行”一轮“排序，一轮排序之后指针的位置指向的

数字假设为 S，会将数组分为两部分，一部分大于 S 记作 Si，一部分小于 S 记作 Sj。

（4）如果 Si 元素个数大于 1000，我们对 Si 数组再进行一轮排序，再次将 Si 分成了 Si 和

Sj。如果 Si 的元素小于 1000，则我们需要在 Sj 中获取 1000-count(Si)个元素的，也就是对 Sj

进行排序

（5）如此递归下去即可获得 TopK。

时间复杂度：一份获取前 TopK 的时间复杂度：O((N/n)logK)。则所有份数为：O(NlogK)，但

是分治法我们会使用多核多机的资源，比如我们有 S 个线程同时处理。则时间复杂度为：

O((N/S)logK)。之后进行快排序，一次的时间复杂度为：O(N),假设排序了 M 次之后得到结果，

则时间复杂度为：O(MN)。所以 ，总时间复杂度大约为 O(MN+(N/S)logK) 。

空间复杂度：空间复杂度为 O(N)。

137 小顶堆的调整过程

堆排序的步骤分为三步:

1）建堆；2）交换数据；3）向下调整。

138BFS 和 DFS 的实现思想

BFS:(1)顶点 v 入队列(2)当队列为非空时继续执行否则停止(3)从队列头取顶点 v,查找顶点 v

的所有子节点并依次从队列尾插入(4)跳到步骤 2

DFS:(1)访问顶点 v 并打印节点(2)遍历 v 的子节点 w,若 w 存在递归的执行该节点。

139 关联规则具体有哪两种算法,它们之间的区别

Apriori 和 FP-growth 算法

Apriori 多次扫描交易数据库,每次利用候选频繁集产生频繁集,

而 FP-growth 则利用树形结构,无需产生候选频繁集而直接得到频繁集,减少了扫描交易数据

库的次数,提高算法的效率

但是 Apriori 有较好的扩展性可用于并行计算。一般使用 Apriori 算法进行关联分析,FP-

growth 算法来高效发现频繁项集。

140 贪婪算法

贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最

有利)的选择，从而希望能够导致结果是最好或者最优的算法。

贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)

最优解的结果。

贪婪算法并没有固定的算法解决框架，算法的关键是贪婪策略的选择，根据不同的问题选

择不同的策略。策略的选择必须具备无后效性，即某个状态的选择不会影响到之前的状态

只与当前状态有关，

其基本的解题思路为：

1)建立数学模型来描述问题;

2)把求解的问题分成若干个子问题;

3)对每一子问题求解，得到子问题的局部最优解;

4)把子问题对应的局部最优解合成原来整个问题的一个近似最优解。

位运算中异或的性质：两个相同数字异或=0，一个数和 0 异或还是它本身。

141 什么是 python 的生成器?

python 生成器是一个返回可以迭代对象的函数,可以被用作控制循环的迭代行为。生成器类

似于返回值为数组的一个函数,这个函数可以接受参数,可以被调用,一般的函数会返回包括

所有数值的数组,生成器一次只能返回一个值,这样消耗的内存将会大大减小。

使用了 yield 的函数被称为生成器（generator）

调用一个生成器函数，返回的是一个迭代器对象。

142 迭代器?

迭代器有两个基本的方法：iter() 和 next()。

list=[1,2,3,4]

it = iter(list) # 创建迭代器对象

print (next(it))

143python 中 is 和==的区别

is 是用来判断两个变量引用的对象是否为同一个（is 判断的是指针是否指向同一个位置）,

==用于判断引用对象的值是否相等。可以通过 id()函数查看引用对象的地址。

144python 方法解析顺序

优先级从高到低为:实例本身 类 继承类(继承关系越近,越先定义,优先级越高)

145 如何判断两个 dict 是否一样,list 头上删除元素,字符串拼接?

通过==可以判断两个 dict 是否相同

list.pop(0)删除 list 第一个元素

join()函数进行字符串拼接

146pytorch 中 cuda()作用,两个 Tensor,一个加了 cuda(),一个没加,相加后很怎样?

cuda()将操作对象放在 GPU 内存中,加了 cuda()的 Tensor 放在 GPU 内存中而没加的 Tensor 放

在 CPU 内存中,所以这两个 Tensor 相加会报错

device = torch.device(“cuda:1” )

model = model.to(device)

Tensor 和 numpy.ndarray 之间可以相互转换：

• Numpy 转 Tensor: torch.from_numpy(numpy 矩阵)

• Tensor 转 Numpy: Torch 矩阵.numpy()

• numpy 与 Tensor 最大的区别就是在对 GPU 的支持上。Tensor 只需要调用 cuda()函数就可

以将其转化为能在 GPU 上运行的类型。CPU 转 GPU: data.cuda()

• GPU 转 CPU: data.cpu()

147python 中 dict 和 list 的区别,dict 的内部实现

dict 查找速度快,占用的内存较大,list 查找速度慢,占用内存较小,

dict 不能用来存储有序集合。

Dict 用{}表示,list 用[]表示。

dict 是通过 hash 表实现的 ,dict 为一个数组 ,数组的索引键是通过 hash 函数处理后得到

的,hash 函数的目的是使键值均匀的分布在数组中。

148python dict 按照 value 进行排序

sorted（d.items(),key=lambda x:x[1],reverse=True）

149C++中 static 关键字的作用

c/c++共有

1）：修饰全局变量时，表明一个全局变量只对定义在同一文件中的函数可见。

2）：修饰局部变量时，表明该变量的值不会因为函数终止而丢失。

3）：修饰函数时，表明该函数只在同一文件中调用。

c++独有：

4）：修饰类的数据成员，表明对该类所有对象这个数据成员都只有一个实例。即该实例归

所有对象共有。

5）：用 static 修饰不访问非静态数据成员的类成员函数。这意味着一个静态成员函数只能

访问它的参数、类的静态数据成员和全局变量

150Python 多进程

方式一: os.fork()

方式二:使用 multiprocessing 模块:创建 Process 的实例，传入任务执行函数作为参数

方式三:使用 multiprocessing 模块:派生 Process 的子类，重写 run 方法

方式四:使用进程池 Pool

深拷贝与浅拷贝的区别

深复制和浅复制最根本的区别在于是否是真正获取了一个对象的复制实体，而不是引用。

浅复制 —-只是拷贝了基本类型的数据，而引用类型数据，复制后也是会发生引用，我们把

这种拷贝叫做“（浅复制）浅拷贝”，换句话说，浅复制仅仅是指向被复制的内存地址，

如果原地址中对象被改变了，那么浅复制出来的对象也会相应改变。 拷贝父对象，不会拷

贝对象的内部的子对象

深复制 —-在计算机中开辟了一块新的内存地址用于存放复制的对象。 完全拷贝了父对象

及其子对象。