纽约州立大学转UCLA结果

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
把贵司招聘信息放这里
查看: 3408|回复: 36
收起左侧

google 电面 跪经

[复制链接] |试试Instant~
我的人缘0
yunjiezhang 发表于 2017-12-5 07:32:57 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (18)
 
 
10% (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.
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. . 牛人云集,一亩三分地
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的值。
第二轮肯定是跪惨了。
. 1point3acres
不过结束之后反思一下,说到底确实自己实力不够好,不然dp的话应该可以秒出最简做法,不管客观情况如何。.留学论坛-一亩-三分地
主要还有其他公司面试,首次发帖,分享一下自己的经历,希望对大家有用,攒一下人品,顺便想混点大米。一次搜索一升米,萌新伤不起。.本文原创自1point3acres论坛
希望给个加面机会把。


评分

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

查看全部评分


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

本帖被以下淘专辑推荐:

  • · google|主题: 105, 订阅: 42
我的人缘0
 楼主| yunjiezhang 发表于 2017-12-5 08:01:45 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  90% (18)
 
 
10% (2)  踩
rhbupt 发表于 2017-12-5 07:49.本文原创自1point3acres论坛
Lz能分享一下第二题的详细解法么,不懂怎么用memoization优化

input就是n,还有一个 int[] stickies ,表示所有sticky的stair。
用一个int[2][n] table来存每一个stair的state,第一个index表示这是odd turn 还是 even turn,第二个n是表示第n级台阶能够到ground的方式的数量。初始化的时候所有值都是0。.1point3acres网
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]
回复

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| yunjiezhang 发表于 2017-12-5 08:03:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (18)
 
 
10% (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)   【踩】
全局: 顶  86% (43)
 
 
14% (7)  踩
table[0][1] = 1, table[0][1] = 0 是不是应该初始化这样?
回复

使用道具 举报

我的人缘0
啊lch 发表于 2017-12-5 08:19:13 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  99% (109)
 
 
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)   【踩】
全局: 顶  90% (18)
 
 
10% (2)  踩
rhbupt 发表于 2017-12-5 07:49
Lz能分享一下第二题的详细解法么,不懂怎么用memoization优化

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

使用道具 举报

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

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

使用道具 举报

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

明白了。谢谢耐心的回复

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.


回复

使用道具 举报

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

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

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-10-17 22:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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