面试问题
常识题
TCP、UDP协议的区别以及各自的应用场景
请看TCP和UDP,着重了解两者的概念、应用及区别。
向量相似度计算
计算两个向量的相似度通常涉及使用不同的距离度量或相似性度量方法,具体方法取决于你的应用场景和数据类型。以下是一些常见的方法:
- 余弦相似度(Cosine Similarity):
余弦相似度是计算两个向量之间的夹角余弦值。这是最常用于文本和高维数据的相似性度量方法之一。假设有两个向量A和B,它们的余弦相似度计算公式如下:
余弦相似度 = (A · B) / (||A|| * ||B||)
其中,A · B 是两个向量的点积,||A|| 和 ||B|| 分别是两个向量的范数(也就是它们的长度)。
余弦相似度的值范围在-1到1之间,越接近1表示两个向量越相似,越接近-1表示越不相似。 - 欧几里德距离(Euclidean Distance):
欧几里德距离是两个向量之间的直线距离。对于两个n维向量A和B,欧几里德距离计算公式如下:
欧几里德距离 = sqrt(Σ(Ai - Bi)^2),其中i从1到n
较小的欧几里德距离表示两个向量越相似。 - 曼哈顿距离(Manhattan Distance):
曼哈顿距离是两个向量之间的城市街区距离,也就是两个向量坐标差的绝对值的总和。对于两个n维向量A和B,曼哈顿距离计算公式如下:
曼哈顿距离 = Σ|Ai - Bi|,其中i从1到n
与欧几里德距离不同,曼哈顿距离更侧重于各个坐标的绝对差异。 - Jaccard相似性(Jaccard Similarity):
Jaccard相似性通常用于衡量两个集合的相似性,但也可以用于向量。对于两个向量A和B,Jaccard相似性计算公式如下:
Jaccard相似性 = (A ∩ B) / (A ∪ B)
其中A ∩ B表示A和B的交集,A ∪ B表示A和B的并集。
这些是常见的相似性度量方法之一,你可以根据你的具体需求选择其中之一。在某些情况下,可能需要结合多个度量方法来综合评估相似性。
内存管理
请看计算机内存管理
线程与进程的区别
进程和线程是操作系统中的重要概念,用于管理和执行计算机程序。它们在多任务处理中起着关键作用,允许计算机同时执行多个任务。
-
进程(Process):
- 进程是资源(CPU、内存等)分配的基本单位,具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个独立单位。
- 进程是操作系统中的一个独立的执行单位。它包含了程序代码、数据、堆栈、寄存器等信息,用于执行一个程序。
- 每个进程都有自己独立的内存空间,这意味着不同进程之间不能直接访问彼此的内存。这提供了隔离和安全性。
- 进程之间可以通过进程间通信(Inter-Process Communication,IPC)来交换数据和信息。常见的IPC方法包括管道、套接字、消息队列等。
- 一个操作系统可以同时运行多个进程,每个进程独立执行,互不干扰。
-
线程(Thread):
- 线程是进程的一个实体,是独立运行和独立调度的基本单位(CPU上真正运行的是线程)。线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。
- 线程是进程中的一个更小的执行单位,它共享相同的进程内存空间。一个进程可以包含多个线程。
- 线程可以看作是进程内的轻量级进程,它们共享进程的资源,如代码段、数据段和文件描述符等。
- 线程之间的通信更加容易,因为它们可以直接访问相同的内存空间。但这也增加了多线程编程的复杂性,因为需要谨慎处理共享数据以避免竞态条件和死锁等问题。
- 多线程可以提高程序的性能,因为它们可以并行执行任务,充分利用多核处理器。
区别:
- 进程是资源分配的基本单位;线程是程序执行的基本单位。
- 进程拥有自己的资源空间,每启动一个进程,系统就会为它分配地址空间;而线程与CPU资源分配无关,多个线程共享同一进程内的资源,使用相同的地址空间。
- 一个进程可以包含若干个线程。
优劣:
- 线程之间的通信更方便,同一进程下的线程共享全局变量、静态变量等数据,而进程之间的通信需要以通信的方式(Inter Process Communication,IPC)进行。不过如何处理好同步与互斥是编写多线程程序的难点。
- 线程的调度与切换比进程快很多,同时创建一个线程的开销也比进程要小很多。
- 但是多进程程序更健壮,多线程程序只要有一个线程死掉,整个进程也死掉了,而一个进程死掉并不会对另外一个进程造成影响,因为进程有自己独立的地址空间。
详细请看:进程与线程的一个简单解释 - 阮一峰的网络日志 (ruanyifeng.com)
c语言指针
深度优先和广度优先
定义:
深度优先搜索(DFS)是一种遍历或搜索树或图的算法。它从一个起始节点开始,先访问该节点,然后递归地访问该节点的子节点,再返回访问该节点的邻居节点。即每次都尽可能深的搜索树的分支。
广度优先搜索(BFS)也是一个用于遍历或搜索树或图的算法。但它的搜索顺序是先访问离起始节点最近的节点,然后按照由近及远的顺序依次访问和搜索节点的邻居。即先逐层访问节点。
总结一下两者的主要区别:
- 搜索顺序不同:DFS是深度方向搜索,BFS是广度方向搜索。
- 使用数据结构不同:DFS通常使用栈,BFS通常使用队列。
- DFS空间复杂度小,BFS时间复杂度小。DFS经常用来解决要深入到特定分支的问题;BFS更适合于找最短路径等问题。
- DFS中可能重复访问同一节点;BFS在访问完一个节点后不会再次访问。
使用原则
适合使用深度优先搜索DFS的场景:
- 解空间非常大,解稀疏且分布广泛,目的是快速找到解。DFS通过深入穷尽可能的路径来尽快找到解。
- 搜索的目标离起点很深,而我们想找最短路径。DFS可以快速到达目标。
- 需要回溯或遍历整个解空间,比如遍历树/图,枚举、排列组合等。DFS更适合这种全遍历。
适合使用广度优先搜索BFS的场景:
- 解空间中的解比较密集。BFS逐层遍历可以快速找到最优解。
- 目标离起点不远,适合用BFS一层一层搜索,找到最短路径。
- 需要知道某状态是否可达,如果可达则找到最短路径。BFS可以在搜索到目标后就结束。
- 解空间结构复杂,需要避免重复状态。BFS使用队列不重复访问。
- 需要按层 level 对图/树进行处理操作。
总结:
DFS适合快速找到可行解;BFS适合找到最优解、最短路径等。游戏和树/图搜索常用DFS;路径搜索和可达性分析常用BFS。需要全遍历时用DFS,需要按层处理用BFS。
举例:
对于找到一个人所有朋友的朋友这个问题,我们可以使用广度优先搜索算法(Breadth First Search, BFS)来解决。
具体思路是:
- 将该人作为起始节点,构建一个图结构,存储该人的所有直接朋友关系。
- 使用一个队列,先将该人入队。
- 当队列不为空时,重复以下操作:
(1) 出队一个人A
(2)遍历A的所有直接朋友,如果朋友不在已遍历的人集合中,就将其入队
(3)将A标记为已遍历 - 重复步骤3,直到队列为空,此时已遍历的人就是该人的朋友的朋友
- 返回已遍历人集合
这样通过BFS的层层推广,可以找到起始人的朋友的朋友,并且时间复杂度为O(n),是一个较优的解法。
BFS适合解决此类通过关系逐层扩散搜索的问题,可以有效找到所有符合条件的人。如果使用DFS,则可能会重复搜索同样的人,时间效率较低。
操作系统知识
操作系统的用户态和系统态
操作系统中的用户态和内核态是两个不同的执行模式或特权级别,用于管理计算机系统的资源和执行任务。它们的主要区别在于权限和资源访问的限制。
-
用户态(User Mode):
- 用户态是操作系统中较低特权级别的执行模式,通常用于运行普通应用程序和用户进程。
- 在用户态下,程序的权限受到限制,它们不能直接访问或修改操作系统的核心功能或硬件资源。
- 用户态的程序执行受到严格的限制,以确保它们不会意外地破坏系统的稳定性和安全性。
- 如果用户态的程序需要执行特权操作,例如访问硬件设备或执行系统级任务,它们必须通过系统调用(System Call)请求操作系统的帮助。操作系统会在必要时切换到内核态来执行这些请求。
-
内核态(Kernel Mode):
- 内核态是操作系统中较高特权级别的执行模式,通常用于执行操作系统内核的核心功能和管理硬件资源。
- 在内核态下,代码拥有更广泛的特权,可以直接访问和操作系统内核、硬件设备和系统资源。
- 内核态的代码负责执行关键的系统管理任务,如任务调度、内存管理、设备驱动程序和中断处理等。
- 由于内核态的代码具有更高的特权,因此必须谨慎编写和维护,以确保系统的安全性、稳定性和完整性。
在正常情况下,操作系统会在用户态和内核态之间进行切换,以确保系统的安全性和稳定性。当用户态的程序需要执行系统级任务时,它们会通过系统调用将控制权转交给内核态,内核态的代码执行所需的操作,然后再返回结果给用户态。这种切换通常由操作系统的内核自动管理,不需要用户干预。
总之,用户态和内核态是操作系统中的两个执行模式,用于区分普通应用程序和操作系统内核之间的权限和资源访问。这种分离有助于维护系统的稳定性、安全性和可维护性。
操作系统常识
- 在Linux系统中,因为某些原因造成了一些进程变成孤儿进程,那么这些孤儿进程会被
init
进程接管
代码题
题目: 时针和分针分别有4盏灯和6栈灯组成(二进制,灯亮为1,不亮为0),如11:59表示为“1011:111011”,给出亮的灯的盏数,求所有的时间可能,并按照时间顺序进行排列
解答:
由于时针上数字时0-11,比较简单,直接列出所有可能,然后用回溯法给出分针上的所有的可能
def backtracking(n,i,start,path,res):
# n 写的时候考虑了时分针上的量n为4或者6,i为实际亮灯数量,即n盏选i盏亮
# 结束条件,路径上的元素数量等于要选择的数量
if len(path)==i:
sums = 0
for ii in path[:]:
sums+=2**(n-1-ii)
res.append(sums)
return
for ii in range(start,n):
path.append(ii)
backtracking(n,i,start+1,path,res)
path.pop()
n = input() # 亮灯的数量
# 时针上数字对应的亮的灯的数量
dic = {0:0,1:1,2:1,3:2,4:1,5:2,6:2,7:3,8:1,9:2,10:2,11:3}
res = [] # 存放结果
for i in range(12):
if dic[i]>n:
break
if n-dic[i]>6:
break
res2 = []
backtracking(6,n-dic[i],0,path,res)
res2 = res2.sort()
for j in res2:
res.append(f"{i}:{j}")
print(res) # 报错
print('[' + ', '.join(res) + ']')
- 设a数组的长度为N,那么下面程序循环内交换数组元素的代码执行的时间复杂度最坏为?( )
for (int i = N - 1; i > 1; I--)
{
for (int j = 1; j < i; j++)
{
if (a[j] > a[j + 1])
{
temp = a[j + 1];
a[j + 1] = a[j];
a[j] = temp;
}
}
}
A.O(N)
B.O(N平方)
C.O(N立方)
D.O(Nlog2N)
-
下面哪个不是用来解决哈希表冲突的开放地址法?( )
线性补偿探测法
拉链探测法
线性探测法
随机探测法 -
在逻辑回归输出与目标对比的情况下,以下评估指标中哪一项不适用?( B )
A. 均方误差
B. 准确度
C. Logloss
D. AUC-ROC -
并称为国际上最有影响的三大统计软件是(B)。
0.SPSS
1.BMDP
2.RapidMiner
3.SAS
A. 仅0和3
B. 仅0,1,3
C. 全部 -
在图集合中发现一组公共子结构,这样的任务称为( D )。
A. 频繁子集挖掘
B. 频繁数据项挖掘
C. 频繁模式挖掘
D. 频繁子图挖掘 -
在输出层不能使用以下哪种激活函数来分类图像?( C )
A. sigmoid
B. Tanh
C. ReLU -
考虑某个具体问题时,你可能只有少量数据来解决这个问题。不过幸运的是你有一个类似问题已经预先训练好的神经网络。可以用下面哪种方法来利用这个预先训练好的网络?( )
A. 对每一层模型进行评估,选择其中的少数来用
B. 对新数据重新训练整个模型
C. 把除了最后一层外所有的层都冻住,重新训练最后一层
D. 只对最后几层进行调参(fine tune) -
马尔可夫性是指系统的下一个状态与当前状态__________,与上一个状态__________,与其它历史状态__________。(回答有关或无关)(答案用顿号分割,例如A、B、... )
-
考虑两队之间的足球比赛:队0和队1。假设65%的比赛队0胜出,剩余的比赛队1获胜。队0获胜的比赛中只有30%是在队1的主场,而队1取胜的比赛中75%是主场获胜。如果下一场比赛在队1的主场进行队1获胜的概率为__________。(结果保留4位小数)
-
三寡头市场需求函数P=100-Q,其中P是价格,Q是三个厂商的产量之和,已知三个厂商都有常数边际成本2而无固定成本。如果厂商1和2先同时决定产量,厂商3再根据1和2的产量决策,则厂商1、2、3的产量分别是__________、、。(答案用顿号分割,例如A、B、...,分式写成A/B的形式 )
-
某种产品中,合格品率为85%。一个合格品被检查成次品的概率是10%,一个次品被检查成合格品的概率为5%。问题:求一个被检查成合格品的产品确实为合格品的概率( )。
0.915
0.85
0.75
0.99 -
求最短路径的FLOYD算法的时间复杂度为( )。
O(n^2)
O(n+e)
O(n^3)
O(n) -
设用一个复杂回归模型拟合一个数据集,使用带固定参数lambda的Ridge回归来减小它的复杂度,下列哪项描述了偏差和方差与lambda的关系?( )
- 对于非常小的lambda,偏差很小,方差很小
- 对于非常小的lambda,偏差很大,方差很大
- 对于非常小的lambda,偏差很大,方差很小
- 对于非常小的lambda,偏差很小,方差很大
前向算法
Baum-Welch算法
后向算法
维特比算法
映射数据到新的空间
特征提取
特征构造
特征修改
- 在抽样方法中,当合适的样本容量很难确定时,可以使用的抽样方法是( )。
分层抽样
有放回的简单随机抽样
渐进抽样
无放回的简单随机抽样 - 将Sigmoid激活函数改为ReLu,将有助于克服梯度消失问题。这种说法是否正确?( )
- 正确✅
- 错误
- 考虑两队之间的足球比赛:队0和队1。假设65%的比赛队0胜出,剩余的比赛队1获胜。队0获胜的比赛中只有30%是在队1的主场,而队1取胜的比赛中75%是主场获胜。如果下一场比赛在队1的主场进行队1获胜的概率为__________。(结果保留4位小数)
- 在一个10阶的B-树上,每个树根结点中所含的关键字数目最多允许为__________个,最少允许为__________个。
- 理论上训练完美的GANs,对于每个样本z,损失函数中D(G(z))接近于__________(填数值),其中D为判别器,G为生成器。(结果用分数表示,如A/B)