实习与工作|算法

VMWare 沙龙 Coding 挑战赛

凝神长老 · 3月12日 · 2019年 · · · 864次已读

本文写于 2019年03月12日,距今已超过 1 年,距 2020年03月27日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


3 月 12 日晚上去交大闵行校区参加了 VMWare 的沙龙,后面有一个现场 Coding 挑战赛,1 个小时,3 道题,我一题都没做出来,或者更明确的说法是,我都知道考什么知识点、也都写了,但是由于各种各样的问题,每道题都只通过了部分 Case 拿了部分分,没有任何一题是成功 AC 的。

博弈论。

思路完全错误了。

后来知道正解是,只要是偶数就一定是后手胜利,因为后手可以完全仿照先手的做法。

对于奇数,如果先手能够成功处理木头的分隔到不可拆分,那么先手胜利,因为那么剩下是偶数根木头,而先手已经成为后手。

特别要注意长度为质数,而最短分隔 k = 1 的情况。

显然贪心不成立。

动态规划。

没写出来。

后来知道正解是,A 的策略是最大化 A – B 的差值,B 的策略是最小化 A – B 的差值。

计算 f[L, R] 表示在一个区间之内考虑,分别对 A 和 B 选取最佳策略,令 Fa[L, R] 取 max, Fb[L, R] 取 min。


维护每个点的入度,入度为零,删掉,并删除相连的边和点,如此遍历,直到所有点被删除,得到唯一的答案。

需要注意维护的过程,小心不要超时,例如不能暴力枚举。

然后我做的时候,没有超时这个问题,反而是内存超过限制,不知道是不是开了太大的数组,或者是我用的语言是 Java 的缘故。

VMWare 这场沙龙的 Coding 赛的题目还是有点难的,但是质量一般,因为,见过一次,就一定会做,没见过就是很难在一个小时之内想出来,所以,我说题目质量差,是因为不能体现每位同学自己思考的水平,只要见过一次类似的题,知道结论,很快就能写对,十分钟/题都没问题,所以不适合作为现场挑战赛。而且事后看出题人的轻浮的样子,估计也没有好好选题和验题。

不过,礼品还是不错的。虽然都是无用玩意。

0 0 投票
文章评分
订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论