(据说)华为的一道面试题

刷微博,看到一道面试题:

先说一下思路

默认题意为不能取重复的数字

总体来说,就是从可行解空间[1,1]~[20,20]中,逐步过滤,找到最终答案的过程。说一下过滤步骤:

  1. 首先A不确定两个数字,所以两数之和sum满足:4<=sum<=38
  2. 其次B也不确定,所以两数之积的分解方式可能有多种(本来以为可以用质因子个数>2来判别的,但是后来发现还要考虑两数在1到20之间)
  3. A知道数字了,所以sum的所有分解方式中,只有一个是让B不能确定的,即i+j=sum,切i*j的分解方式不止一种
  4. 这一步比较难:B知道乘积prod,对于prod分解的所有可能,都能得到其和sum,如果sum的所有分解中,只有一个是让B不能确定的;而且prod的分解只有一个是满足此关系的。则当前的prod,以及对应的让B不能确定的prod分解,即为所求解。

1和2很容易理解。3的话,如果sum的诸多分解方式中,都能被B确定,即ij只能唯一分解,那B就不会说不知道数字了。如果sum的诸多分解方式中,有多个不能被B确定,那A在第三步就不能确定数字了,因为A不确定B是在哪一组ij中。

4,B知道乘积prod,假设可以分解为 I_n, J_n 。对于每一组 I_n, J_n:

和为sum=I_n+J_n,且A知道这个sum,这时B推测sum可以分解为i_n+j_n:
  由于3的结论,所以sum对应的i_n*j_n的分解不唯一的情况只有一个
  如果sum对应的i_n*j_n分解不唯一的情况为0个,那么B在第二步就可以猜出
  如果sum对应的i_n*j_n分解不唯一的情况多于1个,那么A在第三步就猜不出来了
在所有的 I_n, J_n 中,满足如上条件的只有一个
如果都满足上述条件的多于一个,那么B在最后一步就无法确定哪一组I_n,J_n是正确答案了

当然,第四步也是在第三步的结果上过滤的

好,接下来就是写代码了

代码

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
// from http://www.robberphex.com/interview-question-from-huawei/
import java.util.*;

public class Main {
public static void main(String[] args) {
Map<Integer, List<List<Integer>>> sumCount = new HashMap<>();
Map<Integer, List<List<Integer>>> prodCount = new HashMap<>();
Set<List<Integer>> candidates = new HashSet<>();

for (int i = 1; i <= 20; i++) {
for (int j = i + 1; j <= 20; j++) {
// 第一步,A猜不出来
if (i + j < 4 || i + j > 38) {
continue;
}

List<List<Integer>> sumCnt = sumCount.getOrDefault(i + j, new ArrayList<>());
sumCnt.add(Arrays.asList(i, j));
sumCount.put(i + j, sumCnt);

List<List<Integer>> prodCnt = prodCount.getOrDefault(i * j, new ArrayList<>());
prodCnt.add(Arrays.asList(i, j));
prodCount.put(i * j, prodCnt);
}
}

for (Map.Entry<Integer, List<List<Integer>>> entry : sumCount.entrySet()) {
// 第二步,B猜不出来
int cnt = 0;
List<Integer> res = null;
if (entry.getValue().size() > 1) {
for (List<Integer> list : entry.getValue()) {
if (prodCount.get(list.get(0) * list.get(1)).size() > 1) {
res = list;
cnt++;
}
}
}
// 第三步,A猜出来了
if (cnt == 1) {
candidates.add(res);
}
}

//第四步,从第三步拿到的candidates中,过滤
for (List<Integer> num : candidates) {
int poss = 0;
for (List<Integer> prodNum : prodCount.get(num.get(0) * num.get(1))) {
int cnt = 0;
for (List<Integer> sumNum : sumCount.get(prodNum.get(0) + prodNum.get(1))) {
if (prodCount.get(sumNum.get(0) * sumNum.get(1)).size() > 1) {
cnt++;
}
}
if (cnt == 1) {
poss++;
}
}
if (poss == 1) {
System.out.println(num);
}
}
}
}

答案

算出来的答案有三组:

1
2
3
[2, 3]
[2, 4]
[9, 20]

当然,也有人说如果可以取重复的数字呢,那么只需要修改第11行就可以了,这时答案变为:

1
2
[2, 2]
[9, 20]

当然,这个思路也仅仅是我不成熟的想法,我也很难完整的证明这个解法是正确的。如果发现其中有错误的地方,请评论指出,谢谢!

作者

Robert Lu

发布于

2019-07-28

许可协议

评论