8月2日拼多多笔试复盘

前言

人生第一次大公司的笔试,感觉自己还是比较缺少经验,这里记录下好好反思吧。

走飞行棋

题目只能自己大约回忆一下了。给定一个距离终点的举例distance和一个count,然后跟着的是count个数字,这些数字代表了你在飞行棋走的步数。

问如果中间有一次能够走到终点,就打印“paradox”,如果不能走到终点,就返回抵达过终点多少次。

这道题有两个坑,第一个比较容易发现,就是上来distance就是0,那么就说明不用走,直接输出“paradox”即可。

第二个我到最后都没发现,看网上的解析才发现的,如果是最后一次到达,那么就不输出“paradox”。我感觉应该是玩了文字游戏吧,比较违反常规。不过好在这个坑倒我记得只占了4%还是2%,所以不影响。

代码我忘记记下来了,事后补一个类似的吧:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int distance = in.nextInt();
int count = in.nextInt();
int[] array = new int[count];
for (int i = 0; i < array.length; i++) {
array[i] = in.nextInt();
}

// 边界条件判断,题目确保大于等于0
if (distance == 0) {
System.out.println("paradox");
}
int result = 0;
for (int i = 0; i < array.length; i++) {
if (distance > array[i]) {
distance = distance - array[i];
} else if (distance == array[i]) {
System.out.println("paradox");
return;
} else {
distance = array[i] - distance;
result++;
}
}
System.out.println(distance + " " + result);
}
}

10 3

6 1 3

给定的测试数据这样,按照我们平时下棋的理解,距离是10,而最后刚好走到了,应该输出的是paradox,但是本题应该输出3 0,表示还差3步走到,到过终点0次….就让人很无语…..

旋转骰子

给定一个骰子,我们按照上下左右前后这个顺序来输出它的六个面。首先给定N和N组六个面的数值,有一些顺序是可以通过一个骰子旋转得到的,那么判断这N组数据是由几种骰子扔出来的,并将这些骰子按照顺序输出出来。

思路1

首先我先在ipad上画了一个立体图,然后马上就能发现一个规律:一个骰子的对面的两个数,必定是固定的,无论你怎么转。比如[1,2,3,4,5,6]这个骰子顺序,我们把这个数组按照两两分成一组,这样1和2必定会在第一组第二组或者第三组中的其中一个,不可能是[x,1,2,x,x,x]这种。

然后我想出了两种办法:

  • 第一种是我遍历所有的骰子的所有旋转可能,然后我只需要对测试数据进行判断即可。首先我脑子里过了一遍这个的复杂度:一共也就6!种可能性,完全可行。但是…要我手写全排列,我有点忘了怎么写…遂放弃…
  • 第二种就是用一个list把数组存起来,然后每次读到一组数字就和list中的每组进行判断,如果相同则说明是同一个,直接把结果+1并不需要放入。如果不相同则需要放入。

我在第二个里面扎了1小时,然后去试试,就过了10%…..核心函数见下(ps:只有思路,有一些return我实在不想推了,忘记记录笔试的答案了):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static boolean judgeSame(int[] a, int[] b) {
// 分成六组
if (a[0] == b[0] && a[1] == b[1]) {
// 对2345四个位置进行判断
return helper(a[2], a[3], a[4], a[5], b[2], b[3], b[4], b[5]);
} else if (a[1] == b[0] && a[0] == b[1]) {
// 对2345四个位置进行判断
return helper(a[2], a[3], a[4], a[5], b[2], b[3], b[4], b[5]);
} else if (a[2] == b[2] && a[3] == b[3]) {
// 对0145四个位置进行判断
return helper(a[0], a[1], a[4], a[5], b[0], b[1], b[4], b[5]);
} else if (a[3] == b[2] && a[2] == b[3]) {
// 对0145四个位置进行判断
} else if (a[4] == b[4] && a[5] == b[5]) {
// 对0123四个位置进行判断
return helper(a[0], a[1], a[2], a[3], b[0], b[1], b[2], b[3]);
} else if (a[5] == b[4] && a[4] == b[5]) {
// 对0123四个位置进行判断

} else {
return false;
}
}

可以看到就是分成了6组,其实是三组,但是因为可以颠倒一下,然后有六组。每一组再用函数进行判断,后来发现就是这个helper写错了….

笔试结束之后,我感觉这种方法是可行而且速度很快:生成全排列,然后固定其中的一对,比如我就固定好上下这两个面,对一个进行旋转四次,最多最多也只有4*6!种可能性。

