39

(据说)华为的一道面试题 | Robert's Blog

 5 years ago
source link: https://www.robberphex.com/interview-question-from-huawei/?
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

刷微博，看到一道面试题：

interview.png

先说一下思路

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

总体来说，就是从可行解空间[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]

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK