当前位置：首页 > news >正文

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

news 2025/11/22 12:20:25

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

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;}
};

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

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送入后续全连接层继续做分类（具体是哪一类别）和回归。

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

12. c++怎么处理异常

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

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

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

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

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

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

19. 联想编程题：

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

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

查看全文