0818-0824面试题目和复习整理

根据面试问的问题整理一下

1. 并查集

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构// 并查集初始化
void init() {for (int i = 0; i < n; ++i) {father[i] = i;}
}
// 并查集里寻根的过程
int find(int u) {return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}// 将v->u 这条边加入并查集
void join(int u, int v) {u = find(u); // 寻找u的根v = find(v); // 寻找v的根if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回father[v] = u;
}

2. 梯度下降法和二分法求一个函数

对于梯度下降法，x应该考虑实际函数来做，而且lr不能设置的太大，会跳过这个解，二分法最好还是用while来写吧，我用的递归，很奇怪

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int m = 10000;float e = 0.0001;
float f(float x) {return exp(x) + pow(x, 3) - 5;
}
float grad(float x) {return exp(x) + 3 * x * x;
}
float func1(float left, float right) {float mid = (left + right) / 2;if (f(mid) > e) {return func1(mid, right);}else if (f(mid) < -e) {return func1(left, mid);}else return mid;
}
float func2(float x) {int epoch = 10000;float step = 0.0001;for (int i = 0; i < epoch; i++) {if (f(x) > -e && f(x) < e) {return x;}x = x - step * grad(x);cout << x << endl;}return x;
}
int main()
{float x = 3;cout << func1(-10,10) << endl;return 0;
}

3. 为什么分类模型用交叉熵损失函数，而不用MSE

1. MSE是均方误差损失函数，表示的是m个样本的均值，网络模型用它来预测，就是为了拟合实际的值与预测值之间的差。得到的是一个值。

2. 分类问题一般是需要一系列的激活函数，将预测值映射到0-1之间

3. 分类问题使用交叉熵，Loss下降的更快。

4. 使用交叉熵是凸优化，MSE是非凸优化

4. maxpooling的反向传播

5. scaled product attention

6. 链表逆序

我怎么都想不出来链表逆序，烦死了

看模板思路吧: 是我想的太复杂了，绕来绕去其实每次只要维护三个节点，把从左到右的连接改成从右到左的就行了，然后三个节点都往后移动一次。

    ListNode * reverse(ListNode * node){ListNode * pre = nullptr, * cur = node;while(cur!=nullptr){ListNode * nextt = cur->next;cur->next = pre;pre = cur;cur = nextt;}return pre;}

