一面
项目
自我介绍
详细介绍阿里云实习
主要从事关系型数据库，对非关系型数据库了解吗
性能测试的数据量有多大
有从事多机分布式方面的工作吗
微信实习用了 RPC 框架，讲讲 RPC 原理
讲讲 Momenta 车道线检测模型
在 Momenta 实现的数据管理平台是什么
详细介绍天池比赛
哈希表解决冲突的方法
热点数据怎么缓存
空间块大小怎么设置的
如何利用 AEP 特性
RAM、AEP 与 SSD 的对比
Coding
接雨水
class Solution {public:
int trap(int* A, int n) {
// write code here vector<int> lmax(n, A[0]);
vector<int> rmax(n, A[n - 1]);
int res = 0;
for (int i = n - 2; i >= 0; -- i)
rmax[i] = max(rmax[i + 1], A[i]);
for (int i = 1; i < n; ++ i) {
lmax[i] = max(lmax[i - 1], A[i]);
int water = min(lmax[i], rmax[i]) - A[i];
if (water > 0)
res += water;
}
return res;
}};二面
项目
自我介绍
详细介绍天池比赛
get 时，如果50%的key不存在，用什么方法高效判断
bloom filter
考虑过把索引持久化吗
判断 kv 完整性，除了首尾哨兵还有什么方法
checksum
这个比赛读写能达到 AEP IO 吞吐瓶颈吗
Raft 如何保证一致性
Raft 详细过程
智力题
10个红球和10个蓝球，两个桶，如何放置球可以使取一次红球的概率最大
一个桶里放1个红球，另一个桶里放10个蓝球和9个红球
Coding
求一颗 n 个节点的二叉树有多少种形状？
#include <iostream>#include <vector>using namespace std;int main() {
int n;
cin >> n;
vector<int> dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; ++ i) {
for (int j = 0; j <= n - 1; ++ j) {
dp[i] += dp[j] * dp[i - j - 1];
}
}
cout << dp[n];
return 0;}对一个数组 a，要求在 O(n) 的时间复杂度内求出所有满足快排 partition 的数 x，xleft < x <= xright
说了一种单调栈的思路，面试官说没问题，没写代码
后来想了下，顺序扫一遍维护最大值，逆序扫一遍维护最小值就行了
三面
项目
自我介绍
详细介绍天池比赛
工作方向有什么倾向
Coding
向量 v1 =[1,2,0,0,1] v2 =[1,0,0,1,2]
dot(v1, v2)=1*1+1*2=3
稀疏向量 #zero > 95%
你的任务：
1）设计一个数据结构来表示稀疏向量，空间需要比较紧凑
2）基于这个数据结构，实现向量的点积。
// class Vect {// private:// unordered_map<int, int> idx_mp;// public:// Vect(vector<int> &v) {// for (unsigned int i = 0; i < v.size(); ++ i) {// if (v[i] != 0)// idx_mp[i] = v[i];// }// }// int dot(Vect &vec) {// int res = 0;// for (auto p : idx_mp) {// int idx = p.first;// int value = p.second;// if (vec.idx_mp.find(idx) != vec.idx_mp.end())// res += value * vec.idx_mp[idx];// }// return res;// }// };class Vec_arr {private:
vector<pair<int, int>> idx_val;public:
Vec_arr(vector<int> &v) {
for (int i = 0; i < v.size(); ++ i) {
if (v[i] != 0)
idx_val.push_back({i, v[i]});
}
}
int get_size() { return idx_val.size(); }
int binarySearch(Vec_arr &vec, int target) {
int l = 0, r = vec.idx_val.size() - 1;
while (l <= r) {
int m = (r - l) / 2 + l;
if (vec.idx_val[m].first == target)
return vec.idx_val[m].second;
else if (vec.idx_val[m].first < target)
l = m + 1;
else
r = m - 1;
}
return -1;
}
int dot(Vec_arr &vec) { // vec 更长 int res = 0;
for (auto p : idx_val) {
int idx = p.first;
int value = p.second;
int vec_val = binarySearch(vec, idx);
if (vec_val != -1)
res += value * vec_val;
}
return res;
}};int main() {
vector<int> v1 = {1, 2, 0, 0, 1};
vector<int> v2 = {1, 0, 0, 1, 2};
Vec_arr vec1(v1);
Vec_arr vec2(v2);
if (vec1.get_size() < vec2.get_size())
cout << vec1.dot(vec2);
else
cout << vec2.dot(vec1);
return 0;
}先用 unordered_map 实现了一版
面试官说 unordered_map 空间占用大，只用 vector 怎么实现
于是实现了一版 vector 的，dot 复杂度为 O(m+n)，m 为 v1 的非零元素个数，n 为 v2 的非零元素个数
面试官又说假如 m 远大于 n，怎么优化，于是实现了 binary search 优化版的
快 Star 答辩
HR 面后通知的答辩，形式是 20min 1v3 的陈述（讲 PPT 讲 Word 都可以），10min 的问答。问答比较 high level，比如实习经历的创新点有哪些、给公司带来了多少收益、工作中如何定位性能问题及其优化等等。
总结
和快手面试官聊得很融洽，对组内工作也感兴趣，再加上给了 “快Star”，是手上最好的 offer 之一，于是选择了快手。
