商汤算法实习面试(2021.1.11一面 1.13二面 1.14三面)/intel swe实习面试(2021.1.15)/深信服 C++实习面试(2021.1.21)/微软暑期实习笔试(2021.2.28)/阿里暑期实习笔试(2021.3.15)/Google kickstart(2021.3.21))

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

商汤算法实习面试(2021.1.11一面 1.13二面 1.14三面)/intel swe实习面试(2021.1.15)/深信服 C++实习面试(2021.1.21)/微软暑期实习笔试(2021.2.28)/阿里暑期实习笔试(2021.3.15)/Google kickstart(2021.3.21))

作者：

仅存老实人 , 2021-01-11 16:53:15 , 所有人可见 , 阅读 1601

14

11

int f[501][1000010]; segmentation fault -> 数组开太大了栈溢出
int a[];的长度 sizeof();//拼多多面试暴露的问题
scanf("%lld",&x)
printf("%lld",x)
char op[2];scanf("%s",op);
printf(".4lf") double型数据输出
dfs(vector<int> &a);传参时如果值传递可能超时 递归深度过深会segmentation fault(考虑是否没有及时return 比如快排l>r时)

string取子串 s.substr(startidx, length);
string小写转大写 transform(s.begin(),s.end(),s.begin(),::toupper);

LLONG_MAX为longlong 的最大值

注意一个细节就是01背包如果是多维数组 在遍历体积的时候<v[i]的情况下要f[i][j]继承f[i-1][j]
if(j<v[i]) f[i][j] = f[i-1][j];否则到第i+1个的时候j<v[i]的信息就丢了

奇数时到n/2+1 偶数时到n/2的方法: i<=(n-1)/2;

C++不能写成0<=x<m && 0<=y<n 而应写成0<=x && x<m && 0<=y && y<n 
static和&不能漏
sort(vec.begin(),vec.end(),cmp);

auto cmp = [](const PII &a,const PII &b)
{
    return a.first==b.first?a.second<b.second:a.first>b.first;
};
priority_queue<PII,vector<PII>,decltype(cmp)> h(cmp);
优先队列自定义排序 auto cmp定义在函数内 decltype自动类型判断
static bool cmp(vector<int> &a,vector<int> &b){return a[0]<a[1];} 
比sort(vec.begin(),vec.end(),[](vector<int>a,vector<int>b){a[0]<a[1];});快
vector pop_back();返回的是void

邻接表构图前
memset(h,-1,sizeof h);不能漏

结构体实例化//微软面试暴露的问题
struct Node
{
    int val;
    Node *next;
    Node(int x):val(x),next(nullptr){}
}

Node* p = new Node();
Node p = Node();

数组传参需要定义第二维维度
void f(int[][410] s)

背包
如果求组合数(a+b==b+a)就是外层for循环遍历物品，内层for遍历体积。
如果求排列数(a+b!=b+a)就是外层for遍历体积，内层for循环遍历物品。

弱项:
AC自动机 线段树 dp分析

Java
二分搜索的时候考虑(l+r)/2可能会溢出 改为 l+(r-l)/2;
DFS(int[] a)时相当于C++ 按引用传递,即递归到底层时修改会产生作用(leetcode1239)

商汤算法实习

1.11 一面

面试官问我的

1 自我介绍

2 讲一下第一个遥感图像分割的项目
讲一下损失dice
讲一下损失lovasz
讲一下滑窗伪影问题和消除方法
讲一下批预测
讲一下attention

3 了解分类和检测算法吗
讲一下SENet,CBAM

4 讲一下云分类项目
resnet50+CBAM

5 讲一下了解的一些网络结构
讲了一下GCN/Transformers

6 看你是非科班的，数据结构、操作系统这些cs课有学过吗？排序算法讲一下
讲了一下归并排序

7 传统机器学习的课上过吗？讲一些了解的算法
无监督聚类 k-means
svm的优点？
svm的核trick?

1.13二面

15分钟笔试题

实习2面.JPG

面试官问我的

项目介绍

大致内容同一面

学习路径介绍

大四毕设 做分类分割
研一上比赛 分割pipeline走一遍 attention、GCN
研一下开始看点云(展开聊了一下)
研二上开始看其他论文