7. K个一组反转链表

    ListNode * reverse(ListNode * node){ListNode * pre = nullptr, * cur = node;while(cur!=nullptr){ListNode * nextt = cur->next;cur->next = pre;pre = cur;cur = nextt;}return pre;}ListNode * findtail(ListNode * node){while(node != nullptr && node->next != nullptr){node = node->next;}return node;}ListNode* reverseKGroup(ListNode* head, int k) {if(k == 1) return head;vector<ListNode *> heads;ListNode * cur = head;heads.push_back(head);int idx = 1;while(cur != nullptr){if(idx % k == 0){ListNode * t = cur->next;heads.push_back(t);cur -> next = nullptr;cur = t;}else{cur = cur ->next;}idx++;}for(auto head:heads){while(head!=nullptr){cout<<head->val<<" ";head = head->next;}cout<<endl;}// 翻转链表ListNode * res = new ListNode(0);ListNode * pre = res;if((idx-1)%k == 0){for(ListNode* node : heads){node = reverse(node);ListNode * tail = findtail(node);pre -> next = node;pre = tail;}}else{for(int i =0;i<heads.size()-1;i++){ListNode * node = reverse(heads[i]);ListNode * tail = findtail(node);pre -> next = node;pre = tail;}pre->next = heads[heads.size()-1];}return res->next;}

思路倒是不难想，就是先分组再逆序再组合起来，但是好麻烦好容易出错。。

合起来的时候要知道每个子链表的头尾，我是根据头找尾，但是应该可以在reverse的时候就把尾记录下来，这样可以直接得到头尾

还有，每次通过while(x->next != nullptr)的时候要加上while(x!=nullptr && x->next != nullptr)

8. python写AUC

def calculate_AUC(y_pred,y_true):sorted_indices = np.argsort(y_pred)sorted_y_true = y_true[sorted_indices]sorted_y_pred = y_pred[sorted_indices]# 计算真阳性率和假阳性率tpr = []  # 真阳性率fpr = []  # 假阳性率total_positive = np.sum(sorted_y_true)total_negative = len(sorted_y_true) - total_positivecurrent_positive = 0current_negative = 0for i in range(len(sorted_y_true)):if sorted_y_true[i] == 1:current_positive += 1else:current_negative += 1tpr.append(current_positive / total_positive)fpr.append(current_negative / total_negative)# 计算AUCauc = np.trapz(tpr, fpr)return auc

记得排序并根据排序返回索引的方式：np.argsort()

记得求积分的方法：np.trapz()

AUC的时间复杂度？

9. 全排列公式

关键在于去重，去重之前我都会写，唉，还是要记一下思路

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking (vector<int>& nums, vector<bool>& used) {// 此时说明找到了一组if (path.size() == nums.size()) {result.push_back(path);return;}for (int i = 0; i < nums.size(); i++) {// used[i - 1] == true，说明同一树枝nums[i - 1]使用过// used[i - 1] == false，说明同一树层nums[i - 1]使用过// 如果同一树层nums[i - 1]使用过则直接跳过if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;}if (used[i] == false) {used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;}}}
public:vector<vector<int>> permuteUnique(vector<int>& nums) {result.clear();path.clear();sort(nums.begin(), nums.end()); // 排序vector<bool> used(nums.size(), false);backtracking(nums, used);return result;}
};

去重的思路是，给数组1 1 2 2，如果第一个1没选，就不能先选第二个1，也就是每次选的时候，如果这个数和上一个数相等，就得判断上一个数选没选过，没选过就不能选这个数。

去重之前要先对nums排个序。

全排列的时间复杂度是多少?

排序复杂度是O（nlogn），

DFS 函数探索所有可能的排列。在最坏情况下，这涉及访问每个排列一次。
对于 n 个不同的元素，有 n! 种排列。
由于 nums 可能包含重复元素，唯一排列的数量可能小于 n!。不过，复杂度主要受阶乘项控制，所以生成排列的复杂度仍然是 𝑂(𝑛×𝑛!)

也就是说，全排列一共有𝑛!个可能，每次都需要n来取出。所以总的复杂度是𝑛×𝑛!

10. FM的公式，如何优化的

用pytorch写：

import numpy as np
import torch.nn as nn
import torch
class FM(nn.Module):def __init__(self,input_size,k):super(FM, self).__init__()self.linear = nn.Linear(input_size, 1)self.v = nn.Parameter(torch.randn(input_size,k))def forward(self,x):linear_part = self.linear(x)interaction_part = 0.5 * torch.sum(torch.pow(x@(self.v),2) - pow(x,2)@pow(self.v,2))return linear_part + interaction_part

11. 颜色分类

数组只包含0,1,2三种，排序

这题其实感觉在多分类里能用到，比如0101001这种排序成0001，方便求AUC

没想到这么简单的做法，我一直在纠结怎么交换，结果一个ptr就能解决

    void sortColors(vector<int>& nums) {// 对0排序int ptr = 0;int n = nums.size();for(int i =0;i<n;i++){if(nums[i] == 0){swap(nums[ptr],nums[i]);ptr++;}}for(int i =0;i<n;i++){if(nums[i] == 1){swap(nums[ptr],nums[i]);ptr++;}}}

12. 分割回文串

只要知道这道题是回溯就行了，和全排列一样的思路

    bool huiwen(string s){int i = 0, j = s.size()-1;while(i<j){if(s[i] != s[j]) return false;i++, j--;}return true;}vector<vector<string>> res;vector<string> tmp;void dfs(int begin,string s){if(begin == s.size()){res.push_back(tmp);}for(int i = begin;i<= s.size()-1;i++){if(huiwen(s.substr(begin,i-begin+1))){tmp.push_back(s.substr(begin,i-begin+1));dfs(i+1,s);tmp.erase(tmp.end()-1);}}}vector<vector<string>> partition(string s) {dfs(0,s);return res;}

13. RCNN、FastRCNN、FasterRCNN

这三个都是针对目标检测的网络

RCNN大致步骤：先提取proposal，然后将proposal输入CNN提取特征，使用SVM分类，最后做bbox reg。缺点：速度。提取proposal的时候计算机进行大量重复计算

Fast改进：ROI pooling

在fast中，作者将输入变为一整张图片，通过ROI再进行特征选择。

并且将bbox reg和区域分类都加入网络变成了multi-task

Fast将RCNN每一个框都要单独进CNN入这一大缺点改进，提升了速度。

尽管fast极大地提高了速度，但是筛选特征框还是需要花费大量的时间，那么有没有办法进一步提高选择框的速度？

使用 RPN（之前都是使用特定的算法选择）

FasterRCNN用了RPN来加快。

RPN（Region Proposal Network）。即区域候选网络，该网络替代了之前RCNN版本的Selective Search，用于生成候选框。这里任务有两部分，一个是分类：判断所有预设anchor是属于positive还是negative（即anchor内是否有目标，二分类）；还有一个bounding box regression：修正anchors得到较为准确的proposals。因此，RPN网络相当于提前做了一部分检测，即判断是否有目标（具体什么类别这里不判），以及修正anchor使框的更准一些。

RoI Pooling。即兴趣域池化（SPP net中的空间金字塔池化），用于收集RPN生成的proposals（每个框的坐标），并从（1）中的feature maps中提取出来（从对应位置扣出来），生成proposals feature maps送入后续全连接层继续做分类（具体是哪一类别）和回归。

14.MMOE是如何对多目标进行预估的，如果单独把两个模型直接预测得到目标，和用多目标模型有什么区别？

MMOE的好处在于共享专家网络，每个任务（点击率，点赞率）都共享整个专家网络。这些网络在多任务之间共享，但是不同任务考虑到对这些网络不同的加权，所以就能够选择最相关的专家。

每个任务还有一个专门的塔结构（在专家结果之后），进一步处理。

多目标模型比起单独模型的好处在于：

（1）参数共享：多目标模型共享底层网络的参数，可以利用不同任务之间的关联性。单目标是每个任务训练一个网络，就会浪费，类似集成学习的bagging，利用多个网络做加权求和的结果肯定比单个网络直接得到的结果好。

（2）效率更高，在有限数据下，共享信息能够提升预测性能。

15. c++怎么处理异常

用try,catch,throw处理异常。

#include<iostream>
using namespace std;int main(){try{throw runtime_error("An error occurred!");}catch(const std::runtime_error& e){cout<<"";}
}

16. 给数组a1,a2,a3,b1,b2,b3 怎么不使用额外空间变成a1,b1,a2,b2,a3,b3

可以用插入排序的思想！我真傻

从b1开始，把b1插入到a1后，也就是a2到结尾全部往右挪一格，每次都是，这样复杂度倒是高了一点。

14.CT值表示什么意义，范围是多少，CT值为0代表什么

CT值叫做Hounsfield，HU，表示计算机断层扫描中测量的组织密度。

不同组织吸收X射线的能力不同，CT值反映了这种吸收差异。

水的CT值为0，空气为-1000，所以CT值为0反映了该区域密度和水一样。

15. 双向链表和数组的插入\访问时间复杂度，双向链表如何插入一个数

数组的访问是O1，插入是On，（在结尾插入是O1）

双向链表的访问是On，插入是O1（已知节点插入是1，未知是n）

16 pytorch如何反向传播，如果一个层被冻结了，上一层的梯度如何传播?

如果该层被冻结，那么它的输出仍然会参与计算，梯度会通过该层传递到上一层。但冻结层的参数不会更新。

17. tensorRT是如何部署，加载模型并预测的？

TensorRT的执行流程为：1.导出网络定义以及相关权重（onnx）；2.解析网络定义以及相关权重；3.根据显卡算子构造出最优执行计划；4.将执行计划序列化存储；5.反序列化执行计划；6.进行推理

具体我的做法是把pytorch保存下来的模型.pth转成onnx的形式，再转成tensorRT的格式，也就是根据显卡算子进行序列化存储。这一步是根据硬件决定的，换了硬件就没办法再保存了。

序列化阶段：根据ONNX描述的模型结构和权重、当前的硬件环境生成对应的执行计划，并且序列化为xxx.engine文件持久化保存。这一步时间比较长。

一般会开启float16精度模式，压缩模型，加快推理速度。不过这一步精度会有损失。

18. 我的去噪模型的精度是如何衡量的，用什么指标，有什么其他指标，他们分别有什么缺陷

用到的指标有：MSE、SSIM、PSNR、梯度指标

PSNR和MSE的问题在于指标是局部特征的，每个像素的差只与当前像素值有关。这种计算差异的方式仅仅将图像看成了一个个孤立的像素点，而忽略了图像内容所包含的一些视觉特征，特别是图像的局部结构信息。而图像质量的好坏极大程度上是一个主观感受，其中结构信息对人主观感受的影响非常之大。

SSIM的区别在于取的是区域平均值。

LPIPS 使用预训练的深度网络（如 VGG、AlexNet）来提取图像特征，然后计算这些特征之间的距离，以评估图像之间的感知相似度。

tPSNR用这一帧和上一帧的PSNR差异。

19. 联想编程题：

给一个字符串，里面是0-9之间的数字。对字符串进行任意分割，看每个子串（连续的）是否能被4整除，输出所有能整除的子串的个数。（前导0也算，04和4算两个）

我只会用for套for，只过了45%，感觉dp能做，但是没写出来