據(jù)說華為的一道面試題

發(fā)布時(shí)間：2019-07-29 16:50:31 作者：Robert's Blog

這篇文章主要介紹了據(jù)說華為的一道Java面試題，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

刷微博，看到一道面試題：

先說一下思路

默認(rèn)題意為不能取重復(fù)的數(shù)字

總體來說，就是從可行解空間[1,1]~[20,20]中，逐步過濾，找到最終答案的過程。說一下過濾步驟：

首先A不確定兩個(gè)數(shù)字，所以兩數(shù)之和sum滿足：4<=sum<=38
其次B也不確定，所以兩數(shù)之積的分解方式可能有多種（本來以為可以用質(zhì)因子個(gè)數(shù)>2來判別的，但是后來發(fā)現(xiàn)還要考慮兩數(shù)在1到20之間）
A知道數(shù)字了，所以sum的所有分解方式中，只有一個(gè)是讓B不能確定的，即i+j=sum，切i*j的分解方式不止一種
這一步比較難：B知道乘積prod，對于prod分解的所有可能，都能得到其和sum，如果sum的所有分解中，只有一個(gè)是讓B不能確定的；而且prod的分解只有一個(gè)是滿足此關(guān)系的。則當(dāng)前的prod，以及對應(yīng)的讓B不能確定的prod分解，即為所求解。

1和2很容易理解。3的話，如果sum的諸多分解方式中，都能被B確定，即i*j只能唯一分解，那B就不會說不知道數(shù)字了。如果sum的諸多分解方式中，有多個(gè)不能被B確定，那A在第三步就不能確定數(shù)字了，因?yàn)锳拿不準(zhǔn)B是在哪一組i*j中。

4，B知道乘積prod，假設(shè)可以分解為 I_n, J_n 。對于每一組 I_n, J_n：和為sum=I_n+J_n，且A知道這個(gè)sum，這時(shí)B推測sum可以分解為i_n+j_n：由于3的結(jié)論，所以sum對應(yīng)的i_n*j_n的分解不唯一的情況只有一個(gè) 如果sum對應(yīng)的i_n*j_n分解不唯一的情況為0個(gè)，那么B在第二步就可以猜出如果sum對應(yīng)的i_n*j_n分解不唯一的情況多于1個(gè)，那么A在第三步就猜不出來了在所有的 I_n, J_n 中，滿足如上條件的只有一個(gè) 如果都滿足上述條件的多于一個(gè)，那么B在最后一步就無法確定哪一組I_n,J_n是正確答案了

當(dāng)然，第四步也是在第三步的結(jié)果上過濾的

好，接下來就是寫代碼了

代碼

// 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);
            }
        }
    }
}

答案

算出來的答案有三組：