详谈如何最大化利用career fair

一亩三分地论坛

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

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 1901|回复: 30
收起左侧

新鲜出炉的G家面经

[复制链接] |试试Instant~
我的人缘0
四面·楚歌 发表于 2018-2-24 09:42:20 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (8)
 
 
0% (0)  踩

2018(4-6月) 码农类General 硕士 全职@Google - 内推 - Onsite  | Other | fresh grad应届毕业生

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

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

x
春节前拿到的onsite通知,初八(今天)面试。

第一轮:特友好的国人妹子(据说刚来一个月),先扯了几句闲话,开始做题。第一题:给一个array of binary tree node,问能否组成一个树(必须并且只能用上所有给的node,只能组出一棵树)。用hashmap存每个node的parent,然后找那唯一的一个没有parent的node为root,BFS检测环路。剩15分钟第二题:定义一个横向一维棋盘,上面有两种棋子L和R若干,L只能往左走,R只能往右走,并且棋子不可以跨越其他棋子移动。给出起始状态和终点状态,问能否到达。序列对比+起始-终点状态检测秒了。

第二轮:老美。LC340。follow up,如果string太长无法存进内存,只能用getNext()获取下一个字符,该怎么修改算法。

午餐轮:谷歌的食堂吃东西居然是免费的(哇哦)

第三轮:老美。第一题:给一个整数array代表一组线段,问是否任意三条线段都能组成三角形,数学题O(n)秒了。follow up,如果是sorted big array 并且用getNext()获取下个线段长度,问是否存在三条线段能组成三角形(这不还是数学题吗)。第二题:经典3Sum返回T/F,不允许用hashing(包括hashset,hashmap和类似手段)以小于O(n2logn)的时间复杂度完成。这题在binary search上纠结了好长时间,最后用循环+双指针搞定。

第四轮:我快累趴了。给一系列近义词组(a set of pairs of strings),问两个string是否同义(对应词为近义词或完全相同)。一开始用2d boolean array来存储近义词关系,最后改成map(word,set(word))来减小空间需求。关键点在于(a,b)近义词,(a,c)近义词,(b,c)不一定是近义词,除非(b,c)出现在set里面。follow up,如果(a,b)近义词,(a,c)近义词,(b,c)就是近义词(不需要存在于set中),怎么修改算法。类似MST的思路搞定。
. 一亩-三分-地,独家发布
写了一天白板,腰疼。。。
等结果中,发个面经攒人品。

评分

参与人数 6大米 +18 收起 理由
enjoynet + 3 很有用的信息!
evaljy + 3 祝好运!
closewen + 5 666
random_who + 3 给你点个赞!
Yanainusa + 3 很有用的信息!
huruidedd + 1 给你点个赞!

查看全部评分


上一篇:去爸爸昂赛面经
下一篇:【求面经】Marvell Onsite Embedded Software

本帖被以下淘专辑推荐:

  • · google|主题: 86, 订阅: 32
我的人缘0
BigShaun 发表于 2018-3-2 10:55:19 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
21kekeke 发表于 2018-2-27 08:27
楼主请问一下第二题 lc340的followup 是不是还是一样 用hashmap存每个char的latest position?
. From 1point 3acres bbs
如果用java的话可以用LinkedHashMap,可以很容易保存一个队没个char最后出现index的表。类似LRU
回复

使用道具 举报

我的人缘0
 楼主| 四面·楚歌 发表于 2018-2-26 11:39:23 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (8)
 
 
0% (0)  踩
Yanainusa 发表于 2018-2-26 05:29. 围观我们@1point 3 acres
请问楼主为什么复杂度从O(mn2)降到了O(mn)啊?m和n分别是矩阵的长和宽么?

m、n是长和宽。 来源一亩.三分地论坛.
用多源BFS就是O(mn),把所有的5 push进queue然后BFS,找到4就停。所以时间复杂度是O(mn)。
如果需要返回路径也一样,记录parent最后backtrack就好。
回复

使用道具 举报

