记录秋招。。。

旷视一面（2022.08.12）

softmax，交叉熵loss实现

$softmax=\frac{e^{z_i}}{\sum_{j=1}^Ce^{z_j}}$

$L_{CE}=\frac{1}{N}\sum_{i=1}^{N}-log(\frac{e^{z_i}}{\sum_{j=1}^Ce^{z_j}})$

import numpy as np
import torch
import torch.nn.functional as Fdef softmax(logits):logits_exp = torch.exp(logits)logits_softmax = logits_exp / torch.sum(logits_exp, dim=1, keepdims=True)return logits_softmaxdef cross_entropy(logits_softmax, label):log_res = torch.log(logits_softmax)one_hot = torch.zeros_like(logits_softmax)one_hot.scatter_(1,label.view(-1, 1),1)loss = -torch.sum(log_res*one_hot, dim=1).mean()return loss# softmax
logits=torch.randn([2,5]) # B x C
label=torch.tensor([0,3])
logits_softmax=softmax(logits)
print(logits_softmax)
print(F.softmax(logits,dim=1)) # 验证# 预测的值
y_pred = torch.argmax(logits_softmax, dim=1)
print(y_pred)# cross_entropy
print(cross_entropy(logits_softmax, label))
print(F.cross_entropy(logits, label))
'''
输出
tensor([[0.1391, 0.1638, 0.0294, 0.4314, 0.2363],[0.2304, 0.2246, 0.3404, 0.0679, 0.1367]])
tensor([[0.1391, 0.1638, 0.0294, 0.4314, 0.2363],[0.2304, 0.2246, 0.3404, 0.0679, 0.1367]])
tensor([3, 2])
tensor(2.3307)
tensor(2.3307)
'''

【补充】计算IOU

def compute_iou(box1, box2):'''box 0,1,2,3: x1,y1,x2,y2'''area1 = (box1[2]-box1[0]) * (box1[3]-box1[1])area2 = (box2[2]-box2[0]) * (box2[3]-box2[1])area_sum = area1 + area2x1=max(box1[0], box2[0])y1=max(box1[1], box2[1])x2=min(box1[2], box2[2])y2=min(box1[3], box2[3])if x1 >= x2 or y1 >= y2:return 0area_jiao = (x2-x1) * (y2-y1)print(area_sum, area_jiao)iou = area_jiao / (area_sum - area_jiao)return ioubox1=torch.tensor([1,3,4,5]).float()
box2=torch.tensor([3,4,6,8]).float()
print(compute_iou(box1, box2))
'''
输出
tensor(18.) tensor(1.)
tensor(0.0588)
'''

【补充】计算NMS

def NMS(boxes, scores, thresh=0.03):sorted_scores, idx = torch.sort(scores, descending=True)sorted_boxes = boxes[idx]result_boxes = []while len(sorted_boxes) > 1:box=sorted_boxes[0]result_boxes.append(box)sorted_boxes = sorted_boxes[1:]saved_idx = []for i, item in enumerate(sorted_boxes):if(compute_iou(box, item)<thresh):saved_idx.append(i)sorted_boxes = sorted_boxes[saved_idx]if len(sorted_boxes)> 0:result_boxes.append(sorted_boxes[0])return result_boxesbox0 = torch.tensor([100,100,200,200]).float()
box1=torch.tensor([1,3,4,5]).float()
box2=torch.tensor([3,4,6,8]).float()
scores = torch.tensor([0.5, 0.8, 0.9])boxes = []
boxes.append(box0)
boxes.append(box1)
boxes.append(box2)
boxes = torch.cat(boxes, dim=0).reshape(3,-1)
NMS(boxes, scores)
'''
输出
[tensor([3., 4., 6., 8.]), tensor([100., 100., 200., 200.])]
'''

2. 反转链表

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N=505;struct ListNode{int val;ListNode *next;ListNode(int x): val(x), next(NULL) {}
};void print(ListNode *p){if(p!=NULL){printf("%d ", p->val);print(p->next);}
}ListNode *reverse_list(ListNode *root){ListNode *pre=NULL;ListNode *cur=root;while(cur!=NULL){ListNode *nex=cur->next;cur->next=pre;pre=cur;cur=nex;}return pre;
}int main(){int n,a;scanf("%d",&n);ListNode *head=new ListNode(-1);ListNode *p=head;for(int i=0;i<n;i++){scanf("%d",&a);ListNode *now=new ListNode(a);p->next=now;p=p->next;}print(head->next);ListNode *rev_head=reverse_list(head->next);printf("\n");print(rev_head);
}

旷视二面（2022.08.12）