对于一个骰子有9种不同的可能性,我这边弄了一个函数来打印:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
private static int[] rotate(int[] array, int count, int mode) {
// mode取值有三种,1代表固定前两位,2代表固定中间两位,3代表固定最后两位
// count取值有四种种,1代表转一次,2代表转2次,3代表转3次,0和4都意味不旋转,所以只需要一个
int[] copy = new int[6];
if (mode == 1) {
copy[0] = array[0];
copy[1] = array[1];
switch (count) {
case 0:
return array;
case 1:
copy[2] = array[4];
copy[3] = array[5];
copy[4] = array[3];
copy[5] = array[2];
return copy;
case 2:
copy[2] = array[3];
copy[3] = array[2];
copy[4] = array[5];
copy[5] = array[4];
return copy;
case 3:
copy[2] = array[5];
copy[3] = array[4];
copy[4] = array[2];
copy[5] = array[3];
return copy;
default:
return null;
}
}
if (mode == 2) {
copy[2] = array[2];
copy[3] = array[3];
switch (count) {
case 0:
return array;
case 1:
copy[0] = array[4];
copy[1] = array[5];
copy[4] = array[1];
copy[5] = array[0];
return copy;
case 2:
copy[0] = array[1];
copy[1] = array[0];
copy[4] = array[5];
copy[5] = array[4];
return copy;
case 3:
copy[0] = array[5];
copy[1] = array[4];
copy[4] = array[0];
copy[5] = array[1];
return copy;
default:
return null;
}
}
if (mode == 3) {
copy[4] = array[4];
copy[5] = array[5];
switch (count) {
case 0:
return array;
case 1:
copy[0] = array[3];
copy[1] = array[2];
copy[2] = array[0];
copy[3] = array[1];
return copy;
case 2:
copy[0] = array[1];
copy[1] = array[0];
copy[2] = array[3];
copy[3] = array[2];
return copy;
case 3:
copy[0] = array[2];
copy[1] = array[3];
copy[2] = array[1];
copy[3] = array[0];
return copy;
default:
return null;
}
} else {
throw new IllegalArgumentException();
}
}

当时我做的时候觉得没有什么问题,但是只过了10%的case。

思路2

这次从另外一个角度来说,如果为立方体的6个面分别印上1-6,使之成为骰子,那么有多少种这样的骰子呢?30种。

对数组[1,2,3,4,5,6]进行全排序,有多少种组合呢?6! = 720种。

所以一个骰子一共有24种可能的结果。为了判断的简单,进行如下的操作:遍历数组,确保第0位的必须小于第1位的,第2位的必须小于第3位的,第4位的必须小于第5位的。然后这三组分别可以得出三个数字,再对这三个数字进行排序,按照从小到大,这样又可以组合出一个六位数。具体算法见下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static int diceToInt(int[] array) {
for (int i = 0; i < 6; i = i + 2) {
if (array[i] > array[i + 1]) {
swap(array, i, i + 1);
}
}

int[] temp = new int[3];
for (int i = 0; i < 6; i = i + 2) {
temp[i / 2] = array[i] * 10 + array[i + 1];
}
Arrays.sort(temp);
return temp[0] * 10000 + temp[1] * 100 + temp[2];
}

满足美味要求热量最小

写完上面那题骰子的问题已经过了一小时四十分了,匆匆忙忙开始做第三题。

食堂吃饭问题,可以吃午饭和晚饭,然后每一种菜品都有一个热量值和美味值,需要满足美味值的情况下,怎么让热量最少。

当时一看到这题就觉得是背包问题,但是又不是一般的背包问题。实际中做的时候时间不多了,我就简单对取餐的种类做了分类讨论:

  • 不吃。在美味值为0的时候可以这么要求。
  • 只吃午餐或者只吃晚餐。那么只需要对午餐和晚餐进行美味值的降序排序,然后找到能够满足的就可以了。
  • 必须午饭和晚饭都吃。

第一条只有美味值为0的时候可以这么做,所以算是边界条件吧。

当时我做的时候想的是按照性价比的思路来做的,但是感觉有很多条件要判断,比如性价比高的不能满足要求,比如某个性价比稍微低了那么一点点,却能够满足要求。

其实事后想想从性价比这一观念出发的话,基本上就是走入歧途了,就跟当时做01背包问题一样,性价比是得不到最优解的。

最后:暴力能解50%…有点亏。

种地问题

一共有六种农作物,给定一个6x6的二维数组,上面有建筑物和土地,在土地上种地,要求相邻的土地种不一样的作物,问有多少种方案。

举个例子,如果只有一片2x2的土地,那么就有630种可能性。6x5x4x5 + 6x5x1x6 = 630

说一下自己的思路,从左上开始往右下走。

  • 如果有一个格子左边的和上面的都是建筑物,那么这一格可以取6种。
  • 如果有一个格子左边或者上面有一个是可以种地的,那么这一格的取值就是左/上的减一。
  • 如果有一个格子的左边且上面都种了地,这个就有问题了。

然后我到现在还没有好的思路。

总结

感觉这次拼多多题出的是非常不错的,能够有效起到区分的效果。

然后我从这次面试中得到的经验:

  • 下次做题应该一开始把所有题目看一遍,不要在一道题上花太久,我这次第二题骰子的问题实在花的太久了,最后也只做出了10%,非常亏。
  • 能用暴力的可以先使用暴力,这种是机试,感觉应该最后只看你通过的case的百分比和吧(不知道每道题有没有权重)。第三题看帖子如果是暴力能拿50%的分数,我没拿到,很可惜。

但是老实说,虽然我现在想到了第二题的解,但是自认为在那种面试环境下我应该是写不出来的,第三题暴力可能还会多给个30%吧,所以其实提升也有限了。提升提升自己下次再来过吧。