春招-笔试分享

字节跳动的笔试记录是最详细的，但是也是唯一一个没有成功的。

今天带来的一手笔试题目难度各异，分别来自美团、阿里和华为。总体来说，阿里的题目数据量大、用时紧张，很难完整得出结果；美团的题目较多，但上手也比较容易；华为题目虽然相对简单，但是输入输出的数据格式非常糟糕。

下面对部分留下记录的题目进行简单分析：

1. 阿里笔试

比较难，关键感受：测试用例非常完整，很难通过用例，一个测试用例都没有过。

1）牌游戏问题

题目描述：n副牌，每副有m张（就是1到m），每副牌中抽1张，问相加之和为k的抽取方案有多少种？

给出的测试例会有T组，需要一下子给出他们的结果。

这道题似乎在Leetcode上找到了近似的题目，ta的解决方法是概率的方法

2） 零件优化问题

题目描述：n个零件，对每个零件进行一次空间 或 时间优化（二选一，且必选），每种优化带来的不稳定值不同

这些零件中，有的零件之间会有冲突，总计 m 条冲突，冲突零件不可组合

请找到最佳组合方案，要求不稳定值最小。

思路：这道题相比1）题其实可解性稍高，比如可以使用并查集的方式建立零件之间的联系（两种联系，一是冲突问题，二是不稳定值之和），然后寻找最小的不稳定值。

其他笔试

在早期的阿里云笔试中，题目是二叉树的中序遍历问题

在一棵二叉搜索树中，找到第 k 小的数字

2. 美团笔试

一共5道题，难度适中，可解性比较高。

1）积木问题

题目描述：

共有n块积木，每个积木上写了一个数字（0-9之间的数字）。

可以任一将其中一块积木换成其他数字，希望更换后的数字串特点是：

1）回文最好

2）越小越好

不能回文，就越小越好。

输出：最佳的积木更换方案后的情况。

思路：

1）首先需要检查是不是回文，用双指针前后移动，观察到某一位是不是相同，如果不同，试图更换积木，看更换后是不是回文，仍然不是，那么特点1）无望，就换成更小的积木

2）直接从最高位开始，不是0的那一位换成0，就是最小的

现在看来，当时的解法有瑕疵，回文的检查做了两次，其实只需要一次就可以了，更换数字放在中间，然后继续检查就可以了

这道题过了72%的样子。

2）打龙技能问题

题目描述：

在一个游戏中要打龙，有两种技能 1和2，分别需要消耗 c1 和 c2 点体力，使用任意一种技能都可以打败龙。

赢得游戏的要求是，不能连续输3局。

现在给出一串字符串，T和F，表示不用技能的情况下每局的输赢情况。

现在问，最少需要多少点体力，才能赢得游戏？

思路：

这道题的难度应该说很低了，贪心法。

就是从头开始遍历，输的次数累计到3，自然就要用一次技能，计算需要使用技能的最少数量；

两种技能中选择消耗体力比较少的那一种，就可以了。

这道题似乎是全过了。

3）爬树问题

题目：有n棵树，高度分别为 $h_i$

现在要选择一棵树，作为分界点：

• 所有奇数树给一队
• 所有偶数树给另一队

注意：奇偶数是在去除选择的这棵树之后的顺序来计算的！！

要求：找到合适的位置，使得两队的高度应该一致，无法一致就返回false

思路：

这道题我用了前缀和的方法，首先遍历一遍所有树，记录到每一棵树的位置，前面的所有树中奇数和偶数树的高度。

然后遍历位置，以每个位置分界

所有奇数树：该位置前的奇数树+该位置后的偶数树

所有偶数树：该位置前的偶数树+该位置后的奇数树

这个题就是这个索引比较头大，最后似乎通过了82%

---

还有两道题，题目已经不太记得了，通过率均为18%，进入面试环节。

面试题目 - 大数加减法

也就是计算器算法的实现

3. 华为笔试

1） 球赛积分问题

足球小组赛中，通常是两两进行两次比赛，分别当一次主场，然后赢方积3分，平则各积1分

给出一组比赛结果，记录了所有场次比赛的信息

其中球队名称为 a-z 的字母，不会超过26支球队

然后后面跟上比赛结果

输出要求：按照积分高低输出球队名，同积分则按照字母顺序

我的思路：

1. 本题用一个哈希表，或者字典就能很好解决积分计算的问题
2. 最关键的算法是字典的排序，要按照value大小进行排序

问题：

1. 本题在牛客网上进行时，还有一个问题是输入输出的格式问题，不是很规范，需要进行很多转换
2. 字典的键的排序比较糟糕

本题通过70%

2）帽子问题

每个人知道自己的帽子颜色，和在场所有人的帽子颜色

现在给出一个数组，里面记录了部分人报告的数据，该数据表示在场人中帽子颜色和他相同的人的数量

比如在场有4个人戴了蓝色帽子，那么其中任一人被问时，回答都会是 3：表示还有3个人的帽子和自己颜色相同。

问：根据这个数组，在场最少有多少人。

这个逻辑问题的关键是：比如两个颜色的帽子数量是相同的，那么这两个群体中所有人回答的数量都是一样的，如果这两个群体中的人并没有被全部提问，那么我们就可以少算几个人了！

比如2 2

有可能是 两个人颜色并不一样，但我们完全可以认为他们是一样的，这样全场最少就是3个人。

因此，本题的算法应该可以认为是贪心法，用数学方法解决：

用一个哈希表记录相同数字的数量，比如

1: 2	# 2个人答1
2: 2	# 2个人答2
3: 5	# 5个人答3

那么，相当于：

2: 2	# 二人同色，2人
3: 2	# 三人同色，2人
4: 5	# 四人同色，5人

最少的情况就是：

$[\frac{记录数量}{同色人数}]_{取整}*同色人数$

比如：$[\frac{5}{4}]_{取整}4=24=8$，这里取整要向上取整

本题全过。

3）最少步数找到字符串

给出：一个长字符串、一个短字符串、在长字符串中的起始位置

要求：在长字符串的起始位置开始，可以向左或者向右开始找短字符串的头一个字符，然后按照顺序找下一个短字符串中的字符，找出总步数最少的那一种情况输出。

本题还是有一点难度的，就是说我应该怎么找最短的路径，而且本题中的长字符串是可以循环的。

结果：本题通过30%

面试题目

LeetCode - 11 装水的最大容器问题

小结

本文主要是作者个人知识积累和记录，以便后续查看，如果能够帮助其他同学，将不胜荣幸。希望能够继续努力，夯实基础，在职业生涯大放异彩！