不推荐Rice MCS

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
有你有策略
微策略(MicroStrategy)
2019校园招聘火热进行中
E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1941|回复: 19
收起左侧

G家onsite 面经

[复制链接] |试试Instant~
我的人缘0
xpharry 发表于 2018-6-30 16:32:49 | 显示全部楼层 |阅读模式
该内容以做模糊处理,您需要登录后才可查看. 登录 | Sign Up 注册获取更多干货
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  100% (25)
 
 
0% (0)  踩

2018(7-9月) 码农类General 硕士 全职@Google - 网上海投 -   | | fresh grad应届毕业生

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

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

x
Google onsite面经
时间:6/28/2018
地点:San Bruno

一共五轮, 上午三轮,下午两轮,第一轮白人小哥,最后自称母语不是英语,第二轮长发飘逸的泰国大叔,第三轮国人大叔,中午是一个美国小哥带去吃饭散步,下午两轮都是国人小姐姐。recruiter人很好,一直在鼓励我。

第一轮:上来就抛转,丢出一题入门级的DP: 爬楼梯的方式有多少种,LC 70。装模作样讲了几分钟,肯定没超过10分钟。然后当然是follow一题完全不相干的题啊,有一台机器不断地发数据包给本地机器,实现两个函数:
void setPacket(int offset, int size, string data);
int read(char* buffer, int max_length);
前者是要建立一个合理的数据访问机制,只要理解题意,比较容易容易想到用hash map。只是一开始我以为是要把接收的数据包保存到本地,所以思路一直都不对,再问了才确认,数据已经在本地,那么只要找到对应的reference就可以了。read buffer应该也是lc原题。

第二轮:泰国大叔很有大佬的风范,总之气场很强,这轮也是我感觉发挥最不好的一轮。m个栈里面有不同面额的硬币,最多pop n次,peek()可以查看任一位置的值,而不仅是最顶的。那么可以取出最多的总值是多少?一开始懵逼了,不知道怎么下手。面试官给我降低难度,只有一个栈的情况,进一步,只有两个栈怎么办?逐渐觉悟到用递归搜索去解决。按着这个思路代码写出来了。回家复盘的时候,经友人提醒,是多个分组的背包问题。

第三轮:longest subarray with 0 sum。这轮有点可惜。中国大叔,很友好,但是不太主动问问题,我在墙上码代码,他一直在电脑上敲笔记。这题我乍一看,觉得没啥难的,明显双指针嘛,然后一直困扰于如何设置移动窗口边界的条件,一面码代码,一面讲思路,包括讲我为什么卡住,面试官就一直嗯嗯的,也不说对,也不说错。一半多的时间,我发现这不就range sum,换了一面墙,用hash table没几行就写完了。但是时间也到了。可惜的地方是,按着这道题的规模,应该有followup的, 面试官没有机会问了,这部分bonus肯定就没有了。好的一面是,没有他的提醒,我自己从错误的方向上纠正过来了。他最后还问我,我是怎么想到的,我说原数组不能进行排序。希望他get到我的意思了。

第四轮:中国小姐姐。感觉午休过后渐入佳境。出了一题单词处理的问题,听一半还以为要用Trie树,结果不是。一个单词常常用重复某个字母来做强调音,比如hello —> hellooooo, goal —> goooooal。输入这些包含这些重复(这里叫extension)返回所有extension(可能不止一处)的范围。对于helloooo返回的是[[4, 8]]。这是一个one pass的字符串遍历处理就可以了,挺straightforward的。然后followup, 给你一个接口函数可以查字典的,查询一个单词是否在字典里: bool isInDictionary(string word);
要你实现: bool isInExtensionDictionary(string word):
比如对于hellooooo的原始单词是hello是在字典里的,那么返回true。否则像gooool去掉重复的话也不是一个可以查到的单词就返回false。所以其实是实现如何使还原这个含有extension的单词。这里assume单词的extension是3个起,同时所有字典的单词不存在含三个及以上长度连续重复字符的单词。这些条件都是在和面试官不断确认过程中得知的。沟通非常非常重要。那么还原的时候其实有两种情况,重复字符删到只剩一个或者两个,然后调用查字典函数,只要其中一个为true结果就为true。以为有多个extension的情况,我采用了递归去做。

第五轮:也是中国小姐姐。似乎是地里面经里出现过的。一个类似超级马里奥的游戏,有横向和纵向坐标,一个人从高处(x0, y0)往下掉,下面有若干平台(x1, x2, y),掉到一个平台上,可以向左或者向右移动,到边缘又自动往下掉,直到到达地面。问最短路径。路径包含横向移动和纵向移动。每次在新位置又往下掉,实际上又是原来的问题,很像一个二叉树,求最小累计值的那条路。用的是dfs,同时用一个记忆矩阵优化。小姐姐似乎很满意。

