如何在一个新城市*快速*安顿物品清单

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 3005|回复: 36
收起左侧

google 电面 跪经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
yunjiezhang 发表于 2017-12-5 07:32:57 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (11)
 
 
15% (2)  踩

2017(10-12月) 码农类General 本科 实习@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. . from: 1point3acres
input形式自己选,我经过他的允许用的hashmap。
二十分钟差不多写完了,然后就开始聊天,小哥说 I have a very positive comment about you. 当时心里美滋滋。

第二轮一个毛子大叔,姓氏貌似是卡斯帕罗夫,出了道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. -google 1point3acres
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 for more.
第二轮肯定是跪惨了。
. 留学申请论坛-一亩三分地
不过结束之后反思一下,说到底确实自己实力不够好,不然dp的话应该可以秒出最简做法,不管客观情况如何。. from: 1point3acres
主要还有其他公司面试,首次发帖,分享一下自己的经历,希望对大家有用,攒一下人品,顺便想混点大米。一次搜索一升米,萌新伤不起。
希望给个加面机会把。


评分

参与人数 8大米 +30 收起 理由
Matthew179 + 3 欢迎分享你知道的情况,会给更多积分奖励!
xiayank + 5 给你点个赞!
zju无水的鱼 + 5 很有用的信息!
charlie.wuhan + 5 很有用的信息!
kakka + 5 欢迎来一亩三分地论坛!
reliveinfire + 3 很有用的信息!
linlizh + 2 很有用的信息!
hychin + 2 给你点个赞!

查看全部评分


上一篇:twilio 店面
下一篇:[電面] IXL

本帖被以下淘专辑推荐:

  • · google|主题: 59, 订阅: 23
我的人缘0
 楼主| yunjiezhang 发表于 2017-12-5 08:01:45 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  84% (11)
 
 
15% (2)  踩
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 这是最初始的状况。.本文原创自1point3acres论坛
接下来每一次dp的时候,check一下当前这一个stair是不是sticky:
如果是,那么 table[1][current] = table[2][current] = 0;. 1point 3acres 论坛
如果不是,那么根据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]
回复

使用道具 举报

我的人缘0
rhbupt 发表于 2017-12-5 07:49:50 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (39)
 
 
11% (5)  踩
Lz能分享一下第二题的详细解法么,不懂怎么用memoization优化
回复

使用道具 举报

我的人缘0
 楼主| yunjiezhang 发表于 2017-12-5 08:03:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (11)
 
 
15% (2)  踩
rhbupt 发表于 2017-12-5 07:49
Lz能分享一下第二题的详细解法么,不懂怎么用memoization优化

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

使用道具 举报

我的人缘0
rhbupt 发表于 2017-12-5 08:12:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (39)
 
 
11% (5)  踩
table[0][1] = 1, table[0][1] = 0 是不是应该初始化这样?

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
啊lch 发表于 2017-12-5 08:19:13 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  99% (106)
 
 
0% (1)  踩
是不是可以从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,应该就是结果了吧
回复

使用道具 举报

我的人缘0
 楼主| yunjiezhang 发表于 2017-12-5 08:24:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (11)
 
 
15% (2)  踩
rhbupt 发表于 2017-12-5 07:49
Lz能分享一下第二题的详细解法么,不懂怎么用memoization优化

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

使用道具 举报

我的人缘0
 楼主| yunjiezhang 发表于 2017-12-5 08:31:35 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (11)
 
 
15% (2)  踩
啊lch 发表于 2017-12-5 08:19
是不是可以从0开始到n这么做更简便一些。这样只用一个一维的int[] dp数组,如果当前到达位置i是偶数,那么 ...

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

使用道具 举报

我的人缘0
rhbupt 发表于 2017-12-5 08:33:28 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (39)
 
 
11% (5)  踩
yunjiezhang 发表于 2017-12-5 08:24
诶。。初始化写错了 不好意思
table[0][1] = 3, table[1][1] = 3. more info on 1point3acres
在第一级的时候,不管任何跳法都可以 ...

明白了。谢谢耐心的回复
回复

使用道具 举报

我的人缘0
啊lch 发表于 2017-12-5 08:36:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  99% (106)
 
 
0% (1)  踩
yunjiezhang 发表于 2017-12-5 08:24
诶。。初始化写错了 不好意思 来源一亩.三分地论坛.
table[0][1] = 3, table[1][1] = 3
在第一级的时候,不管任何跳法都可以 ...

哦哦,哦哦,原来如此,审题直接gg。。。。
回复

使用道具 举报

我的人缘0
 楼主| yunjiezhang 发表于 2017-12-5 08:36:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (11)
 
 
15% (2)  踩
啊lch 发表于 2017-12-5 08:36
哦哦,哦哦,原来如此,审题直接gg。。。。

没事没事 2333

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
hychin 发表于 2017-12-5 10:19:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  81% (243)
 
 
18% (54)  踩
yunjiezhang 发表于 2017-12-5 08:03
面试时候面试官说 assume stair one is not sticky,他自己的方法是直接求到第一层的ways,第一层到groun ...

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

使用道具 举报

我的人缘0
 楼主| yunjiezhang 发表于 2017-12-5 10:25:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (11)
 
 
15% (2)  踩
hychin 发表于 2017-12-5 10:19
楼主干的漂亮,我感觉你应该能过,没看到为啥会跪,给你加了点大米

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

使用道具 举报

我的人缘0
hychin 发表于 2017-12-5 10:26:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  81% (243)
 
 
18% (54)  踩
对了,最后return的值应该是 table[0][n] + table[1][n] 吧因为到ground你有可能跳了奇数次,也有可能跳了偶数次
回复

使用道具 举报

我的人缘0
 楼主| yunjiezhang 发表于 2017-12-5 10:27:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (11)
 
 
15% (2)  踩
hychin 发表于 2017-12-5 10:26
对了,最后return的值应该是 table[0][n] + table[1][n] 吧因为到ground你有可能跳了奇数次,也有可能跳了 ...

啊 没错。。诶。。我这脑子老出错。。. 1point 3acres 论坛
谢谢指出来
回复

使用道具 举报

我的人缘0
prince123 发表于 2017-12-5 10:40:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (218)
 
 
11% (27)  踩
请问楼主google实习背靠背是每轮一题么

评分

参与人数 1大米 +3 收起 理由
黑人不是牙膏 + 3 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| yunjiezhang 发表于 2017-12-5 10:51:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (11)
 
 
15% (2)  踩
prince123 发表于 2017-12-5 10:40
请问楼主google实习背靠背是每轮一题么

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

使用道具 举报

我的人缘0
b01501085 发表于 2017-12-5 12:29:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
請問樓主第一題是怎麼去random的呢?
回复

使用道具 举报

我的人缘0
b01501085 发表于 2017-12-5 13:26:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
另外問一下如果我在第三層直接跳4這樣算一種嗎?
回复

使用道具 举报

我的人缘0
 楼主| yunjiezhang 发表于 2017-12-6 00:14:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (11)
 
 
15% (2)  踩
b01501085 发表于 2017-12-5 13:26
另外問一下如果我在第三層直接跳4這樣算一種嗎?
-google 1point3acres
算。所以第一层有三种跳法。
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

GMT+8, 2018-8-19 10:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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