实习笔试题目

2020年因疫情在家投递实习的笔试题目

一些大厂2020年暑期实习题目

Posted by 柳阳飞 on April 19, 2020
阿里笔试题（编程题2道）

  1. 小强有一个 的矩阵 ，他将 中每列的三个数字中取出一个按顺序组成一个长度为 的数组 ，求 的最小值。

    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

    #include <bits/stdc++.h>
    
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;
}

  2. 给 三个数，一个 行 列的矩阵，每行每列都是等差数列，其中0表示未知值，组位置，问每个位置的值是否可确定。

    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

    #include <bits/stdc++.h>
    
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;
}
腾讯笔试题（编程题5道）

  1. 小Q在玩一款打怪兽的游戏，他在之前的关卡已经获得了足够多的金币，当前关有n个怪兽，每个怪兽有的血量，打死它可以获得的金币， 问小Q通过当前关卡最多可以多获得多少金币。 输入： 输入两个数，n,m 。n表示怪兽的数量，m表示一个金币可以购买的血量。接下来n行，每行是一个怪兽的血量和打死它可以获得的金币。 输出： 通过当前关卡最多可以多获得的金币数

    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 <iostream>
using namespace std;
const int N = 1010;
int c[N], w[N];
int main() 
{
    int n, m;
    while (cin >> n >> m) 
    {
    	for (int i = 0; i < n; i++) 
        {
    		cin >> c[i] >> w[i];
    	}
    	int cost = 0; // 记录买血花了多少钱
    	int blood = 0; // 记录自己拥有的血量
    	int gain = 0; // 记录打怪兽获得的金币
        // 遍历每一只怪兽，可以选择打或者不打
        for (int i = 0; i < n; i++) 
        {
            // 先购买可以打死当前怪兽的血量
            int cnt = 0;
            while (blood < c[i]) 
            {
                cnt++;
                blood += m;
            }
            //如果买血花的金币小于等于打死获得的金币，说明值得打
            if (cnt - w[i] <= 0) 
            {
                cost += cnt;
                blood -= c[i];
                gain += w[i];
            // 否则选择不打
            } 
            else 
            {
                blood -= cnt * m;
            }
        }
        cout << gain - cost << endl;
    }
    return 0;
}

  2. 抛物线与直线围成的面积，给一个抛物线方程是，直线方程是，求所围成封闭图形的面积。

    输入：

    A, B, C

    输出：

    面积

    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

    #include <bits/stdc++.h>
   
using namespace std;
   
int a, b, c;
// 定义积分函数
double fun(double y)
{
    return ((y - c) / b) - (pow(y, 2) / (2 * a));
}
// 求定积分，n控制精确度
double djf(double y1, double y2, int n)
{
    double w, s = 0.0;
    double k = (y2 - y1) / n;
    for(int i = 1; i <= n; i++)
    {
        w = fun(y1 + (i - 1) * k) * k;
        s += w;
    }
    return s;
}
   
int main()
{
    int t;
    while(cin >> t)
    {
        vector<float> ans;
        for(int i = 0; i < t; i++)
        {
            cin >> a >> b >> c;
         	// 求根的判别式
            double delta = 4 * pow(a, 2) - 8 * a * b * c;
            if(delta <= 0)
                ans.push_back(0);
            else
            {
                float y1 = (2 * a + sqrt(delta)) / (2 * b), 
                y2 = (2 * a - sqrt(delta)) / (2 * b);
                if(y1 > y2)
                    swap(y1, y2);
                ans.push_back(djf(y1, y2, 10000));
            }
        }
        for(int i = 0; i < t; i++)
            cout << ans[i] << endl;
    }
}

  3. 牢房冲突

    有n个牢房，编号为1~n,每个牢房中都包含一个人，每个人都可以在1~m中选择一个数字，如果有相邻牢房选择的数字相同，则会发生冲突。求发生冲突的情况有多少种？结果对100003取余。

    输入：m, n

    输出：发生冲突情况数

  4. 完美数

    有n个数，每个数有k个属性值，对于任意的两个数和，如果 ，则$a_{i}a_{j}$是一对完美数。 求这n个数中总共有多少对完美数. 输入： n, k 。n个数，每个数有k个属性。 接下来n行，每行k个属性 输出： 总共有多少对完美数

  5. 最大关系网

    有n对关系，比如A和B有关系，B和C有关系，则ABC关系。求这些关系中能构成的最大关系网中的人数。

    输入： n 。n对关系 接下来n行，每行是一对关系 输出： 这些关系中构建出来的最大关系网中的人数

    输入举例：

    1 2

    3 4

    5 6

    1 6

    输出 4，解释：1256在一个集合中。

