阿里2020实习生笔试

阿里2020实习生笔试

今年各个技术岗都是第一轮笔试+测评,笔试时间1h,2道编程题。

4.8

  • 小强攻击范围为b,每次攻击能对最多b个存活的木头人造成1点伤害,每次共计需要1s。当经过一次攻击,木头人的血量为0,则木头人死亡。假设有m个木头人,每个木头人血量为a,小强在n 秒时间内最多能消灭多少个木头人。( $1<=n,m,a,b<=10^9$ )

  • 解析:

    • 这个问题需要考虑的情况比较多,需要考虑到轮流攻击这一个点。
    • 当$m<=b$ ,$ans=(n//a)*m$
    • 当$m>b, n<a$ ,$ans=0$
    • 当$m>b,n>=a$ ,$ans=min(nb//a,m)$
  • 给一个n*m矩阵,每一个矩阵有一个值,初始时候位于左上角,每一次可以选择上下左右四个方向中的一个,并且可以移动的距离不大于 k,且保证到达的格子的值要比当前位置的格子的值要大,否则不能移动到这个格子。当无法移动时,游戏结束。求在所有可能走的方案中,到达的位置的格子值相加总和最大是多少?( $1<=n,k<=100, 1<=A[i][j]<=10^5$ )

  • 解析:

    • 由于需要保证到达的格子的值要比当前位置的格子值要大,所以很显然所有的路径形成一个有向无环图DAG。
    • 有了有向无环图之后,我们需要在这个DAG上进行DP,第 k 个节点的最大值取决于其前驱结点的值。
    • 所以我们直接对DAG做拓扑排序,找到这样一个从左到右的序列,复杂度n^2
      在拓扑排序的序列上做DP就很简单了。

4.10

  • 给一个nm的方格,有c种颜色的染料,每一种染料有ci升,每涂一个格子需要1L,对于某个格子上下左右4邻域的格子不能染成和本身格子一样的颜色,求是否能够找到染色方案?($c<=n,m<=5, 1<=k<=nm$ ,保证升数总和和格子总数一致。)

  • 解析:

    • 数据量范围非常小只有5*5,递归即可。
    • 格子坐标之和的奇偶性与四邻域不同,所以根据抽屉原理,如果$max(C[i])>(m*n+1/2)$一定是无解的。充分性或者反例暂时没有想到
  • 二维格点上有n座房子,小强打算修一条平行y轴的水渠,水渠无限长,现在求小强修水渠的位置,能使得这n 座房子到水渠的处置距离和最小,输出最小距离和。($0<=xi,yi<=10^5, 1<=n<=10^5$)

解析:

  • 排序,如果有奇数个点,则水渠修在那个点上,如果有偶数个点,则修建在中位数的两个端点之间即可,复杂度nlogn
  • 根据上述分析,求第k大的数即可,复杂度n

4.13

  • 蚂蚁森林n个小动物,1~n,小动物编号越小能力越强,现在筛选国王,每个小动物都会崇拜别的小动物或者自己,但只会崇拜比自己能力强的小动物。已知是否有偶像和具体是谁,求问每个人最多可以获得多少票。

    • 每只小动物都可以投票选自己,初始 =1
    • 由于小动物能力值从大到小排列,所以从后向前遍历+=num[i]即可。
    • 时间复杂度 [公式]
  • 有n个人,分别在编号1-n的城市,现在去城市x聚会,图有m条有向路径组成,每一个人到达城市 x之后,仍然需要返回初始城市。每一个人的时间消耗为往返距离之和,已知每个人都会走最短的路径,求消耗时间最长的一个人消耗的时间是多少?

    • 初看题目去程是求每一个节点到城市x最短路径,回城是以x为起点的有源最短路径。细想一下去程的问题可以进行改装:
    • 将所有路径反向,求以x为起点的有源最短路径,就是从其他点到达x的去程路径。
    • 初始图求以x为起点的有源最短路径,将所有路径反向,再求以x为起点的有源最短路径,复杂度是朴素Dijkstra复杂度n^2

4.15

  • 有n个人围着坐,给你n个数,你把n个数排列成a1-an,找到|a1-a2|+|a2-a3|…+|an-1 -an|+|an-a1|最大的情况
    • 直观上来说,肯定要把数据参差排列,大小相间,才能够使得 [公式] 尽可能大。尝试几组小的case。
    • 把绝对值符号去掉,可以发现较大的数总是被加了两次,较小的数是被减了两次。
      把n个数排序,对于偶数个数据,最后的结果是n/2个较大的数减去了n/2个较小的数的和的2倍。对于奇数个数据,中位数会被加一次被减一次,对结果无影响。
    • 复杂度 nlogn
  • 有n个人,每个人有一个A和B的值,选择两个人i, j, X=(Ai+Aj)/2, Y=(Bi+Bj)/2, 找到min{X, Y}最大的两个人,输出他们的min{X, Y}

4.17

  • 给定n,构造排列使得满足$i<j<k$的$a_i,a_j,a_k$,不出现$a_k+a_i=aj*2$的情况
    • 如果三个正整数a,b,c形成等差数列,2b=a+c,显然 a,c 的奇偶性相同,且a,c 在整个排列中应当位于b的左侧或者右侧( (a,c,b) (b,a,c)(c,a,b)(b,c,a))。
    • 我们把数据分为奇数和偶数两部分,很显然a,c不能跨越两部分。只需要奇数和偶数也不满足等差数列即可。 对于偶数x=2m, 奇数x=2m+1,对于m来说,又是一个从0开始的正整数序列。所以一次把m,按照奇偶性再分开,依次递归下去
    • code:AC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
    #include <cstdio>
using namespace std;

const int maxn=int(1e6)+11;
int n;
int a[maxn];

void solve(int l,int r,int mark) {
if(l==r) {
if(mark) a[l]=1;
else a[l]=2;
return;
}
int mid=(l+r)>>1;
solve(l,mid,1), solve(mid+1,r,0);
for(int i=l;i<=r;++i)
a[i]=a[i]*2-mark;
return;
}

int main() {
scanf("%d",&n);
solve(1,n,0);

int i;
for(i=1;i<=n;++i) printf("%d ",a[i]/2);
putchar('\n');

return 0;
}
  • 给定一个环,有n个节点,点与点之间有一条无向边,第i条边连接第i个点和第i+1个点,边的权重为Ai,代表走这条边的时间花费。有一条边将被破坏,每一条边被破坏的概率相同。当前有q个人分别从各自的起点走到各自的终点,在边被破坏之前,大家都计划走最近的路线。破坏之后,有可能将不得不改道而行。现在求每一个人的时间花费有多大概率会变大。
  • code:AC
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    #include<bits/stdc++.h>
    using namespace std;

    const int maxn=int(2e5)+111;
    int n,m;
    int val[maxn];
    long long sum[maxn];
    int gcd(int n, int m){
    if(!m)
    return n;
    return gcd(m,n%m);
    }
    void print(int a, int b){
    int g=gcd(a,b);
    printf("%d/%d", a/g, b/g);
    putchar('\n');
    return;
    }
    int main(){
    scanf("%d%d",&n, &m);
    int i;
    for(i=1;i<=n;i++){
    scanf("%d",&val[i]);
    sum[i]=sum[i-1]+val[i];
    }
    for(i=1;i<=m;++i){
    int a,b;
    scanf("%d%d",&a,&b);
    if(a>b)
    swap(a,b);
    long long p1=sum[b-1]-sum[a-1],p2=sum[n]-p1;
    int len1=b-a;len2=n-len1;
    if(p1<p2){
    print(len,n);
    }else if(p2<p1){
    print(len2,n);
    }else{
    printf("0/1");
    putchar('\n');
    }
    }
    return 0;
    }

4.20

  • 勇士打怪兽,n只不同等级Ai的怪兽,勇士有初始能力值n,勇士能力大于等于怪兽,则获得一枚金币,勇士可以用1金币换1能力,问勇士最多可以得到多少金币

  • 解析:怪兽能力排序,一个个打,还是比较容易的

  • code:AC

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;

    int main(){
    int a,n;
    cin >> a >> n;
    vector<int> c;
    for(int i=0; i<n; i++){
    int tmp;
    cin >> tmp;
    c.push_back(tmp);
    }
    sort(c.begin(), c.end());
    int max=0;
    int count=0;
    for(int i=0; i<c.size(); i++){
    if(a >= c[i])
    count++;
    if(count > max) max=count;
    if(a < c[i]){
    count -=(c[i]-a);
    if(count<0)
    break;
    a += c[i]-a;
    count++;
    }
    }
    cout << max;
    return 0;
    }
  • 有n个城市,有n-1条无向边,城市有等级,城市间距离时间为1,小明想要从一个城市到另一个城市,但是一条边只能走一次,起点和终点的等级相同,问最短时间。

  • 解析:就是最短路径问题,同dijiska即可(欸,笔试的时候先是电脑不知道为什么编译什么都不通过,然后是客人来访,然后最后十分钟加的一直编译失败,欸,不说了都是泪)

  • code:30% 超时(可以通过对等级的筛选简化,包括没有两个相同等级的城市不需要计算,同一等级的城市只需要计算一次,但是没来得及交不知道能不能AC)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <map>
    using namespace std;
    # define INF 5000
    int n;
    void Dijkstra_cpp(vector<vector<int>>&vec, vector<int>& result, int v0){
    vector<int> visited(vec.size(), 0); // 表示顶点是否被选中,0:顶点未被选中;1:顶点已被选中
    int last_visited = 0;
    visited[v0] = 1; // 选中起始顶点
    result[v0] = 0;

    for (int i = 0; i < vec.size() - 1; ++i) {
    for (int j = 0; j < vec.size(); ++j) {
    if (visited[j] == 0){
    if (vec[v0][j] != 0){
    int dist = vec[v0][j] + last_visited;
    if (dist < result[j])result[j] = dist;
    }
    }
    }
    // 找出最小值
    int minIndex = 0;
    while (visited[minIndex] == 1) minIndex++;
    for (int j = minIndex; j < vec.size(); ++j) {
    if (visited[j] == 0 && result[j] < result[minIndex]){
    minIndex = j;
    }
    }

    last_visited = result[minIndex]; // 更新最小值
    visited[minIndex] = 1; // 将最小值顶点选中
    v0 = minIndex; // 下次查找从最限制顶点开始
    }
    }


    int main(){
    cin >> n;
    int a[n];
    for(int i=0; i<n; i++){
    cin >> a[i];
    }

    vector<vector<int>> vec(n, vector<int>(n, 0));
    int u,v;
    for(int i=0; i<n-1; i++){
    cin >> u >> v;
    vec[u-1][v-1]=1;
    vec[v-1][u-1]=1;
    }

    int index[n]=0;
    int min=INF;
    for(int i=0; i<n; i++){
    vector<int> result(n, INF);
    if(index[i]==0){
    Dijkstra_cpp(vec,result, i);
    }

    for(int j=0; j<n; j++){
    if(a[i]==a[j])
    index[j]=1;
    if(i!=j && a[i]==a[j] && result[j]<min && min!=0)
    min = result[j];
    }
    }

    if(min==INF)
    cout << -1;
    else
    cout << min;
    return 0;
    }
    // 3
    // 1 2 1
    // 1 2
    // 2 3
    // 2

面试-算法-机器学习

基础知识

  • 正则化的作用:L1/L2正则减弱过拟合,区别:L2平方和开放,L0非零元素,L1绝对值
  • CNN模型:池化层的作用,Max Pooling 是如何反向传递梯度的
  • 线性回归、LR、Naive 贝叶斯、SVM、Kmeans:
  • KNN和LR的区别

  • Dropout

  • 深度学习的优化方法:随机梯度下降

  • RNN模型:

  • Transformer 和 BERT 的位置编码有什么区别?

  • DSSM 语义匹配模型及其变种

项目问题

  • 文本生成任务:1对多训练、如何创造无监督标签、如何提高生成文本的信息含量避免安全回复生成
  • 预训练模型:Transformer、BERT、UniLM 等等模型细节,区别,模型中的 Attention 使用、Mask 使用

语言问题

  • Python 垃圾回收了解吗?

算法

  • 贪心和 DP 区别?DP的一般做法
  • Top-K问题:
    • 堆排序(nlogK)
    • 随机选择(n)
# 面试

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×