长尾识别中Decoupling方法为什么有效
人脸loss中为什么||W||=1了，但是head classes权重的模长还是较长
大数定律。。。

挂。。。

快手一面（2022.08.18）

最长递增子序列leetcode300

class Solution {
public:int dp[2505];int lengthOfLIS(vector<int>& nums) {int n=nums.size();dp[0]=1;int ans=dp[0];for(int i=1;i<n;i++){dp[i]=1;for(int j=0;j<i;j++){if(nums[j]<nums[i]){dp[i]=max(dp[i], dp[j]+1);}}ans=max(dp[i], ans);}return ans;}
};

快手二面（2022.09.13）

问项目问的很详细，第1道题最小k个数，我先讲的思路：单边快排(O(n))、优先队列(O(nlogk))、插入排序(O(nk))，这三个思路面试官都说让我别着急写，然后给我出了第2题。。。此时我还以为我第一题所有思路不对。。。就直接开始写第2题了。。。大怨种说的是我吧。。。后续又提问了知识点和场景题，面了大概1.5h，累虚脱了。。。

1143. 最长公共子序列

class Solution {
public:int Partition(vector<int>&arr, int b, int e){if(b>=e)return b;int x=arr[b];int i=b,j=e+1;while(1){while(arr[++i]<x&&i<e);while(arr[--j]>x);if(i>=j)break;swap(arr[i], arr[j]);}arr[b]=arr[j];arr[j]=x;return j;}void quick_sort(vector<int>&arr, int b, int e, int k){if(b>=e)return ;int pos=Partition(arr, b, e);if(k<=pos){quick_sort(arr, b, pos-1, k);}else{quick_sort(arr, b, pos-1, k);quick_sort(arr, pos+1, e, k);}}vector<int> smallestK(vector<int>& arr, int k) {vector<int>ans;if(arr.size()==0)return ans;if(k==0)return ans;quick_sort(arr, 0, arr.size()-1, k-1);for(int i=0;i<k;i++){ans.push_back(arr[i]);}return ans;}
};

最长公共子序列的值

这里开个数组记录状态路径，然后回推回去返回最长公共子序列的值

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int n=text1.length();int m=text2.length();int dp[n+1][m+1];memset(dp, 0, sizeof(dp));int pre[n+1][m+1];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(text1[i-1]==text2[j-1]){dp[i][j]=dp[i-1][j-1]+1;pre[i][j]=1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);if(dp[i][j]==dp[i-1][j]){pre[i][j]=2;}else{pre[i][j]=3;}}}}int i=n,j=m;string ans="";while(i>=1&&j>=1){if(text1[i-1]==text2[j-1]){string t;t.push_back(text1[i-1]);ans=t+ans;}if(pre[i][j]==1){i--;j--;}else if(pre[i][j]==2){i--;}else j--;}cout<<ans<<endl;return dp[n][m];}
};

超参数一面

剑指 Offer II 078. 合并排序链表

方法一：优先队列，把链表的每个元素看出单个元素送到优先队列中

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:struct cmp{bool operator()(ListNode *a, ListNode *b){return a->val > b->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, cmp>pq;int n=lists.size();for(int i=0;i<n;i++){if(lists[i])pq.push(lists[i]);}ListNode *res=new ListNode(-1);ListNode *p=res;while(!pq.empty()){ListNode *tmp=pq.top();pq.pop();p->next=tmp;p=p->next;if(tmp->next){pq.push(tmp->next);}}return res->next;}
};

方法二：归并排序

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* Merge(ListNode *left, ListNode *right){if(left==NULL)return right;if(right==NULL)return left;ListNode *ans=new ListNode(-1);ListNode *p=ans;while(left&&right){if(left->val<=right->val){p->next=left;left=left->next;}else{p->next=right;right=right->next;}p=p->next;}if(left)p->next=left;if(right)p->next=right;return ans->next;}ListNode* merge_sort(vector<ListNode*>lists, int b, int e){if(b==e)return lists[b];if(b>e)return NULL;int m=(b+e)/2;ListNode *left=merge_sort(lists, b, m);ListNode *right=merge_sort(lists, m+1, e);return Merge(left, right);}ListNode* mergeKLists(vector<ListNode*>& lists) {return merge_sort(lists, 0, lists.size()-1);}
};

剑指 Offer II 016. 不含重复字符的最长子字符串

