一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1016|回复: 30
收起左侧

google 电面 跪经

[复制链接] |试试Instant~ |关注本帖
yunjiezhang 发表于 2017-12-5 07:32:57 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 本科 实习@Google - 内推 - 技术电面 |Other其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
上周五电面的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 positive comment about you. 当时心里美滋滋。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
.鏈枃鍘熷垱鑷1point3acres璁哄潧
第二轮一个毛子大叔,姓氏貌似是卡斯帕罗夫,出了道dp的题,有点像leetcode frog,感觉也不难。
There is a ball on the nth stairs, and it wants to get to the ground(level 0). There are some sticky stairs, and once the ball lands on the sticky stair, it is stuck and can never move. . 1point3acres.com/bbs
During odd turns, you can jump down 1, 2, or 4 stairs.  During even turns, you can jump down 1, 3, 4 stairs.
Return the number of ways you can get to ground.
和面试官先确定了思路dp,写了个不用memoization的最好写解法。写的过程中我解释思路,然后面试官莫名其妙一直在催,还自言自语,为了听清他说话我还刻意留意慢点写,他先对code的方式抱怨了一大段,后面突然emmmm了一会儿然后说it seems work, i like your way of writing it. Don't stop. 内心崩溃的。之后让我说时间复杂度,然后追着时间复杂的事情问了一大堆问题。我小心地问是否是希望我用memoization 优化,他说是的,但是don't get ahead, let's focus on this。 然后又花了十几分钟,最后只剩十五分钟给我优化,然后又开始催,写一行就说一行什么什么问题,然后要求我按照他的思路写,最后心态崩了,没写完,把思路说了一下,用一个 int[2][n]的array来存dp的subproblem的值。
第二轮肯定是跪惨了。. visit 1point3acres.com for more.

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


评分

6

查看全部评分

本帖被以下淘专辑推荐:

  • · google|主题: 6, 订阅: 0
rhbupt 发表于 2017-12-5 07:49:50 | 显示全部楼层
Lz能分享一下第二题的详细解法么,不懂怎么用memoization优化
回复 支持 反对

使用道具 举报

 楼主| yunjiezhang 发表于 2017-12-5 08:01:45 | 显示全部楼层
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]
回复 支持 反对

使用道具 举报

 楼主| yunjiezhang 发表于 2017-12-5 08:03:20 | 显示全部楼层
rhbupt 发表于 2017-12-5 07:49
Lz能分享一下第二题的详细解法么,不懂怎么用memoization优化

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

使用道具 举报

rhbupt 发表于 2017-12-5 08:12:32 | 显示全部楼层
table[0][1] = 1, table[0][1] = 0 是不是应该初始化这样?
回复 支持 反对

使用道具 举报

啊lch 发表于 2017-12-5 08:19:13 | 显示全部楼层
是不是可以从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,应该就是结果了吧
回复 支持 反对

使用道具 举报

 楼主| yunjiezhang 发表于 2017-12-5 08:24:20 | 显示全部楼层
rhbupt 发表于 2017-12-5 07:49
鏉ユ簮涓浜.涓夊垎鍦拌鍧. Lz能分享一下第二题的详细解法么,不懂怎么用memoization优化

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

使用道具 举报

 楼主| yunjiezhang 发表于 2017-12-5 08:31:35 | 显示全部楼层
啊lch 发表于 2017-12-5 08:19
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴是不是可以从0开始到n这么做更简便一些。这样只用一个一维的int[] dp数组,如果当前到达位置i是偶数,那么 ...

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

使用道具 举报

rhbupt 发表于 2017-12-5 08:33:28 | 显示全部楼层
yunjiezhang 发表于 2017-12-5 08:24
诶。。初始化写错了 不好意思
table[0][1] = 3, table[1][1] = 3
在第一级的时候,不管任何跳法都可以 ...
. 1point3acres.com/bbs
明白了。谢谢耐心的回复
回复 支持 反对

使用道具 举报

啊lch 发表于 2017-12-5 08:36:14 | 显示全部楼层
yunjiezhang 发表于 2017-12-5 08:24. visit 1point3acres.com for more.
诶。。初始化写错了 不好意思 . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
table[0][1] = 3, table[1][1] = 3
在第一级的时候,不管任何跳法都可以 ...

哦哦,哦哦,原来如此,审题直接gg。。。。
回复 支持 反对

使用道具 举报

 楼主| yunjiezhang 发表于 2017-12-5 08:36:44 | 显示全部楼层
啊lch 发表于 2017-12-5 08:36
哦哦,哦哦,原来如此,审题直接gg。。。。

没事没事 2333
回复 支持 反对

使用道具 举报

hychin 发表于 2017-12-5 10:19:34 | 显示全部楼层
yunjiezhang 发表于 2017-12-5 08:03
面试时候面试官说 assume stair one is not sticky,他自己的方法是直接求到第一层的ways,第一层到groun ...

楼主干的漂亮,我感觉你应该能过,没看到为啥会跪,给你加了点大米
回复 支持 反对

使用道具 举报

 楼主| yunjiezhang 发表于 2017-12-5 10:25:03 | 显示全部楼层
hychin 发表于 2017-12-5 10:19
楼主干的漂亮,我感觉你应该能过,没看到为啥会跪,给你加了点大米

哈哈哈哈 托你吉言。谢谢啦。但还是感觉不太好。但愿有机会吧。
回复 支持 反对

使用道具 举报

hychin 发表于 2017-12-5 10:26:26 | 显示全部楼层
对了,最后return的值应该是 table[0][n] + table[1][n] 吧因为到ground你有可能跳了奇数次,也有可能跳了偶数次
回复 支持 反对

使用道具 举报

 楼主| yunjiezhang 发表于 2017-12-5 10:27:44 | 显示全部楼层
hychin 发表于 2017-12-5 10:26
对了,最后return的值应该是 table[0][n] + table[1][n] 吧因为到ground你有可能跳了奇数次,也有可能跳了 ...

啊 没错。。诶。。我这脑子老出错。。
谢谢指出来
回复 支持 反对

使用道具 举报

prince123 发表于 2017-12-5 10:40:34 | 显示全部楼层
请问楼主google实习背靠背是每轮一题么

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| yunjiezhang 发表于 2017-12-5 10:51:20 | 显示全部楼层
prince123 发表于 2017-12-5 10:40
请问楼主google实习背靠背是每轮一题么

我碰到的情况是的,我身边的朋友们也是背靠背每轮一题。
回复 支持 反对

使用道具 举报

b01501085 发表于 2017-12-5 12:29:14 | 显示全部楼层
請問樓主第一題是怎麼去random的呢?
回复 支持 反对

使用道具 举报

b01501085 发表于 2017-12-5 13:26:44 | 显示全部楼层
另外問一下如果我在第三層直接跳4這樣算一種嗎?
回复 支持 反对

使用道具 举报

 楼主| yunjiezhang 发表于 2017-12-6 00:14:31 | 显示全部楼层
b01501085 发表于 2017-12-5 13:26
另外問一下如果我在第三層直接跳4這樣算一種嗎?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
算。所以第一层有三种跳法。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-12-16 01:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表