快手游戏客户端秋招一二面面经

一个都不会，现在没改简历志愿吗，我想投运营岗了，编程不适合我

1,2过了，3 12%.4 72%，完了，第三题看错题目了，以为拿到的能源可以用作燃料，反应过来时已经来不及了

ttl： 3.19一面，23约二面（拿了铁厂的offer拒了一面面经：全程一个小时双机位，必须露出屏幕和手，高柱那个支架调了半天，面试官对这个还蛮严格的1️⃣实习经历拷打（没问项目经历，先自己介绍然后面试官又挑了几个简历上写的问了2️⃣八股1.常用的数据结构2.ArrayList的增删改查的时间复杂度3.ArrayList的扩容机制4.证明ArrayList新增元素的时间复杂度，答案直接背出来了，但是不会证明（到这里高柱已经疯了，面试官说要从上界和下界分别证明，磕磕绊绊勉勉强强套出来个答案3️⃣手撕统计所有满足子串元素和 = 0的子串个数（秒了面试官说再问一道，题目出了就是上面的升级版，0换成n，但是又说时间到了，就结束了高柱以为完蛋了但是过了，不过拿了offer了就没继续推流程，还是很感谢多多的，笔试高柱就a了1.2也给我进面了新进群的同学可以看一下我历史笔试&面经 *****************************************准备好了再投递，内推链接：https://careers.pddglobalhr.com/campus/intern?t=vSypT8yAuQ 内推码：vSypT8yAuQ

T1 大分讨,不过没太讨论清楚T2 不会ML，oh noT3 先容斥变成求解长为m,取值[1,v] 总和为k的数组，考虑用如下的生成函数描述总和为k的个数：[x^k] (\frac{x *(1-x^v)}{1- x})^m= [x^{k - m}] (1-x^v)^m  \cdot  (1-x)^{-m}前者二项式系数展开，后者牛顿二项式系数展开，枚举前一项x的系数为x^{iv}, 可得：ans = \sum_{i = 0, r = k - m - iv}^{iv \leq k - m} (-1)^i C(m, i) C(m + r - 1,r)最后ans <-   v^n - ans 即可, 注意n根据费马小定理要对P - 1取模，或者直接传i64复杂度O(\sum m + log P)T4, 一个基环树，考虑将答案拆为3部分：1. 链， 2. 若干次整个环， 3 部分环我们先通过dfs求得基环树的环和链，用倍增维护链上的父节点和其他信息，复杂度O(nlogn)1.如果k > 链长，直接跳到根节点，进入2部分否则，倍增上跳的过程中求和即可，O(log n)2/3 若环长为len，还剩k步，则我们走x = k / len个整环，y = k % len 一部分长的环于是贡献就是 x(x+1)/2 * all(circle) + (x + 1) * getcir(p, p + y - 1), 求解这部分是O(1)的总复杂度是O(nlogn + qlogn)可惜T4 赛后才调完