1.14三面

面试官问我的

项目介绍

大致内容同一面
不过这次要我把项目ppt和界面演示都做了一遍
超分辨率重建srGAN
多尺度注意力目标检测

点云相关

针对我做点云的背景，三面面试官也是一个做点云的
讲一下pointnet和pointnet++的区别-后者在前者基础上做了局部邻域特征聚合
pointnet文章里的blocksize怎么取的、ball queries是怎么做的？(这两没答上来)
knn取邻近点代码
代码有看过吗？

intel swe实习

自我介绍

面试官问

python 装饰器会吗？怎么用？
C++强制类型转换类型
pytorch modules和function区别
pytorch能不能在自己没有写模型函数而只有模型权重的情况下输出中间层的范围？(没答对，面试官说torch中间变量不会保存，需要用一个token才能调用到)

深信服 C++实习

自我介绍

面试官问

C++多态/虚函数/STL中的vector/list底层区别
网络TCP/IP

微软暑期实习(2.28)

笔试

一面 实现一个字符串s,将其中0~1000的数字转为英文--纯模拟
二面 bfs、dfs、leetcode143 重排链表

1

微软1.JPG
记录最大数之后,遍历两次,一次放严格上升数,一次放严格下降

import collections
def solution(A):
    MAX_NUM=max(A)
    res=collections.Counter(A)
    count=0
    for i in res:
        if i<=MAX_NUM:
            res[i]-=1
            count+=1
    for i in res:
        if i<MAX_NUM and res[i]>0:
            res[i]-=1
            count+=1
    return count

2

微软2.JPG
dp O(n^2)在时间上只过了60%数据

#include<iostream>
#include<vector>
#include<map>
#include<cstring>
using namespace std;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int n = A.size();
    map<int,int> mapp;
    for(int i=1;i<n;i++)mapp[A[i-1]+A[i]]=1;
    vector<int> sums;
    for(auto& [s,in]:mapp)sums.push_back(s);
    int ans = 0,m=sums.size();
    vector<vector<int>> dp(m,vector<int>(n,0));
    for(int idx=1;idx<n;idx++)
    {
        for(int j=0;j<m;j++)
        {
            int s = sums[j];
            if(s==A[idx]+A[idx-1])
            {
                if(idx==1)dp[j][idx]=1;
                else dp[j][idx] = dp[j][idx-2]+1;
            }
            else dp[j][idx] = dp[j][idx-1];
            ans = max(ans,dp[j][idx]);
        }
    }
    return ans;
}

int main()
{
    int x;
    vector<int> A;
    while(cin >> x,x)
    {
        A.push_back(x);
    }
    cout << solution(A);
    return 0;
}

dp优化O(nlogn)

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int n = A.size();
    map<int,int> mapp;
    for(int i=1;i<n;i++)mapp[A[i-1]+A[i]]=1;
    vector<int> sums;
    for(auto& [s,in]:mapp)sums.push_back(s);
    sort(sums.begin(),sums.end());//从小到大排 方便后期用二分搜
    int ans = 0,m=sums.size();
    vector<vector<int>> dp(m,vector<int>(3,0));
    int cur_idx=-1,pre_idx=-1;
    for(int idx=1;idx<n;idx++)
    {
        int l=0,r=m,s=A[idx]+A[idx-1];
        while(l<r)
        {
            int mid=(l+r)/2;
            if(sums[mid]>=s)r=mid;
            else l=mid+1;
        }
        // 找到和为A[i-1]+A[i]在sums中的索引l
        if(dp[l][2]+1>dp[l][1])
        {
            dp[l][2]=dp[l][0]+1;
            cur_idx = l;
        }
        else
        {
            dp[l][2]=dp[l][1];
            cur_idx = -1;
        }
        // 进入下一个idx之前把第1列赋到第0列，把第2列赋到第1列
        if(pre_idx!=-1)
        {
            dp[pre_idx][0]=dp[pre_idx][1];
        }
        pre_idx=cur_idx;// 进入下一个idx后当前更改索引变成pre更改索引
        if(cur_idx!=-1)
        {  
            dp[cur_idx][1]=dp[cur_idx][2]; 
        }
        ans = max(ans,dp[l][2]);
    }
    return ans;
}

