面经 - 吉比特 引擎开发实习生 笔试 240425
时间线
流程概况
240425 笔试
应该都写出来了,个别问题存疑。
240527
拒绝了面试邀约,因为这段时间没什么时间。
笔试
Part1 选择题
回忆几道印象深刻的题,其余部分概括一下。
-
甲乙丙丁戊其中四人发言说 “XX 是我的 XX (亲戚) 的 XX (亲戚)”,请问谁未发言。(岳母和女婿是啥来着…)
-
有三个小组各 10 / 15 / 25 人,其中女生 3 / 7 / 5 人,问随机从其中一个组选两人,已知后选出的为男生,则先选出为女生的概率?
(完全不会,五次算出五个答案,没一个在选项里)
-
一副扑克 54 张,均分 3 副,一副 18 张。问大小王在同一人手中的概率是多少?(吉比特你超爱考概率啊!)
剩余一道读代码题:本质是数二进制 。
两道时间复杂度分析,余下都是些计算机基础选择题,和大学考试题有点像。
Part2 填空题
- 大小端与 gcd,读代码填输出。
- 奇怪赋值、引用、指针,读代码填输出。
聪明点,把代码抄下来放到 Part3 跑一下…
Part3 编程题
球赛综合排名
已知多场球赛所有选手排名序列,根据拿到第一名、第二名… 的次数排名选手;如果选手并列,按字典序输出姓名。具体而言,选手 A 比选手 B 排名好,当取得第一名的次数比选手 B 更多,或取得第一名次数一样多而取得第二名次数更多,或前面同等条件取得第三名次数更多… 忘记数据范围了,别太蠢应该都行。
两端取数博弈
给定一个序列,A 和 B 从两段取数,可以选择一端,然后从该端拿走至少一个数,取到空游戏结束。游戏结束时,两人比手上拿到的数之和的差,然后可以从对方手上赢取相应的筹码。取到的数可能是负数,数据范围 。
不考虑优化, 的区间 :
表示当前数字为 的状态下,玩家 比对手最多多多少筹码。应该可以单调队列优化为 。
去除一点的 MST
单独召唤精灵 的代价为 。不过如果两种精灵存在吸引力,你可以花费 的代价通过精灵 召唤精灵 ,这样做的前提是你已经召唤了精灵 。已知并非任何精灵间存在吸引力,但如果存在总有 。请问集齐其中任意 种精灵的最小代价。数据范围 。
本质是个图论问题。将精灵间吸引力关系连边,这是个无向图。然后把召唤者当精灵 ,用单独召唤代价与其他精灵连边。问题转化为去除任意一个点( 除外)的最小生成树。
解法有三:
- Prim 从 开始,只剩一个点时结束。复杂度 。
- Prim 采用堆优化。复杂度 ,。
- Kruskal 枚举去除的点,每次重跑。复杂度 ,。
方法一最优秀,不过当时我用的方法三,因为平时写 Kruskal 比较多。