华为暑期实习软件开发笔试复盘

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 2k 阅读时长 ≈ 2 分钟

声明：本文只是本人笔试后对试题的复盘反思，从未由此牟利.如侵犯任何一方权利，请通过本站提供的联系方式联系本人，本人将立刻删除本文。

3月30号大清早，正准备出门去北京植物园春游，就收到华为HR消息，说3月31号笔试...不过还是去春游了，玩了一天:-)

虽然上周就知道会有笔试，也稍微复健了一下，但最近实在太忙了，基本等于没复习。昨晚到牛客网练了一下输入输出，今天上午去公司忙项目，中午回学校把图形学作业的收尾工作写完、写了报告交了作业，之后上法语课，课后还和同学编排了下节课的对话。晚饭吃了个水煮肉，这就该回宿舍开始考试了。

一共三道题两小时，自己处理IO，经典套路，第一题水题，第二题看起来花哨实际很简单，第三题是个很传统的DP，可以说中规中矩吧，甚至有点偏简单？但对于一向算法题废物还毫无准备的我，今天提前挺久做完了也是挺意外。

第一题：足球循环赛

输入比分

1
2
3
A-B 1:2
B-C 3:0
...

胜得3分，平得1分，负得0分。最终输出排行榜和积分

1
B 6,A 0,C 0...

对于写Python的我，实在是水题...但是遇到了两个意外情况（一看就是平时不刷题）。首先是我习惯读这种不知道多少行输入时用ErrorEOF控制，但牛客网似乎把异常直接接管了...还好昨天练了一下IO，改成了

1
2
3
import sys
for line in sys.stdin:
    pass

另一个更可笑了，卡了我十多分钟的问题竟然是我忘了sorted怎么传参了...key和reverse都必须用keyword传入，不能用位置传。还好可以用自己的IDE，我倒是真没有Python IDE，就在VS Code的terminal里打开Python，用help(sorted)看了一眼才想起来...

第二题：有多少人来party

没见过的新奇问题。输入一个list如[1,2,1]，每个数字是一个人报告的party上和自己戴的帽子颜色相同的人数。只有部分人报告了。求party至少来了多少人。

其实很简单，如果一个人报告了1，那么这个颜色一共也就2个人。那么如果有三个1，说明至少有两种不同颜色都各有2个人。所以考场上想到的一个方法是把list排个序，然后给数字加括号：

1
(1,1),(2)

每组括号是一个颜色，所以例子里有两种颜色，颜色A有2个人，颜色B有3个人（尽管其中只有1个人报告了）。

这样的复杂度是\(O(n\log n)\)，因为要排序。但交了卷吃夜宵的时候回想这个问题，其实根本不用排序，本质上就是个往桶里扔球的问题。报告的每个unique的数字是一个桶（i表示有i+1个人同一种颜色），扔完所有球以后，如果桶i有n个球，那么这个桶可以分成\(ceil(\frac{n}{i+1})\)组，一组是一种颜色，这个桶至少代表了\((i+1) \times ceil(\frac{n}{i+1})\)人。

所以又用哈希表（Python的dict）重写了一遍，只用10行代码左右就能写完...复杂度降到了\(O(n)\)。

第三题：游标寻找字符

给定一个字符串src，一个目标字符串dst，和指向src中某字符的游标的起始位置pos。游标可以左右移动，每次一步，最左边往左一步可以到最右边，最右边同理（循环数组）。现要用游标在src中依次找到dst中所有字符，求最少步数。

一开始很intuitively想用greedy，但是转念一想这么明显的坑...随便找了个例子就发现greedy肯定不行，比如

1
2
3
src: axxxxxxxyzby
pos:          ^
dst: ya

应该先找最右边的y，但greedy会先找z左边的y。那自然是DP了。递推关系式很简单：

\[\text{min_step}(j,i)=\min_{p:src[p]=dst[j]}\left\{\text{min_step}(j+1,p)+\text{loop_dist}(i,p)\right\},\]

其中\(i\)表示当前游标在src中的位置，\(j\)表示下一个要匹配字符在的dst中的位置。loop_dist表示在循环游标设定下两点的距离。

一个技巧是先扫描一遍src串，记下每个字符出现的所有位置，以此决定上式中求\(\min\)时\(p\)的范围。

DP有两个变量，复杂度是\(O(mn)\)，\(m,n\)分别表示src和dst的长度。

写在最后

用Python写这些东西其实真的很简单。比如DP可以直接搞个dict当memory，用\((i,j)\)二元组当key就行，传统写C/C++一般会开个二维数组来存。当然当代C++鼓励大家多用STL，那么std::map之类的用起来应该也挺方便。但不得不说，同样的东西，用C++来写总会长一点，而且C++时间要求相对更严格（也可能是更宽松了？不知道开O3的C++ 11到底能比Python 3.9快多少倍...），感觉还是写Python更轻松一点。