阿里工程研发实习笔试2023-04-03

还记得20年做阿里的笔试题,一个是普通 BFS,一个是普通 set,两三百百刷题量就可以秒杀。

但现在,不仅难度提升,题量还变大,而且还增加了考点巨细无比的选择题。

时过境迁,校招笔试题已经卷到如此地步了,不得不让人唏嘘....

T1 黄牌警告,红牌下场

一个球队有n个球员,已知他们一共接受了x张黄牌,y张红牌。

当一个球员满足以下条件之一时会立刻下场:

1. 接受了2张黄牌

2. 接受了1张红牌

请问已知以上信息的前提下,当前能上场的球员最多有多少人?最少有多少人?共有q次查询。

q <= 1e4, 1 <= n <= 1e9, 0 <= x, y <= 1e9

输入:

4

2 2 1

3 2 0

3 0 2

1000000000 0 0

输出:

1 0

3 2

1 1

1000000000 1000000000


最少很好算,n - int(x / 2) - y 即可。

最大的情况是:将黄牌尽可能的发个每一个人,然后剩余的 x - n 张发给没有发红牌的人(n - y 个里面选择 x - n 个)。

T2 矩阵染色问题

给定一个n行m列的矩阵,其中一些方格被染成了红色,其余方格为初始的白色。

现在定义 f(i, j) 为:若将第i行、第j列的方格染白,当前矩阵的红色连通块数量。

请你求出每个 f(i,j) 的值。

1 <= n,m <= 40


暴力枚举每一个方格,修改后求红色连通块个数(DFS)。求解连通块个数可以参考:https://leetcode.cn/problems/number-of-islands/description/

复杂度 O(n^2m^2)。

T3 权值不超过 k 的连续子数组数量

我们定义一个数组的权值为:所有元素乘积的因子数量。例如,[2,6]的权值为6,因为2*6=12,12有6个因子:11,2,3,4,6,12}

现在给定一个数组,试求该数组有多少连续子数组的权值不小于K?

1 <= n, a_i <= 2e5, 1 <= k <= 1e9


所有元素的乘积的因子数量与质因数分解后的指数有关。

一个数 x 可以被分解为若干个质因数的乘积:

x = p_1^{c_1} \times p_2^{c_2} \times \cdots \times p_k^{c_k}

它的因子个数是:

(c_1+1)\times (c_2 + 1) \times \cdots \times (c_k+1)

所以,我们通过滑动窗口维护其中所有数字乘积的质因数的指数(用一个数组或哈希表),同时维护因子数量(cnt)。

对于每个右端点 i,维护最小的左端点 j,使得 [i,j] 乘积因子数目小于 k。那么对于 i 来说,共有 j 种方案满足要求,例如 [0, i], [1, i], ... [j-1, i]。

时间复杂度为 O(n\sqrt n),主要是质因数分解的复杂度。

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    unordered_map<int, int> mp;
    ll cnt = 1, res = 0;
    auto addv = [&](int x, int t) {
        for (int i = 2; i * i <= x; i++) {
            while (x % i == 0) {
                cnt /= (mp[i] + 1);
                mp[i] += t;
                cnt *= (mp[i] + 1);
                x /= i;
            }
        }
        if (x > 1) {
            cnt /= (mp[x] + 1);
            mp[x] += t;
            cnt *= (mp[x] + 1);
        }
    };
    for (int i = 0, j = 0; i < n; i++) {
        cin >> a[i];
        addv(a[i], 1);
        while (j <= i && cnt >= k) {
            addv(a[j], -1);
            j++;
        }
        res += j;
    }
    cout << res << "\n";
}
#笔试##软件开发2023笔面经##阿里#
今夕的求职日记 文章被收录于专栏

记录2023年-2024年的笔试、面试问题~

全部评论
想问下第一问的代码时类似这样的吗 public static void query(int n, int x, int y) { int min, max = 0; min = n - y - x/2; int yellowRemain = Math.max(0, x - n); max = yellowRemain + n - y; System.out.println(max + " " + min); }
点赞 回复 分享
发布于 2023-08-05 23:56 美国
第三题厉害了,我还以为连续子数组是必须要从0开始的子数组呢
点赞 回复 分享
发布于 2023-04-05 15:10 湖南
捞简历,杭州-阿里巴巴-淘菜菜技术部,不泡池子,欢迎私信
点赞 回复 分享
发布于 2023-04-04 18:00 浙江
打个广告,阿里巴巴数字供应链2024届实习生正在急招,欢迎来撩
点赞 回复 分享
发布于 2023-04-04 16:29 浙江
第三题思路真妙啊,只想到了暴力解,还能这样用滑动窗口
点赞 回复 分享
发布于 2023-04-04 15:51 四川
up主太强了,最后一题看到的时候,完全没思路
点赞 回复 分享
发布于 2023-04-04 09:40 广东
太强了
点赞 回复 分享
发布于 2023-04-04 03:17 江苏
优秀
点赞 回复 分享
发布于 2023-04-04 00:04 辽宁

相关推荐

07-15 16:52
已编辑
门头沟学院 Java
周五投的,流程今天结束
投递地平线等公司7个岗位
点赞 评论 收藏
分享
彧未sr:查看图片
投递牧原集团等公司7个岗位
点赞 评论 收藏
分享
06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
评论
14
50
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务