2022 年 4 月 10 日拼多多笔试

​ 不得不说，拼多多的这些题目我觉得出的挺好的，能感觉到难度梯度的变化，而且我觉得难度设置也比较合理（没有出现像华为 6 日的题目那样，第一题让很多人感到不舒服，以至于影响后面的做题节奏）。

​ 拼多多一共 4 到编程题，最终 ac 了三道，最后一道考场上没有想到解法，做完之后居然一小会儿就想到了思路（考场上专注于想贪心的做法，对于动态规划的思路没有认真思考）。

第一题：

​ 靠，因为花的时间少，忘了，但是还是比较简单的，希望有同学补充上来。

第二题：

​ 在棋盘上求从起点出发按照 “马走日” 的方法，到达终点的最小步数，其中增加了棋盘中的障碍和 马脚被堵 两个限制。

​ 典型的 BFS 求棋盘上的最小步数的问题，基本上只要正常按照 BFS 的思路不会有太大的问题，主要注意的是代码中的一些细节问题。

第三题：
M 个座位， N 个被占用，q 次查询，每次一个区间，查找区间 [l, r] 为被占用的最小的座位编号。 本质是求解一个有序列整数序列中未出现的最小的数的问题，其中的座位总数是一个干扰项。

​ 用二分法解决，先对 N 个座位数组 vec 编号排序，然后求出其中大于等于 l 的最小的下标 s 和 小于等于 r 的最大的数的下标 e。

​ 对特殊情况做完判断之后，本质就是求解有序序列 vec[s : e] 中第一个不连续的整数，采用二分法进行求解。

第四题：

​ 考场上没有做出来，下来之后想到了一个思路，应该没有问题，希望大佬们一起交流一下，先对货物到达时间排序为 times：
​ 则：

​ 感觉这种做法应该 ok，但是考试的时候直接往贪心去想了，淦，结果啥都没想到，感觉心有不甘，这个动态规划的思路应该并不算难。

总结：

​ 拼多多的题目出的还可以，难度梯度设置比较合理。但是做题的时候的心态还是没有刷题的时候放松，思路打不开。

​ 希望能进面试，大家加油。