面经 - 吉比特 引擎开发实习生 笔试 240425

时间线

流程概况

240425 笔试

应该都写出来了，个别问题存疑。

240527

拒绝了面试邀约，因为这段时间没什么时间。

笔试

Part1 选择题

回忆几道印象深刻的题，其余部分概括一下。

• 甲乙丙丁戊其中四人发言说 “XX 是我的 XX (亲戚) 的 XX (亲戚)”，请问谁未发言。（岳母和女婿是啥来着…）

• 有三个小组各 10 / 15 / 25 人，其中女生 3 / 7 / 5 人，问随机从其中一个组选两人，已知后选出的为男生，则先选出为女生的概率？

  $A.~\frac{1}{3};~~B.~\frac{2}{9};~~C.~\frac{20}{61};~~D.~\frac{29}{90};$ （完全不会，五次算出五个答案，没一个在选项里）

• 一副扑克 54 张，均分 3 副，一副 18 张。问大小王在同一人手中的概率是多少？（吉比特你超爱考概率啊！）

剩余一道读代码题：本质是数二进制 $1$。

两道时间复杂度分析，余下都是些计算机基础选择题，和大学考试题有点像。

Part2 填空题

• 大小端与 gcd，读代码填输出。
• 奇怪赋值、引用、指针，读代码填输出。

聪明点，把代码抄下来放到 Part3 跑一下…

Part3 编程题

球赛综合排名

已知多场球赛所有选手排名序列，根据拿到第一名、第二名… 的次数排名选手；如果选手并列，按字典序输出姓名。具体而言，选手 A 比选手 B 排名好，当取得第一名的次数比选手 B 更多，或取得第一名次数一样多而取得第二名次数更多，或前面同等条件取得第三名次数更多… 忘记数据范围了，别太蠢应该都行。

两端取数博弈

给定一个序列，A 和 B 从两段取数，可以选择一端，然后从该端拿走至少一个数，取到空游戏结束。游戏结束时，两人比手上拿到的数之和的差，然后可以从对方手上赢取相应的筹码。取到的数可能是负数，数据范围 $N \le 100$。

不考虑优化，$O(N^3)$ 的区间 $dp$：

$$dp[l][r][w] = \max\left\{\begin{array}{ll} \sum_{j=l}^{r}{a[j]}\\ \sum_{j=l+1}^{r}{a[j]} - dp[i][r][1-w] & ,~l < i \le r \\ \sum_{j=l}^{r-1}{a[j]} - dp[l][i][1-w] & ,~l \le i < r \\ \end{array}\right.$$

$dp[i][j][w]$ 表示当前数字为 $a[l..r]$ 的状态下，玩家 $w$ 比对手最多多多少筹码。应该可以单调队列优化为 $O(N^2)$。

去除一点的 MST

单独召唤精灵 $i$ 的代价为 $a_i$。不过如果两种精灵存在吸引力，你可以花费 $b_{i,j}$ 的代价通过精灵 $i$ 召唤精灵 $j$，这样做的前提是你已经召唤了精灵 $i$。已知并非任何精灵间存在吸引力，但如果存在总有 $b_{i,j}=b_{j,i}$。请问集齐其中任意 $n-1$ 种精灵的最小代价。数据范围 $N \le 150$。

本质是个图论问题。将精灵间吸引力关系连边，这是个无向图。然后把召唤者当精灵 $0$，用单独召唤代价与其他精灵连边。问题转化为去除任意一个点（$0$ 除外）的最小生成树。

解法有三：

• Prim 从 $0$ 开始，只剩一个点时结束。复杂度 $O(N^2)$。
• Prim 采用堆优化。复杂度 $O(MlogN)$，$M \le \frac{N(N-1)}{2}$。
• Kruskal 枚举去除的点，每次重跑。复杂度 $O(NM+MlogM)$，$M \le \frac{N(N-1)}{2}$。

方法一最优秀，不过当时我用的方法三，因为平时写 Kruskal 比较多。