我的人缘0
dawskiper 发表于 2018-2-24 16:22:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
第一轮第二题是柒柒柒,第四轮是陆捌肆+陆捌伍
陆捌伍我看过的做法是,先找in-degree为2的点,如果能找到的话,删除其中一条边,用union-found检测连通性.如果找不到in-degree为2的点的话,说明有环,union-found的时候也能找到环返回.. 1point 3acres 论坛
LZ可以说说用MST来做的思路吗?


补充内容 (2018-2-25 10:20):. Waral 博客有更多文章,
Emmmm我看错题了...昨天找union-find的题号看错了.第四轮是柒叁柒和柒叁肆.
柒叁肆用union-find维护各个集合就可以了,每个集合内部单词彼此相似.

评分

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

查看全部评分

回复

使用道具 举报

我的人缘0
橙小夕 发表于 2018-2-24 16:26:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (34)
 
 
2% (1)  踩
想问问楼主电面面经是啥

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
 楼主| 四面·楚歌 发表于 2018-2-25 06:48:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (8)
 
 
0% (0)  踩
dawskiper 发表于 2018-2-24 16:22
第一轮第二题是柒柒柒,第四轮是陆捌肆+陆捌伍. 1point 3acres 论坛
陆捌伍我看过的做法是,先找in-degree为2的点,如果能找到的话 ...
. 围观我们@1point 3 acres
我的作法说白了就是分组,如果两个词是近义词,就分为一个组;如果两个词已经各自有组了,那么合并两个组。用两个map来存储分组信息,一个是某单词所属组的root单词,另一个是某root单词的所有组员,包括它自己。
回复

使用道具 举报

我的人缘0
 楼主| 四面·楚歌 发表于 2018-2-25 06:52:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (8)
 
 
0% (0)  踩
橙小夕 发表于 2018-2-24 16:26
想问问楼主电面面经是啥
. 1point3acres
我电面的题目是:给一个整型二维矩阵
比如:
1 5 6 3 5.1point3acres网
2 6 1 2 3. Waral 博客有更多文章,
1 3 6 4 9. Waral 博客有更多文章,
4 3 2 1 0
求某两个数之间的最短Manhattan distance
比如求5和4的最短距离,就是(0,4)的5和(2,3)的4的距离,返回3。
回复

使用道具 举报

我的人缘0
anica567 发表于 2018-2-25 08:20:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
第四题是气散气
回复

使用道具 举报

我的人缘0
cmuqiyihu 发表于 2018-2-25 08:47:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
感觉你和我同一天面的那个同学。。。感觉你这个面试很有希望呀!!! 顶一个
回复

使用道具 举报

我的人缘0
橙小夕 发表于 2018-2-25 09:56:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (34)
 
 
2% (1)  踩
四面·楚歌 发表于 2018-2-25 06:52
我电面的题目是:给一个整型二维矩阵
比如:
1 5 6 3 5
-google 1point3acres
我个人的想法是对每一个5都找一遍到4的最短距离,然后输出最短的那个,不知道对不对。
回复

使用道具 举报

我的人缘0
 楼主| 四面·楚歌 发表于 2018-2-25 10:08:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (8)
 
 
0% (0)  踩
橙小夕 发表于 2018-2-25 09:56
我个人的想法是对每一个5都找一遍到4的最短距离,然后输出最短的那个,不知道对不对。

我的第一想法也是这样的只是时间复杂度是O(mn2),太大了。
最后用的多源BFS。时间复杂度O(mn)

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

回复

使用道具 举报

我的人缘0
dawskiper 发表于 2018-2-25 10:28:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (14)
 
 
0% (0)  踩
再请教一下LZ,关于第三题,O(n)的做法是不是找到最短边a,次短边b和最长边c,然后比较是否a+b>c?
然后如果是排序好的stream,记录之前的两个边e[i-2]和e[i-1],如果当前的e[i]满足e[i-2]+e[i-1]>e[i],那么对于stream来说,在这个点之后都存在符合条件的三个边.
回复

使用道具 举报

我的人缘0
Googlehsie 发表于 2018-2-25 10:31:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (47)
 
 
11% (6)  踩
楼主都能秒杀题目 太屌了!!!!!
回复

使用道具 举报

我的人缘0
 楼主| 四面·楚歌 发表于 2018-2-25 12:13:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (8)
 
 
0% (0)  踩
dawskiper 发表于 2018-2-25 10:28
再请教一下LZ,关于第三题,O(n)的做法是不是找到最短边a,次短边b和最长边c,然后比较是否a+b>c?
然后如果是 ...

1.是的,我一开始就只想到O(n3)的暴力破解,写了一半想到先排序一下然后找最短两条边和最长边来比较(O(nlogn))然后发现根本不需要排序-google 1point3acres
2.是的,只需要比较连续的三个getNext()就可以。
回复

使用道具 举报

我的人缘0
 楼主| 四面·楚歌 发表于 2018-2-25 12:22:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (8)
 
 
0% (0)  踩
Googlehsie 发表于 2018-2-25 10:31
楼主都能秒杀题目 太屌了!!!!!

还好,还好。运气也占了一部分的4轮没考到我不那么擅长的算法,比如没见过的dp题。. visit 1point3acres for more.
感觉休息得好也很重要。我是前一天早睡,当天早起,早餐俩煮鸡蛋,感觉自己大脑能超频。
回复

使用道具 举报

我的人缘0
Yanainusa 发表于 2018-2-26 05:29:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (37)
 
 
0% (0)  踩
四面·楚歌 发表于 2018-2-25 10:08
我的第一想法也是这样的只是时间复杂度是O(mn),太大了。
最后用的多源BFS。时间复杂度O(mn)
...
.留学论坛-一亩-三分地
请问楼主为什么复杂度从O(mn2)降到了O(mn)啊?m和n分别是矩阵的长和宽么?
回复

使用道具 举报

我的人缘0
huzhouwjj 发表于 2018-2-26 07:29:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (70)
 
 
0% (0)  踩
Yanainusa 发表于 2018-2-26 05:29.1point3acres网
请问楼主为什么复杂度从O(mn2)降到了O(mn)啊?m和n分别是矩阵的长和宽么?

应该是可以类似于dp一样储存每个数到4的最短距离吧?这样的话,最多每个数遍历一遍。
回复

使用道具 举报

我的人缘0
BigShaun 发表于 2018-2-26 11:40:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
电面那题LZ能把思路详细的说下吗? 谢谢
回复

使用道具 举报

我的人缘0
BigShaun 发表于 2018-2-26 11:40:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
我擦,,刷新就看到你楼上的回复了,,LOL
回复

使用道具 举报

我的人缘0
Yanainusa 发表于 2018-2-26 11:59:48 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (37)
 
 
0% (0)  踩
四面·楚歌 发表于 2018-2-26 11:39
m、n是长和宽。. from: 1point3acres
用多源BFS就是O(mn),把所有的5 push进queue然后BFS,找到4就停。所以时间复杂度是O(mn) ...

谢谢楼主回复,但仍然不清楚为什么一开始的解法的复杂度是O(mn2)。我的想法是:每次BFS复杂度是O(mn),假设5的个数是k,则复杂度是O(mnk)。请楼主解答
回复

使用道具 举报

我的人缘0
dlwlrma 发表于 2018-2-26 12:20:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  76% (10)
 
 
23% (3)  踩
Yanainusa 发表于 2018-2-26 11:59
谢谢楼主回复,但仍然不清楚为什么一开始的解法的复杂度是O(mn2)。我的想法是:每次BFS复杂度是O(mn),假 ...

我觉得是(mn)^2, 最坏的情况是矩阵全部由5,4组成,假设5有x个,4就是mn-x, 总的就是(mn-x)x, 这个乘积最大的情况是mn-x = x, 即x = (mn)/2时,这样复杂度就是(mn)^2了。
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-9-25 14:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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