2019年算法、开发找日常实习&暑期实习记录

去年的记录，offer基本都拿到，过程和题目记录分享给大家。

1. Momenta视觉算法岗

GAN做语义分割有什么特别之处？
GAN的Generator最后一层为什么要用tanh？
优化器的区别sgd：adam。
BN在训练和测试过程中的表现。

cuda？
并行计算？
python、golang并发的不同。
讲最大流（讲dinic）

第三个聊了聊paper，十分钟。

面试官说一个算法，让你手撕代码（道格拉斯抽稀）：
double dist(vector<double> P, vector<double> A, vector<double> B) {
function<double(vector<double>, vector<double>)> dist_point = [](vector<double> a, vector<double> b) {
double ret = .0;
assert(a.size() == b.size());
for(int i = 0; i < a.size(); i++) {
ret += (a[i] - b[i]) * (a[i] - b[i]);
}
return (double)sqrt(ret);
};
function<double(vector<double>, vector<double>, vector<double>, vector<double>)> dot =
[](vector<double> a1, vector<double> a2, vector<double> b1, vector<double> b2) {
double ret = .0;
vector<double> a, b;
assert(a1.size() == a2.size());
assert(b1.size() == b2.size());
assert(a1.size() == b1.size());
for(int i = 0; i < a1.size(); i++) {
a.emplace_back(a2[i] - a1[i]);
b.emplace_back(b2[i] - b1[i]);
}
for(int i = 0; i < a.size(); i++) {
ret += a[i] * b[i];
}
return ret;
};

double cos_theta = dot(A, P, A, B) / dist_point(A, P) / dist_point(A, B);
double a0 = dist_point(A, P) * cos_theta;
double L = dist_point(P, A), R = dist_point(P, B);
if(a0 >= dist_point(A, B) || a0 <= 0) return min(L, R);
double sin_theta = (double)sqrt(1.0 - cos_theta * cos_theta);
double ret = dist_point(A, P) * sin_theta;
return ret;
}

vector<vector<double>> douglas(const vector<vector<double>> &points, double thresh) {
using pivd = pair<int, vector<double>>;
vector<pivd> pointss;
for(int i = 0; i < points.size(); i++) {
pointss.emplace_back(i, points[i]);
}
vector<pivd> ret;
ret.emplace_back(*pointss.begin()); ret.emplace_back(*pointss.rbegin());
function<void(int, int)> split = [&](int l, int r) {
vector<double> L = pointss[l].second, R = pointss[r].second;
double D = -1;
int id = -1;
for(int i = l + 1; i < r; i++) {
double tmp = dist(pointss[i].second, L, R);
if(tmp > D) {
D = tmp;
id = i;
}
}
if(D > thresh) {
split(l, id); split(id+1, r);
ret.emplace_back(pointss[id]);
}
};
split(0, points.size()-1);
sort(ret.begin(), ret.end(), [](pivd a, pivd b) {
return a.first < b.first;
});
vector<vector<double>> result;
for(auto x : ret) result.emplace_back(x.second);
return result;
}

地平线视觉算法岗

一面：
问了一堆项目里的细节，主要是PAPER里的。
Batch Normalization理解，公式。
CRF的优化目标。
解释一下Dice指标。
100w个100维的数据，多次查询和给定的100维的数据点欧几里德距离最近的点。
Python在一个类里用multiprocessing有什么问题。
Python线程和进程，有没有用过多进程，怎么设计的调度。

二面：
也问了BN、CRF
什么是过拟合，如何避免过拟合（droupout，怎么设置）
又介绍了一遍Paper的工作
要我十分详细地讲了一下U-Net的结构。
抛硬币20次，正反面概率都是1/2，问8次向上的概率。

题目1：
Input : 数组A[1..n] , 构造数组B[1...n],  B[i] = A[1]A[2]...A[n]/A[i], 不能使用除法， 时间复杂度O(n)
题目2：
输入：
/mnt/dir/A.jpg
/mnt/di/B.jpg
/mnt/dir/C.jpg
输出：
/mnt/dir0/A.jpg 0
/mnt/dir1/B.jpg 1
/mnt/dir0/C.jpg 0


