谈谈使用过的几款咖啡机

一亩三分地论坛

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

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1616|回复: 30
收起左侧

新鲜出炉的G家面经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
四面·楚歌 发表于 2018-2-24 09:42:20 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

x
春节前拿到的onsite通知,初八(今天)面试。
. From 1point 3acres bbs
第一轮:特友好的国人妹子(据说刚来一个月),先扯了几句闲话,开始做题。第一题:给一个array of binary tree node,问能否组成一个树(必须并且只能用上所有给的node,只能组出一棵树)。用hashmap存每个node的parent,然后找那唯一的一个没有parent的node为root,BFS检测环路。剩15分钟第二题:定义一个横向一维棋盘,上面有两种棋子L和R若干,L只能往左走,R只能往右走,并且棋子不可以跨越其他棋子移动。给出起始状态和终点状态,问能否到达。序列对比+起始-终点状态检测秒了。
. 1point3acres
第二轮:老美。LC340。follow up,如果string太长无法存进内存,只能用getNext()获取下一个字符,该怎么修改算法。. more info on 1point3acres

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

第三轮:老美。第一题:给一个整数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|主题: 41, 订阅: 15
我的人缘0
BigShaun 发表于 2018-3-2 10:55:19 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
21kekeke 发表于 2018-2-27 08:27
楼主请问一下第二题 lc340的followup 是不是还是一样 用hashmap存每个char的latest position?

如果用java的话可以用LinkedHashMap,可以很容易保存一个队没个char最后出现index的表。类似LRU
回复 支持 1 反对 0

使用道具 举报

我的人缘0
 楼主| 四面·楚歌 发表于 2018-2-26 11:39:23 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Yanainusa 发表于 2018-2-26 05:29.本文原创自1point3acres论坛
请问楼主为什么复杂度从O(mn2)降到了O(mn)啊?m和n分别是矩阵的长和宽么?
. From 1point 3acres bbs
m、n是长和宽。.本文原创自1point3acres论坛
用多源BFS就是O(mn),把所有的5 push进queue然后BFS,找到4就停。所以时间复杂度是O(mn)。. visit 1point3acres for more.
如果需要返回路径也一样,记录parent最后backtrack就好。
回复 支持 1 反对 0

使用道具 举报

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


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

评分

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

查看全部评分

回复 支持 反对

使用道具 举报

我的人缘0
橙小夕 发表于 2018-2-24 16:26:05 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
想问问楼主电面面经是啥
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

我的人缘0
 楼主| 四面·楚歌 发表于 2018-2-25 06:52:01 | 显示全部楼层
  此人我要顶:
 
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% (暂未有人投票) 【我投】
第四题是气散气
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
cmuqiyihu 发表于 2018-2-25 08:47:08 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
感觉你和我同一天面的那个同学。。。感觉你这个面试很有希望呀!!! 顶一个
回复 支持 反对

使用道具 举报

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

我个人的想法是对每一个5都找一遍到4的最短距离,然后输出最短的那个,不知道对不对。
回复 支持 反对

使用道具 举报

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

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

回复 支持 反对

使用道具 举报

我的人缘0
dawskiper 发表于 2018-2-25 10:28:01 | 显示全部楼层
  此人我要顶:
 
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 | 显示全部楼层
  此人我要顶:
 
50% (2) 【我投】
  此人我要踩:
 
50% (2) 【我投】
楼主都能秒杀题目 太屌了!!!!!
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

我的人缘0
 楼主| 四面·楚歌 发表于 2018-2-25 12:22:25 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Googlehsie 发表于 2018-2-25 10:31
楼主都能秒杀题目 太屌了!!!!!
.本文原创自1point3acres论坛
还好,还好。运气也占了一部分的4轮没考到我不那么擅长的算法,比如没见过的dp题。
感觉休息得好也很重要。我是前一天早睡,当天早起,早餐俩煮鸡蛋,感觉自己大脑能超频。
回复 支持 反对

使用道具 举报

我的人缘0
Yanainusa 发表于 2018-2-26 05:29:18 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
四面·楚歌 发表于 2018-2-25 10:08
我的第一想法也是这样的只是时间复杂度是O(mn),太大了。. 1point3acres
最后用的多源BFS。时间复杂度O(mn). 1point3acres
...

请问楼主为什么复杂度从O(mn2)降到了O(mn)啊?m和n分别是矩阵的长和宽么?
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

我的人缘0
BigShaun 发表于 2018-2-26 11:40:21 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
电面那题LZ能把思路详细的说下吗? 谢谢
回复 支持 反对

使用道具 举报

我的人缘0
BigShaun 发表于 2018-2-26 11:40:51 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
我擦,,刷新就看到你楼上的回复了,,LOL
回复 支持 反对

使用道具 举报

我的人缘0
Yanainusa 发表于 2018-2-26 11:59:48 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
四面·楚歌 发表于 2018-2-26 11:39
m、n是长和宽。
用多源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 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
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

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

custom counter

GMT+8, 2018-6-25 06:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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