• 菜鸡的秋招升级打怪之旅

    记录秋招。。。

    旷视一面（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}})

    1. import numpy as np
    2. import torch
    3. import torch.nn.functional as F
    4.  
    5. def softmax(logits):
    6.     logits_exp = torch.exp(logits)
    7.     logits_softmax = logits_exp / torch.sum(logits_exp, dim=1, keepdims=True)
    8.     return logits_softmax
    9.  
    10. def cross_entropy(logits_softmax, label):
    11.     log_res = torch.log(logits_softmax)
    12.     one_hot = torch.zeros_like(logits_softmax)
    13.     one_hot.scatter_(1,label.view(-1, 1),1)
    14.     loss = -torch.sum(log_res*one_hot, dim=1).mean()
    15.     return loss
    16.  
    17. # softmax
    18. logits=torch.randn([2,5]) # B x C
    19. label=torch.tensor([0,3])
    20. logits_softmax=softmax(logits)
    21. print(logits_softmax)
    22. print(F.softmax(logits,dim=1)) # 验证
    23.  
    24. # 预测的值
    25. y_pred = torch.argmax(logits_softmax, dim=1)
    26. print(y_pred)
    27.  
    28. # cross_entropy
    29. print(cross_entropy(logits_softmax, label))
    30. print(F.cross_entropy(logits, label))
    31. '''
    32. 输出
    33. tensor([[0.1391, 0.1638, 0.0294, 0.4314, 0.2363],
    34.         [0.2304, 0.2246, 0.3404, 0.0679, 0.1367]])
    35. tensor([[0.1391, 0.1638, 0.0294, 0.4314, 0.2363],
    36.         [0.2304, 0.2246, 0.3404, 0.0679, 0.1367]])
    37. tensor([3, 2])
    38. tensor(2.3307)
    39. tensor(2.3307)
    40. '''
    • 【补充】计算IOU
    1. def compute_iou(box1, box2):
    2.     '''
    3.     box 0,1,2,3: x1,y1,x2,y2
    4.     '''
    5.     area1 = (box1[2]-box1[0]) * (box1[3]-box1[1])
    6.     area2 = (box2[2]-box2[0]) * (box2[3]-box2[1])
    7.     
    8.     area_sum = area1 + area2
    9.     x1=max(box1[0], box2[0])
    10.     y1=max(box1[1], box2[1])
    11.     
    12.     x2=min(box1[2], box2[2])
    13.     y2=min(box1[3], box2[3])
    14.     
    15.     if x1 >= x2 or y1 >= y2:
    16.         return 0
    17.     
    18.     area_jiao = (x2-x1) * (y2-y1)
    19.     print(area_sum, area_jiao)
    20.     iou = area_jiao / (area_sum - area_jiao)
    21.     return iou
    22.     
    23. box1=torch.tensor([1,3,4,5]).float()
    24. box2=torch.tensor([3,4,6,8]).float()
    25. print(compute_iou(box1, box2))
    26. '''
    27. 输出
    28. tensor(18.) tensor(1.)
    29. tensor(0.0588)
    30. '''
    • 【补充】计算NMS
    1. def NMS(boxes, scores, thresh=0.03):
    2.     sorted_scores, idx = torch.sort(scores, descending=True)
    3.     sorted_boxes = boxes[idx]
    4.     result_boxes = []
    5.     
    6.     while len(sorted_boxes) > 1:
    7.         box=sorted_boxes[0]
    8.         result_boxes.append(box)
    9.         
    10.         sorted_boxes = sorted_boxes[1:]
    11.         saved_idx = []
    12.         for i, item in enumerate(sorted_boxes):
    13.             if(compute_iou(box, item)<thresh):
    14.                 saved_idx.append(i)
    15.         sorted_boxes = sorted_boxes[saved_idx]
    16.     if len(sorted_boxes)> 0:
    17.         result_boxes.append(sorted_boxes[0])
    18.     return result_boxes
    19.  
    20. box0 = torch.tensor([100,100,200,200]).float()
    21. box1=torch.tensor([1,3,4,5]).float()
    22. box2=torch.tensor([3,4,6,8]).float()
    23. scores = torch.tensor([0.5, 0.8, 0.9])
    24.  
    25. boxes = []
    26. boxes.append(box0)
    27. boxes.append(box1)
    28. boxes.append(box2)
    29. boxes = torch.cat(boxes, dim=0).reshape(3,-1)
    30. NMS(boxes, scores)
    31. '''
    32. 输出
    33. [tensor([3., 4., 6., 8.]), tensor([100., 100., 200., 200.])]
    34. '''

    2. 反转链表

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. typedef long long ll;
    4. typedef pair<int,int> P;
    5. const int N=505;
    6.  
    7. struct ListNode{
    8.     int val;
    9.     ListNode *next;
    10.     ListNode(int x): val(x), next(NULL) {}
    11. };
    12.  
    13. void print(ListNode *p){
    14.     if(p!=NULL){
    15.         printf("%d ", p->val);
    16.         print(p->next);
    17.     }
    18. }
    19.  
    20. ListNode *reverse_list(ListNode *root){
    21.     ListNode *pre=NULL;
    22.     ListNode *cur=root;
    23.     while(cur!=NULL){
    24.         ListNode *nex=cur->next;
    25.         cur->next=pre;
    26.         pre=cur;
    27.         cur=nex;
    28.     }
    29.     return pre;
    30. }
    31.  
    32. int main(){
    33.     int n,a;
    34.     scanf("%d",&n);
    35.     ListNode *head=new ListNode(-1);
    36.     ListNode *p=head;
    37.     for(int i=0;i<n;i++){
    38.         scanf("%d",&a);
    39.         ListNode *now=new ListNode(a);
    40.         p->next=now;
    41.         p=p->next;
    42.     }
    43.     print(head->next);
    44.     ListNode *rev_head=reverse_list(head->next);
    45.     printf("\n");
    46.     print(rev_head);
    47. }

    旷视二面（2022.08.12）

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

    挂。。。

    快手一面（2022.08.18）

    1. class Solution {
    2. public:
    3.     int dp[2505];
    4.     int lengthOfLIS(vector<int>& nums) {
    5.         int n=nums.size();
    6.         dp[0]=1;
    7.         int ans=dp[0];
    8.         for(int i=1;i
    9.             dp[i]=1;
    10.             for(int j=0;j
    11.                 if(nums[j]
    12.                     dp[i]=max(dp[i], dp[j]+1);
    13.                 }
    14.             }
    15.             ans=max(dp[i], ans);
    16.         }
    17.         return ans;
    18.     }
    19. };

    快手二面（2022.09.13）

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

    1. class Solution {
    2. public:
    3.     int Partition(vector<int>&arr, int b, int e){
    4.         if(b>=e)return b;
    5.         int x=arr[b];
    6.         int i=b,j=e+1;
    7.         while(1){
    8.             while(arr[++i]
    9.             while(arr[--j]>x);
    10.             if(i>=j)break;
    11.             swap(arr[i], arr[j]);
    12.         }
    13.         arr[b]=arr[j];
    14.         arr[j]=x;
    15.         return j;
    16.     }
    17.     void quick_sort(vector<int>&arr, int b, int e, int k){
    18.         if(b>=e)return ;
    19.         int pos=Partition(arr, b, e);
    20.         if(k<=pos){
    21.             quick_sort(arr, b, pos-1, k);
    22.         }
    23.         else{
    24.             quick_sort(arr, b, pos-1, k);
    25.             quick_sort(arr, pos+1, e, k);
    26.         }
    27.     }
    28.     vector<int> smallestK(vector<int>& arr, int k) {
    29.         vector<int>ans;
    30.         if(arr.size()==0)return ans;
    31.         if(k==0)return ans;
    32.         quick_sort(arr, 0, arr.size()-1, k-1);
    33.         for(int i=0;i
    34.             ans.push_back(arr[i]);
    35.         }
    36.         return ans;
    37.     }
    38. };
    • 最长公共子序列的值

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

    1. class Solution {
    2. public:
    3.     int longestCommonSubsequence(string text1, string text2) {
    4.         int n=text1.length();
    5.         int m=text2.length();
    6.         int dp[n+1][m+1];
    7.         memset(dp, 0, sizeof(dp));
    8.         int pre[n+1][m+1];
    9.         for(int i=1;i<=n;i++){
    10.             for(int j=1;j<=m;j++){
    11.                 if(text1[i-1]==text2[j-1]){
    12.                     dp[i][j]=dp[i-1][j-1]+1;
    13.                     pre[i][j]=1;
    14.                 }
    15.                 else{
    16.                     dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    17.                     if(dp[i][j]==dp[i-1][j]){
    18.                         pre[i][j]=2;
    19.                     }
    20.                     else{
    21.                         pre[i][j]=3;
    22.                     }
    23.                 }
    24.             }
    25.         }
    26.         int i=n,j=m;
    27.         string ans="";
    28.         while(i>=1&&j>=1){
    29.             if(text1[i-1]==text2[j-1]){
    30.                 string t;
    31.                 t.push_back(text1[i-1]);
    32.                 ans=t+ans;
    33.             }
    34.             if(pre[i][j]==1){
    35.                 i--;
    36.                 j--;
    37.             }
    38.             else if(pre[i][j]==2){
    39.                 i--;
    40.             }
    41.             else j--;
    42.         }
    43.         cout<
    44.         return dp[n][m];
    45.     }
    46. };

    超参数一面

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

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     ListNode *next;
    6.  *     ListNode() : val(0), next(nullptr) {}
    7.  *     ListNode(int x) : val(x), next(nullptr) {}
    8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9.  * };
    10.  */
    11. class Solution {
    12. public:
    13.     struct cmp{
    14.         bool operator()(ListNode *a, ListNode *b){
    15.             return a->val > b->val;
    16.         }
    17.     };
    18.     ListNode* mergeKLists(vector& lists) {
    19.         priority_queue, cmp>pq;
    20.         int n=lists.size();
    21.         for(int i=0;i
    22.             if(lists[i])pq.push(lists[i]);
    23.         }
    24.         ListNode *res=new ListNode(-1);
    25.         ListNode *p=res;
    26.         while(!pq.empty()){
    27.             ListNode *tmp=pq.top();
    28.             pq.pop();
    29.             p->next=tmp;
    30.             p=p->next;
    31.             if(tmp->next){
    32.                 pq.push(tmp->next);
    33.             }
    34.         }
    35.         return res->next;
    36.     }
    37. };

    方法二：归并排序

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     ListNode *next;
    6.  *     ListNode() : val(0), next(nullptr) {}
    7.  *     ListNode(int x) : val(x), next(nullptr) {}
    8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9.  * };
    10.  */
    11. class Solution {
    12. public:
    13.     ListNode* Merge(ListNode *left, ListNode *right){
    14.         if(left==NULL)return right;
    15.         if(right==NULL)return left;
    16.         ListNode *ans=new ListNode(-1);
    17.         ListNode *p=ans;
    18.         while(left&&right){
    19.             if(left->val<=right->val){
    20.                 p->next=left;
    21.                 left=left->next;
    22.             }
    23.             else{
    24.                 p->next=right;
    25.                 right=right->next;
    26.             }
    27.             p=p->next;
    28.         }
    29.         if(left)p->next=left;
    30.         if(right)p->next=right;
    31.         return ans->next;
    32.     }
    33.     ListNode* merge_sort(vectorlists, int b, int e){
    34.         if(b==e)return lists[b];
    35.         if(b>e)return NULL;
    36.         int m=(b+e)/2;
    37.         ListNode *left=merge_sort(lists, b, m);
    38.         ListNode *right=merge_sort(lists, m+1, e);
    39.         return Merge(left, right);
    40.     }
    41.     ListNode* mergeKLists(vector& lists) {
    42.         return merge_sort(lists, 0, lists.size()-1);
    43.     }
    44. };
    1. class Solution {
    2. public:
    3.     unordered_map<char,int>pos;
    4.     int lengthOfLongestSubstring(string s) {
    5.         int n=s.length();
    6.         int left=0;
    7.         int ans=0;
    8.  
    9.         for(int i=0;i
    10.             if(pos[s[i]]-1>=left){//交叉重复
    11.                 ans=max(ans, i-left);
    12.                 left=pos[s[i]];
    13.             }
    14.             pos[s[i]]=i+1;
    15.         }
    16.         ans=max(ans, n-left);
    17.         return ans;
    18.     }
    19. };

     超参数二面

     

    •  调用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)

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

    挂。。。

    1. #include
    2.  
    3. using namespace std;
    4. typedef long long ll;
    5. typedef pair<int,int> P;
    6. const int N=100005;
    7. const ll mod=1e9+7;
    8. int randint4(){
    9.     return rand()%4;
    10. }
    11.  
    12. int randint5(){
    13.     int x=randint4();
    14.     int y=randint4();
    15.     int sum=4*x+y;
    16.     if(sum+1!=16){
    17.         return (sum+1)%5;
    18.     }
    19.     else{
    20.         return randint5();
    21.     }
    22. }
    23.  
    24. int main(){
    25.     for(int i=1;i<=10;i++){
    26.         cout<<randint5()<
    27.     }
    28. }

    阿里一面（2022.09.14）

    • 大数加法
    1. #include
    2.  
    3. using namespace std;
    4. typedef long long ll;
    5. typedef pair<int,int> P;
    6.  
    7. const int INF=0x3f3f3f3f;
    8. const int N=3005;
    9. int n,cnt=0;
    10.  
    11. void add(string s1, string s2, int flag){
    12.     int n=s1.length();
    13.     int m=s2.length();
    14.     int len=max(n,m);
    15.  
    16.     int nums[len+5];
    17.     memset(nums,0,sizeof(nums));
    18.     for(int i=0;i
    19.         int a=s1[i]-'0';
    20.         int b=s2[i]-'0';
    21.         nums[i]+=(a+b);
    22.         nums[i+1]+=nums[i]/10;
    23.         nums[i]%=10;
    24.     }
    25.     int k;
    26.     if(nums[len]!=0){
    27.         k=len;
    28.     }
    29.     else k=len-1;
    30.     if(flag)printf("-");
    31.     for(int i=k;i>=0;i--){
    32.         printf("%d",nums[i]);
    33.     }
    34.     printf("\n");
    35. }
    36.  
    37. void sub_solve(string s1, string s2){
    38.     int len=s1.length();
    39.     reverse(s1.begin(),s1.end());
    40.     reverse(s2.begin(),s2.end());
    41.     int nums[len+1];
    42.     memset(nums,0,sizeof(nums));
    43.  
    44.     for(int i=0;i
    45.         int a=s1[i]-'0';
    46.         int b;
    47.         if(ilength()){
    48.             b=s2[i]-'0';
    49.         }
    50.         else{
    51.             b=0;
    52.         }
    53.         if(a>=b){
    54.             nums[i]+=a-b;
    55.         }
    56.         else{
    57.             nums[i]=10+a-b;
    58.             nums[i+1]--;
    59.         }
    60.     }
    61.     for(int i=len-1;i>=0;i--){
    62.         if(nums[i]==0)len--;
    63.         else break;
    64.     }
    65.     for(int i=len-1;i>=0;i--){
    66.         printf("%d",nums[i]);
    67.     }
    68.     printf("\n");
    69. }
    70.  
    71.  
    72. void sub(string s1, string s2){//s1-s2
    73.     int len1=s1.length();
    74.     int len2=s2.length();
    75.     int flag=0;
    76.     if(len1>len2){
    77.         flag=1;
    78.     }
    79.     else if(len1
    80.         flag=2;
    81.     }
    82.     else{
    83.         for(int i=0;i
    84.             if(s1[i]>s2[i]){
    85.                 flag=1;
    86.                 break;
    87.             }
    88.             else if(s1[i]
    89.                 flag=2;
    90.                 break;
    91.             }
    92.         }
    93.     }
    94.     if(flag==0){
    95.         printf("0\n");
    96.     }
    97.     else if(flag==1){
    98.         sub_solve(s1,s2);
    99.     }
    100.     else{
    101.         printf("-");
    102.         sub_solve(s2,s1);
    103.     }
    104. }
    105.  
    106. int main(){
    107.     string s1,s2;
    108.     cin>>s1>>s2;
    109.     if(s1[0]!='-'&&s2[0]!='-'){
    110.         reverse(s1.begin(),s1.end());
    111.         reverse(s2.begin(),s2.end());
    112.         add(s1,s2,0);
    113.     }
    114.     else if(s1[0]=='-'&&s2[0]=='-'){
    115.         s1=s1.substr(1);
    116.         s2=s2.substr(1);
    117.         reverse(s1.begin(),s1.end());
    118.         reverse(s2.begin(),s2.end());
    119.         add(s1,s2,1);
    120.     }
    121.     else{
    122.         if(s1[0]=='-'){
    123.             s1=s1.substr(1);
    124.             sub(s2,s1);
    125.         }
    126.         else{
    127.             s2=s2.substr(1);
    128.             sub(s1,s2);
    129.         }
    130.     }
    131. }
    • 一道leetcode题，字符+数字，字符重复数字的，问第k个字符是什么，暴力模拟即可

    阿里二面（2022.09.16）

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

    微软一面（2022.09.19） 

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

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

    需要考虑出现重复的情况 

    1. class Solution {
    2. public:
    3.     int longestConsecutive(vector<int>& nums) {
    4.         int n=nums.size();
    5.         if(n==0||n==1)return n;
    6.  
    7.         sort(nums.begin(), nums.end());
    8.         
    9.         int left=0,cnt=1,maxx=1;
    10.         for(int i=1;i
    11.             if(nums[i]==nums[i-1])continue;
    12.             if(nums[i]-1==nums[i-1]){
    13.                 cnt++;
    14.             }
    15.             else{
    16.                 if(maxx
    17.                     maxx=cnt;
    18.                     left=i-cnt;
    19.                 }
    20.                 cnt=1;
    21.             }
    22.         }
    23.         if(cnt>maxx){
    24.             maxx=cnt;
    25.             left=n-cnt;
    26.         }
    27.         return maxx;
    28.     }
    29. };

  • 相关阅读:
    Docker镜像多架构构建
    09-排序3 Insertion or Heap Sort（浙大数据结构）
    38.CSS文本动画效果
    Vue组合式 api 的常用知识点
    人工智能基础_机器学习039_sigmoid函数_逻辑回归_逻辑斯蒂回归_分类神器_代码实现逻辑回归图---人工智能工作笔记0079
    MySQL（4）
    PyTorch 卷积网络正则化 DropBlock
    学生信息管理系统 图形用户界面（GUI） java 实现对数据库的操作 数据库用的mysql
    MakeSense中文版使用手册【图像标注神器】
    C++ Reference: Standard C++ Library reference: Containers: array: array: rend
  • 原文地址：https://blog.csdn.net/m0_37579232/article/details/126306501