先写了一个，然后要求优化。我说除法可以用二分转成乘法算，不过变成nlogn。
最后优化到n
using LL = long long;
vector<LL> gao(vector<LL>& a) {
int n = a.size();
if(!n) return vector<LL>();
vector<LL> b(n, 0);
vector<LL> s1(n, 1), s2(n, 1);
s1[0] = a[0], s2[n-1] = a[n-1];
for(int i = 1; i < n; i++) {
s1[i] = s1[i-1] * a[i];
}
for(int i = n-2; i >= 0; i--) {
s2[i] = s2[i+1] * a[i];
}
b[0] = s2[1]; b[n-1] = s1[n-2];
for(int i = 1; i < n - 1; i++) {
b[i] = s1[i-1] * s2[i+1];
}
return b;
}

考会不会写python
def gao(input_filename, output_filename):
lbl = dict()
lbl_cnt = 0
with open(output_filename, 'w') as fout:
with open(input_filename, 'r') as fin:
cur_path = fin.readline()
dir = cur_path.split('/')[:-2]
if dir not in lbl:
lbl[dir] = lbl_cnt
lbl_cnt += 1
cur_lbl = lbl[dir]
fout.write('{} {}\n'.format(cur_path, cur_lbl))

3. 商汤视觉算法岗

一面
介绍paper，非常非常细节。
介绍一下复现paper的工作，SRResNet的结构，如何上采样。
你用了什么trick训的GAN。
[1,100]里随一个数，每个数都有一个权重，设计一个随机数生成器。
N皇后复杂度。

二面
介绍paper，U-Net的结构细节，比一面粗略一些。
ResNet里的瓶颈层的作用是什么。
DenseNet的结构是什么样的？
AlexNet里的Dropout是怎么设计的，训练和测试时Dropout都有什么样的表现？
C++多态可以怎么有几种实现（答两种）。
C++里new malloc的区别是什么？
KL散度是什么，说一下公式，拿来判别两个分布的缺陷是什么？
SVM核方法是做什么的？常见的有哪些核？SMO算法是什么，做什么的？
红黑树（后来说自己不太熟悉红黑树，于是解释了Splay）是做什么的，说说怎么实现。
最长公共子序列（我直接说了递推方程，于是被跳过）。
2n个数的和为S，是否有一种分法，使得分成两组后和分别为S/2？（这是个np问题，我给了2个暴力和1个近似解，发现优化不动）。
乱序数组求第k大/小。

4. 字节跳动算法岗

二维数组逆时针螺旋打印
比如输入
1234
5678
9abc
输出
159abc843267

讲讲SVM，有什么优缺点。
快排复杂度说明。

--------
下面的代码对么？不对后修改，输出是什么？为什么？
struct Node {
int value;
char b;
Node *left;
Node *right;
};
struct  Node *a=0;
a++;
cout<<a<<endl;

-----------(c++ 17)
#include<iostream>
namespace A{
extern "C" int x;
};
namespace B{
extern "C" int x;
};
int A::x = 0;
int main(){
std::cout << B::x;
A::x=1;
std::cout << B::x;
}

介绍SVM。
ROC、AUC。
神经网络参数初始化同一个值会怎么样。
说说dropout。
依旧是paper的工作非常详细…以及仔细讲了讲U-Net。
手撕了一棵字典树。
面试官介绍了一下工作。

5. 头条后端开发

TCP挥手。
然后问TCP UDP的区别。
进程和线程的区别；
代码：给定两个正整数M和N，N<M，求1,2,3,4....M按照字典序排列的第N小的。
字典树根节点存不存字符。

路由器和交换机的区别。
段页存储。
快速排序复杂度证明。
网络流算法原理。
一个地方的人都想生男孩，于是会一直生女孩，生到有一个男孩为止，问男女比。
代码：判断完全二叉树。
40g砝码分成4个，怎么分能称出1~40g的物品。