回国之前,写点东西和H1B了断。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
锦晖律师事务所
12月16日
H1B讲座通知
E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 2170|回复: 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太长无法存进内存
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
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|主题: 129, 订阅: 55
我的人缘0
BigShaun 发表于 2018-3-2 10:55:19 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  95% (20)
 
 
4% (1)  踩
21kekeke 发表于 2018-2-27 08:27
楼主请问一下第二题 lc340的followup 是不是还是一样 用hashmap存每个char的latest position?

如果用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
请问楼主为什么复杂度从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
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
-find的题号看错了.第四轮是柒叁柒和柒叁肆.
柒叁肆用union-find维护各个集合就可以了,每个集合内部单词彼此相似.

评分

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

查看全部评分

回复

使用道具 举报

我的人缘0
橙小夕 发表于 2018-2-24 16:26:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (38)
 
 
2% (1)  踩
想问问楼主
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
是啥
回复

使用道具 举报

我的人缘0
 楼主| 四面·楚歌 发表于 2018-2-25 06:48:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (8)
 
 
0% (0)  踩
dawskiper 发表于 2018-2-24 16:22
第一轮第二题是柒柒柒,第四轮是陆捌肆+陆捌伍
陆捌伍我看过的做法是,先找in-degree为2的点,如果能找到的话 ...

我的作法说白了就是分组,如果两个词是近义词,就分为一个组;如果两个词已经各自有组了,那么合并两个组。用两个map来存储分组信息,一个是某单词所属组的root单词,另一个是某root单词的所有组员,包括它自己。
回复

使用道具 举报

我的人缘0
 楼主| 四面·楚歌 发表于 2018-2-25 06:52:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (8)
 
 
0% (0)  踩
橙小夕 发表于 2018-2-24 16:26
想问问楼主电面面经是啥

我电面的题目是:给一个整型二维矩阵
比如:
1 5 6 3 5
2 6 1 2 3
1 3 6 4 9
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)  踩
感觉你和我同一天面的那个同学。。。
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
!! 顶一个

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


回复

使用道具 举报

我的人缘0
橙小夕 发表于 2018-2-25 09:56:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (38)
 
 
2% (1)  踩
四面·楚歌 发表于 2018-2-25 06:52
我电面的题目是:给一个整型二维矩阵
比如:
1 5 6 3 5

我个人的想法是对每一个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)
. 1point3acres
回复

使用道具 举报

我的人缘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,记录
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
eam来说,在这个点之后都存在符合条件的三个边.
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

手机版|小黑屋|一亩三分地留学网

GMT+8, 2018-12-11 07:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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