谷歌跪经

谷歌全职new grad面试凉了,贡献一枚面经第一轮:
华人面试官,猜数字,题面在 lc bulls and cows, 问的是最少多少次能猜着。
没复习到这题,理解题意有误,绕了圈子,最后也没想出特别好的办法来。面试官拼命给hint不太能get得到。 这轮挂了。

第二轮
白人小哥,设计贪吃蛇,只聊到怎么随机放置食物。

第三轮
小哥,find peak num简化版,二分秒, 然后是货币汇率原题,follow up 使得query时间最优。

第四轮
前缀表达式转后缀,要求O(1)空间复杂度,用递归写出来了,但是写得慢跑test cases后就没了。。这轮一般。

面试官都很nice,自己实力不够,来年再战吧。

谢谢找工一路上帮忙的同学,真的谢谢。

第一题抛砖引玉一下,如果我理解没错的话,面试官想要问的是最少多少次能「保证」猜到。
我也觉得应该使用minmax

以下是我的naive minmax,尚未实现alpha beta剪枝,并且应该有很多地方可以优化,希望可以和大家讨论以下


// opponent move. 1point3acres
int max(Set<Integer> candidates, int guess) {
    int res = Integer.MIN_VALUE;
    for (int a = 0; a <= 4; ++a) {
        for (int b = 0; b <=4; ++b) {
            Set<Integer> nextLayer = filter(candidates, guess, a, b);
            res = Math.max(res, min(nextLayer));
        }
    }
    return res;
}
// player move
int min(Set<Integer> candidates) {. 1point3acres
    int res = Integer.MAX_VALUE;
    for (int guess : candidates) {
        res = Math.min(res, max(candidates, guess));
    }
    return res;
}

// helper function: compute the set of candidates corresponds to given guess and a b
Set<Integer> filter(Set<Integer> candidates, int guess, a, b) {
    Set<Integer> res = new HashSet<>();
    for (int candidate : candidate) {
        // compute a and b
        int aa = 0;
        int [] digits_candidate = new int[10];
        int [] digits_guess = new int[10];
        for (int i = 0; i < 4; ++i) {
            digits_candidate[i] = candidate % 10;
            digits_guess[i] = guess % 10
            if (digits_candidate == digits_guess) {
                ++aa;
            }
            candidate /= 10;
            guess /= 10;
        }
        int bb = 0;
        for (int i = 0; i < 10; ++i) {
            bb += Math.min(digits_candidate[i], digits_guess[i]);
        }
        bb -= aa;. From 1point 3acres bbs
        
        if (aa == a && bb == b) {
            res.add(candidate);. 1point3acres
        }
    }
    return res;
}


补充内容 (2018-3-1 14:49):
Oops, line 06 should be:

for (int b = 0; a + b <=4; ++b) {

因为这类题目要求的是(最坏情况下的)“最少步数”,也就是worst-case lower bound。

寻找lower bound的方法之一就是Adversary Arguments,也就是假想有一个对手与你博弈,它总是挑选对你最坏的“分支”。

我随便找了一篇文章,感觉可以看一下:http://jeffe.cs.illinois.edu/tea … es/29-adversary.pdf