总的来说,五轮中三轮都比较顺利,有两轮遇到点麻烦。每一轮都一定写满两面墙,一边写,一边讲,保持跟面试官的通讯在线。被一再提醒的是,面试不是看你做题结果,而是你做题反映出你的思考过程。希望两位大叔手下留情啦~~~

评分

参与人数 7大米 +36 收起 理由
sarahzjn + 10 给你点个赞!
咩酱 + 5 给你点个赞!
idatascience + 5 很有用的信息!
hhfhfhhy1 + 5 感谢楼主分享
marthew777 + 5 给你点个赞!
mitchellhe + 1 很有用的信息!
oceanator + 5 很有用的信息!

查看全部评分


上一篇:unity onsite 跪经
下一篇:lyft店面+店面总结

本帖被以下淘专辑推荐:

我的人缘0
david18 发表于 2018-7-4 13:51:50 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
xpharry 发表于 2018-7-4 03:09
你不需要这么绕,问题就是问弹出的总价值最多是多少,只有弹出,没有压入的动作。

感觉是可以用背包DP来解:
1. 先把每个栈当成一个array, 算出每一位的preSum, 这样就相当于是有 k 个item, preSum是value, index就是cost,
2. 然后用类似背包的方法扫描各个栈,需要注意每个栈只能选一个item,去update Dp每个cost下的值应该就可以了
回复

使用道具 举报

我的人缘0
marthew777 发表于 2018-7-1 02:23:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (56)
 
 
6% (4)  踩
多谢分享。
求大神分析一下Round2的递归方程
回复

使用道具 举报

我的人缘0
hhfhfhhy1 发表于 2018-7-1 03:44:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (40)
 
 
2% (1)  踩
楼主你好。请问第二题每个栈里面的硬币面值是一样的还是可以不一样?
回复

使用道具 举报

我的人缘0
 楼主| xpharry 发表于 2018-7-3 11:54:45 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (25)
 
 
0% (0)  踩
hhfhfhhy1 发表于 2018-7-1 03:44
楼主你好。请问第二题每个栈里面的硬币面值是一样的还是可以不一样?

不一样的,栈里面是各种数值
回复

使用道具 举报

我的人缘0
hhfhfhhy1 发表于 2018-7-3 15:58:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (40)
 
 
2% (1)  踩
xpharry 发表于 2018-7-3 11:54
不一样的,栈里面是各种数值

谢谢。那么请问pop是只可以出某一端的吗。还是和peek一样可以出任意一个地方。
回复

使用道具 举报

我的人缘0
lyyy7537721825 发表于 2018-7-3 19:08:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  80% (4)
 
 
20% (1)  踩
第二题是不是可以用memo加上递归做?
回复

使用道具 举报

我的人缘0
 楼主| xpharry 发表于 2018-7-4 01:01:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (25)
 
 
0% (0)  踩
hhfhfhhy1 发表于 2018-7-3 15:58
谢谢。那么请问pop是只可以出某一端的吗。还是和peek一样可以出任意一个地方。

pop是没有改动的,不然这题栈就没有意义了
回复

使用道具 举报

我的人缘0
 楼主| xpharry 发表于 2018-7-4 01:03:11 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (25)
 
 
0% (0)  踩
lyyy7537721825 发表于 2018-7-3 19:08
第二题是不是可以用memo加上递归做?

是的,我没有加memo,因为时间不够了。

理论上DFS搜索可以解决所有题,相当于找所有可能答案中最优解。
回复

使用道具 举报

我的人缘1
idatascience 发表于 2018-7-4 02:33:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  86% (347)
 
 
13% (55)  踩
xpharry 发表于 2018-7-4 01:01
pop是没有改动的,不然这题栈就没有意义了
. 1point3acres
是说对每个栈,栈顶元素被用了,弹出之后才能使用该栈的第二个元素,对吧?
回复

使用道具 举报

我的人缘0
 楼主| xpharry 发表于 2018-7-4 02:55:27 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (25)
 
 
0% (0)  踩
idatascience 发表于 2018-7-4 02:33
是说对每个栈,栈顶元素被用了,弹出之后才能使用该栈的第二个元素,对吧?

是的。

或者这么说,栈是透明的,所有元素都可见,但作为栈来说,它仍然是保持first-in-last-out的性质,从顶部一个一个弹出来。

评分

参与人数 1大米 +5 收起 理由
idatascience + 5 给你点个赞!

查看全部评分

回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-11-16 17:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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