google 电面 跪经

上周五电面的google两轮，跪惨了。
第一轮一个听口音一个白人小哥，问了一道感觉是原创题，不难。
There are 10 countries, each with a unique population. Your job is to create a random country generator that generates each country according to its population.
input形式自己选，我经过他的允许用的hashmap。
二十分钟差不多写完了，然后就开始聊天，小哥说 I have a very posi

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

说了一下，用一个 int[2][n]的array来存dp的subproblem的值。
第二轮肯定是跪惨了。

不过结束之后反思一下，说到底确实自己实力不够好，不然dp的话应该可以秒出最简做法，不管客观情况如何。
主要还有其他公司面试，首次发帖，分享一下自己的经历，希望对大家有用，攒一下人品，顺便想混点大米。一次搜索一升米，萌新伤不起。
希望给个加面机会把。

rhbupt 发表于 2017-12-5 07:49
Lz能分享一下第二题的详细解法么，不懂怎么用memoization优化

input就是n，还有一个 int[] stickies ，表示所有sticky的stair。
用一个int[2][n] table来存每一个stair的state，第一个index表示这是odd turn 还是 even turn，第二个n是表示第n级台阶能够到ground的方式的数量。初始化的时候所有值都是0。
table[1][1] = 3, table[2][1] = 3 这是最初始的状况。
接下来每一次dp的时候，check一下当前这一个stair是不是sticky:
如果是，那么 table[1][current] = table[2][current] = 0;
如果不是，那么根据turn判断到底能fall down 多少层。
even: table[0][current] = table[1][current - 1] + table[1][current - 3] + table[1][current - 4]
odd: table[1][current] = table[0][current - 1] + table[0][current - 2] + table[0][current - 4]
最后直接return table[n]

写了个dp的，思路是从n开始往下跳，没test case不知道是不是对。。。

class Solution {
    public int jumpGround(int n, int[] sticky) {
        HashSet<Integer> set = new HashSet();
        for (int num : sticky)
            set.add(num);
        int[][] dp = new int[n+4][2];
        if (!set.contains(n)) dp[n][0] = 1;
        for (int i = n - 1; i > 0; i--) {
            if (set.contains(i)) continue;
            dp[i][0] = dp[i+1][1] + dp[i+3][1] + dp[i+4][1];
            dp[i][1] = dp[i+1][0] + dp[i+2][0] + dp[i+4][0];
        }
        int ans = 3 * (dp[1][0] + dp[1][1]);
        ans += 2 * (dp[2][0] + dp[2][1]);
        ans += (dp[3][0] + 2 * dp[3][1]);
        ans += (dp[4][0] + dp[4][1]);
        return ans;
    }
}

Lz能分享一下第二题的详细解法么，不懂怎么用memoization优化

rhbupt 发表于 2017-12-5 07:49
Lz能分享一下第二题的详细解法么，不懂怎么用memoization优化

面试时候面试官说 assume stair one is not sticky，他自己的方法是直接求到第一层的ways，第一层到ground的ways他当作是已知。具体面试如果碰到，建议你问清楚一些特殊情况，比如第一层是不是sticky。

table[0][1] = 1, table[0][1] = 0 是不是应该初始化这样？

是不是可以从0开始到n这么做更简便一些。这样只用一个一维的int[] dp数组，如果当前到达位置i是偶数，那么只用考虑dp[i－1]，dp[i-4]，因为偶－2是偶，偶减3是奇；如果i是奇数，那么得考虑dp[i-1],dp[i-2].dp[i-3],dp[i-4]，奇－2 ＝ 奇，奇－3 ＝ 偶；如果以上dp[i-k]中i－k是sticky的话，我们就也不考虑dp[i-k]， 这样一直到n，应该就是结果了吧

rhbupt 发表于 2017-12-5 07:49
Lz能分享一下第二题的详细解法么，不懂怎么用memoization优化

诶。。初始化写错了 不好意思
table[0][1] = 3, table[1][1] = 3
在第一级的时候，不管任何跳法都可以到gorund，所以算三种，这也是面试官特地指出来到。我一开始初始化也是都当成1的。上面帖子第一个index写错了，不好意思。

啊lch 发表于 2017-12-5 08:19
是不是可以从0开始到n这么做更简便一些。这样只用一个一维的int[] dp数组，如果当前到达位置i是偶数，那么 ...

嗯 懂你的意思
不过题目的奇偶行考虑的是jump的次数而不是当前台阶高度，没有理解错的话，你说的是台阶的高度把。貌似在这个题目里面可能有点不太合适

yunjiezhang 发表于 2017-12-5 08:24
诶。。初始化写错了 不好意思
table[0][1] = 3, table[1][1] = 3
在第一级的时候，不管任何跳法都可以 ...

明白了。谢谢耐心的回复

yunjiezhang 发表于 2017-12-5 08:24
诶。。初始化写错了 不好意思
table[0][1] = 3, table[1][1] = 3
在第一级的时候，不管任何跳法都可以 ...

哦哦，哦哦，原来如此，审题直接gg。。。。