class Solution {
public:unordered_map<char,int>pos;int lengthOfLongestSubstring(string s) {int n=s.length();int left=0;int ans=0;for(int i=0;i<n;i++){if(pos[s[i]]-1>=left){//交叉重复ans=max(ans, i-left);left=pos[s[i]];}pos[s[i]]=i+1;}ans=max(ans, n-left);return ans;}
};

超参数二面

pytorch用的什么并行训练方法：5种pytorch并行训练方法
训练用的训练集大小：

调用randint4（随机生成0-3），构造randint5（随机生成0-4），要求等概率

面试官的提示：5个人掷骰子决定谁去拿快递，那么掷到1-5就对应的人去，掷到6就再来一次

那么，这里可以看成调用2次randint4函数分别得到x，y，那么4x+y的范围是0-15（其实也就是x有4种，4x+y可以构造成等概率即两两不相等的16种）

由于16种结果是等概率的，我们只要前15种，如果是最后1种的话，就再来一次。

则调用randint4中rand函数的期望是：2*（1+1/16+1/16^2+1/16^3...）=2*(1+1/15)

此处感谢瓜佬的思路。。。

挂。。。

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N=100005;
const ll mod=1e9+7;
int randint4(){return rand()%4;
}int randint5(){int x=randint4();int y=randint4();int sum=4*x+y;if(sum+1!=16){return (sum+1)%5;}else{return randint5();}
}int main(){for(int i=1;i<=10;i++){cout<<randint5()<<endl;}
}

阿里一面（2022.09.14）

大数加法

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
typedef pair<int,int> P;const int INF=0x3f3f3f3f;
const int N=3005;
int n,cnt=0;void add(string s1, string s2, int flag){int n=s1.length();int m=s2.length();int len=max(n,m);int nums[len+5];memset(nums,0,sizeof(nums));for(int i=0;i<len;i++){int a=s1[i]-'0';int b=s2[i]-'0';nums[i]+=(a+b);nums[i+1]+=nums[i]/10;nums[i]%=10;}int k;if(nums[len]!=0){k=len;}else k=len-1;if(flag)printf("-");for(int i=k;i>=0;i--){printf("%d",nums[i]);}printf("\n");
}void sub_solve(string s1, string s2){int len=s1.length();reverse(s1.begin(),s1.end());reverse(s2.begin(),s2.end());int nums[len+1];memset(nums,0,sizeof(nums));for(int i=0;i<len;i++){int a=s1[i]-'0';int b;if(i<s2.length()){b=s2[i]-'0';}else{b=0;}if(a>=b){nums[i]+=a-b;}else{nums[i]=10+a-b;nums[i+1]--;}}for(int i=len-1;i>=0;i--){if(nums[i]==0)len--;else break;}for(int i=len-1;i>=0;i--){printf("%d",nums[i]);}printf("\n");
}void sub(string s1, string s2){//s1-s2int len1=s1.length();int len2=s2.length();int flag=0;if(len1>len2){flag=1;}else if(len1<len2){flag=2;}else{for(int i=0;i<len1;i++){if(s1[i]>s2[i]){flag=1;break;}else if(s1[i]<s2[i]){flag=2;break;}}}if(flag==0){printf("0\n");}else if(flag==1){sub_solve(s1,s2);}else{printf("-");sub_solve(s2,s1);}
}int main(){string s1,s2;cin>>s1>>s2;if(s1[0]!='-'&&s2[0]!='-'){reverse(s1.begin(),s1.end());reverse(s2.begin(),s2.end());add(s1,s2,0);}else if(s1[0]=='-'&&s2[0]=='-'){s1=s1.substr(1);s2=s2.substr(1);reverse(s1.begin(),s1.end());reverse(s2.begin(),s2.end());add(s1,s2,1);}else{if(s1[0]=='-'){s1=s1.substr(1);sub(s2,s1);}else{s2=s2.substr(1);sub(s1,s2);}}
}

一道leetcode题，字符+数字，字符重复数字的，问第k个字符是什么，暴力模拟即可

阿里二面（2022.09.16）

电话面试，没考算法，方向不匹配，面完就挂了

微软一面（2022.09.19）

面试官小哥哥真的是我面过的最有礼貌最谦虚的，夸夸

剑指 Offer II 119. 最长连续序列

需要考虑出现重复的情况

class Solution {
public:int longestConsecutive(vector<int>& nums) {int n=nums.size();if(n==0||n==1)return n;sort(nums.begin(), nums.end());int left=0,cnt=1,maxx=1;for(int i=1;i<n;i++){if(nums[i]==nums[i-1])continue;if(nums[i]-1==nums[i-1]){cnt++;}else{if(maxx<cnt){maxx=cnt;left=i-cnt;}cnt=1;}}if(cnt>maxx){maxx=cnt;left=n-cnt;}return maxx;}
};