3

微软3.JPG
优先队列维护最小两个值融合

import heapq
def solution(A):
    h = []
    for i in A:
        heapq.heappush(h,i)
    while len(h)>=2:
        s0=heapq.heappop(h)
        s1=heapq.heappop(h)
        if s0==s1:
            heapq.heappush(h,s0+1)
            heapq.heappop(h)
        else:
            res.append(s0)
            heapq.heappush(h,s1)
    return len(h)+len(res)

阿里暑期实习(3.15)

一面 面试内容偏推荐算法
问如何选出重要性最大的特征--求梯度(类似gradCAM)、gumbel softmax学一个选择矩阵
问没有点特征只有点特征之间的距离，怎么无监督聚类--谱聚类
二面 纯聊项目

1

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        vector<int> a2(30,0);
        vector<int> b2(30,0);
        vector<int> c2(30,0);
        for(int i=0;i<30;i++)
        {
            if(a&(1<<i))a2[i]=1;
            if(b&(1<<i))b2[i]=1;
            if(c&(1<<i))c2[i]=1;
        }
        int res = 0;
        for(int i=0;i<30;i++)
        {
            if(c2[i]==0)
            {
                if(a2[i]==1)res++;
                if(b2[i]==1)res++;
            }
            else
            {
                if(a2[i]==1 || b2[i]==1)continue;
                else res++;
            }
        }
        cout<<res<<endl;
    }
    return 0;
}

2

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>

using namespace std;

const int N=10010;
double f[N];

int dp(int n,int d)
{
    if(d==0)return n;
    if(f[n])return f[n];
    double res = 0.0;
    for(int i=1;i<=n-1;i++)
    {
        double maxi = max(i,n-i);
        double mini = min(i,n-i);
        if(maxi-mini>=2&&d>0)res+=(mini+dp(maxi-mini,d-1))/(n-1);
        else res+=maxi/(n-1);
    }
    f[n]=res;
    return res;
}
int main()
{
    memset(f,0,sizeof f);
    int n;
    cin>>n;
    f[1]=1;
    f[2]=1;
    vector<int> res;
    dp(n,2);
    printf("%.4lf",f[n]);
    return 0;
}

Google 3.21

1

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
const int N=200010;
char s[N];
int t;
int main()
{
    cin>>t;
    for(int tt=1;tt<=t;tt++)
    {
        int n,k;
        cin>>n>>k;
        cin>>s;
        int cur = 0;
        for(int i=0;i<n/2;i++)
        {
            if(s[i]!=s[n-i-1])cur++;
        }
        int res = abs(k-cur);
        printf("Case #%d: %d\n",tt,res);
    }
    return 0;
}

2

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
const int N=1010;

int t;
int a[N][N];
int u[N][N],l[N][N],d[N][N],r[N][N];

int calc(int a,int b)
{
    int mini = min(a,b);
    int maxi = max(a,b);
    if(maxi<4)return 0;
    int res = 0;
    res+=min(mini,maxi/2)-1;//长的做长
    if(mini<4)return res;
    res+=mini/2-1;//短的做长
    return res;
}
int main()
{
    cin>>t;
    for(int tt=1;tt<=t;tt++)
    {
        int m,n;
        cin>>m>>n;
        memset(a,0,sizeof a);
        memset(u,0,sizeof u);
        memset(d,0,sizeof d);
        memset(l,0,sizeof l);
        memset(r,0,sizeof r);
        int res = 0;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
            {
                cin>>a[i][j];
                if(a[i][j]!=0)
                {
                    u[i][j]=u[i-1][j]+1;
                    l[i][j]=l[i][j-1]+1;
                }
            }
        for(int i=m;i>=1;i--)
            for(int j=n;j>=1;j--)
                if(a[i][j]!=0)
                {
                    d[i][j]=d[i+1][j]+1;
                    r[i][j]=r[i][j+1]+1;
                }
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
            {
                res+=calc(u[i][j],l[i][j])+calc(u[i][j],r[i][j])+calc(d[i][j],l[i][j])+calc(d[i][j],r[i][j]);
            }
        printf("Case #%d: %d\n",tt,res);
    }
    return 0;
}