华为笔试题目（编程题3道）

  1. 输入一串字符串，表示人名，输出票数最多的人的名字，票数一样多的按首字母先后顺序，先后顺序一样的，名字短的在前面，其中每个人名只有首字母大写，用空格隔开。

    输入:

    Tom Lily Mike Lily Tom

    输出：

    Lily

  2. 字符串匹配，输入一串字符串，找出特定字符串后面的特定类型的值，保证’[‘前的字符要和第一个关键词就是read 是一样的，中间也要保证十六进制。

    输入：

    “read read[addr=0x17,mask=0xff,val=0x7], read_his[addr=0xff,mask=0xff,val=0x1], read[addr=0xf0,mask=0xff,val=0x80]“

    输出：

    addr mask val 所对应16进制值

  3. 最大开销栈，函数a 的空间是30，函数a调用了函数b(空间是60)，函数b调用了函数c(空间是30)，则最大开销栈是30+60+30=120。

    输入：

    第一行n，表示n个函数，编号为1-n,

    第二行n个数，表示n个函数每个函数调用的子函数个数

    接下来n行分别是每个函数的编号，空间，调用的子函数编号

    输出：

    最大开销

    测试例：

    6

    2 3 1 0 0 0 // 表示每个函数调用多少个子函数

    1 20 2 3

    2 30 3 4 5

    3 50 4

    4 60

    5 80

    6 90

    输出：160，解释1-2-3-4

美团笔试题（编程5道)

  1. 给n个学生的m科成绩，如果一个学生的某一科是单科最高，那么这个学生获得奖励，即便该学生有多科最高，也只获得一次奖励。求获得奖励的学生人数。

    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

    #include <iostream>
#include <vector>
using namespace std;
    
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> data(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int tmp;
            cin >> tmp;
            data[i].push_back(tmp);
        }
    }
    vector<int> flag(n);
    for (int j = 0; j < m; ++j) {
        int max_value = 0;
        vector<int> max_index;
        for (int i = 0; i < n; ++i) {
            if (data[i][j] > max_value) {
                max_value = data[i][j];
                max_index.clear();
                max_index.push_back(i);
            } else if (data[i][j] == max_value) {
                max_index.push_back(i);
            }
        }
        for (int i = 0; i < max_index.size(); ++i) {
            flag[max_index[i]] = 1;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += flag[i];
    }
    cout << ans << endl;
    return 0;
}

  2. 给a,b,x,m四个数，给定递推式 x=(a*x+b)%m，这个x不停算会循环，问递推第几次起x开始循环。

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

    #include <iostream>
#include <vector>
using namespace std;
    
int main() {
    long long a, b, x, m;
    int cnt = 0;
    cin >> a >> b >> m >> x;
    vector<int> flag(m);
    while (true) {
        x = (a * x + b) % m;
        if (flag[x] == 1) {
            cout << cnt << endl;
            break;
        }
        flag[x] = 1;
        ++cnt;
    }
    return 0;
}

  3. 给定n个数，这n个数两两结合构成一共n^2个有序数对（i， j）（可以自己和自己构成有序数对）。给定k，求第k大的有序数对是哪一个。例如给定1，2，2那么9个有序数对应该是：

    （1，1）（1，2）（1，2）

    （2，1）（2，2）（2，2）

    （2，1）（2，2）（2，2）

    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

    #include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
    
int main() {
    int n;
    long long k;
    vector<int> data;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        int tmp;
        cin >> tmp;
        data.push_back(tmp);
    }
    sort(data.begin(), data.end());
    long long a = (k - 1) / n;
    long long l = 0, row = 0;
    while (data[l] != data[a]) ++l;
    while (data[l+row] == data[a]) ++row;
    long long aa = (k - l * n - 1) / row;
    printf("(%d,%d)", data[a], data[aa]);
    return 0;
}

  4. 给定有序数列伪中位数的定义，m=a[floor((n-1)/2)]， 给定一个数列，和一个值k，问至少添加几个数，使得该序列的伪中位数等于k。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <iostream>
using namespace std;
 
int main() {
    int n, k;
    cin >> n >> k;
    int cnt_big = 0, cnt_small = 0, cnt_equal = 0;
    for (int i = 0; i < n; ++i) {
        int tmp;
        cin >> tmp;
        if (tmp < k) ++cnt_small;
        else if (tmp > k) ++cnt_big;
        else ++cnt_equal;
    }
    cout << max(max(cnt_small - cnt_big + 1, cnt_big - cnt_small) - cnt_equal, 0);
 
    return 0;
}

  1. 给两个字符串s,t，求s的子串与t的子序列相同的情况有多少种。

    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

    #include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
    
const int M = 1000000007;
int f[5001][5001], ns, nt;
string s, t;
    
int main() {
    cin >> s >> t;
    ns = s.size();
    nt = t.size();
    
    unordered_map<char, int> cnt;
    unordered_map<char, vector<int>> value;
    for (int j = 1; j <= nt; ++j) {
        char tt = t[j-1];
        cnt[tt]++;
        if (value.find(tt) == value.end()) {
            value[tt].resize(ns+1);
        }
        for (int i = 1; i <= ns; ++i) {
            char ss = s[i-1];
            f[i][j] = cnt[ss];
            if (value.find(ss) != value.end()) {
                f[i][j] = (f[i][j] + value[ss][i-1]) % M;
            }
            value[tt][i] = (value[tt][i] + f[i][j-1]) % M;
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= ns; ++i) {
        ans = (ans + f[i][nt]) % M;
    }
    cout << ans;
    
    return 0;
}
FEATURED TAGS
attention pytorch scene segmentation