蚂蚁金服 暑期实习生 3面 和 阿里笔试 3.25
昨天电话约了今天的电话面试，11:30，聊了40分钟。
昨天下午做了阿里的线上笔试，晚上做了测评。
笔试
笔试难度不大，在牛客网上完成，2道算法题，LeetCode medium难度。
给3xn的矩阵，每列选择其中的一个数, 形成最后的数组。
使得最后的
最小。
输出最小的这个值。
DP求解即可。
时间复杂度: O(3N),
空间复杂度: O(3).
```cpp
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<ll> last_dp(3, 0);
vector<vector<ll>> matrix(3, vector<ll> (n));
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < n; ++j) {
cin >> matrix[i][j];
}
}
for (int i = 1; i < n; ++i) {
vector<ll> dp(3);
for (int dp_index = 0; dp_index < 3; ++dp_index) {
dp[dp_index] = abs(matrix[dp_index][i] - matrix[0][i-1]) + last_dp[0];
for (int j = 1; j < 3; ++j) {
ll new_value = abs(matrix[dp_index][i] - matrix[j][i-1]) + last_dp[j];
if (new_value < dp[dp_index]) {
dp[dp_index] = new_value;
}
}
}
last_dp = move(dp);
}
cout << min({last_dp[0], last_dp[1], last_dp[2]}) << endl;
return 0;
}
一个n x m的矩阵，每列每行都是等差数列，公差为整数。
输入n x m个数，如果为0表示不知道，否则知道。
q个查询，特定位置（下标1开始）的值是否可确定。
递归求解，进行推测即可。可以用一些数组维护：每行/列是否已经被推断、每行/列已知道的数的下标、行列信息。
时间复杂度: O(N * M),
空间复杂度: O(N * M).
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
using ll = long long;
const int INF = 0x3f3f3f3f;
int main() {
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> A(n, vector<int> (m, INF));
vector<int> row(n, -1);
vector<bool> row_ok(n, false);
vector<int> col(m, -1);
vector<bool> col_ok(m, false);
function<void(int, int, int)> fill = [&](int i, int j, int value) -> void {
A[i][j] = value;
if (col_ok[j] && row_ok[i]) {
return;
} else {
if (!col_ok[j]) {
if (col[j] == -1 || col[j] == i) {
col[j] = i;
} else {
col_ok[j] = true;
int diff = (A[i][j] - A[col[j]][j]) / (i - col[j]);
for (int r = i - 1; r >= 0; --r) {
fill(r, j, A[r + 1][j] - diff);
}
for (int r = i + 1; r < n; ++r) {
fill(r, j, A[r - 1][j] + diff);
}
}
}
if (!row_ok[i]) {
if (row[i] == -1 || row[i] == j) {
row[i] = j;
} else {
row_ok[i] = true;
int diff = (A[i][j] - A[i][row[i]]) / (j - row[i]);
for (int c = j - 1; c >= 0; --c) {
fill(i, c, A[i][c + 1] - diff);
}
for (int c = j + 1; c < m; ++c) {
fill(i, c, A[i][c - 1] + diff);
}
}
}
}
};
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int v;
cin >> v;
if (v != 0) {
fill(i, j, v);
}
}
}
for (int i = 0; i < q; ++i) {
int r, c;
cin >> r >> c;
--r;
--c;
if (A[r][c] == INF) {
cout << "Unknown" << endl;
} else {
cout << A[r][c] << endl;
}
}
return 0;
}
测评
笔试没难倒我，测试却花了我不少时间。
主要是测试
- 语文：阅读理解、成语使用、归纳和排除 10min
- 数学：表格、图、经济用语 10min
- 智商：看图找规律 10min
- 性格：是否抗压、反社会 30min
全靠高中学习到的知识和技能。智商就天生的呗。
据说和公务员的考试很像，行测。有了解的朋友可以看看。
应该也不会用测评去筛人，又不是考公务员，手撕代码才是王道。
面试
面试官很NICE，还加了我微信进行沟通。
主要聊了项目，还有一些数据处理的知识和Java的了解。
- 数据预处理，对缺失值的处理
- 给一个信用评估的数据，如何利用和上线
- Java了解程度和使用，Spring boot
最后问了英语怎样，口语如何。可能是因为对方是 国际化事业群 吧。
我最后问了面试官所在的组和业务。
面向海外的个人信贷业务，类似花呗和借呗。
