一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4017|回复: 49
收起左侧

近期谷歌和F家面经,onsite+电面

[复制链接] |试试Instant~ |关注本帖
askyfeng 发表于 2015-10-30 12:35:43 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 博士 全职@GoogleFacebook - 内推 - 技术电面 Onsite |Passfresh grad应届毕业生

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

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

x
G家拿到了正式的offer,F家还没有,但是据recruiter说feedback looks very positive,我就姑且厚颜选了pass。
. 1point 3acres 璁哄潧
G家
电面:
H-Index. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我G家的电面是8月面的,但是leetcode还没有这个题,而且我拿到的题目是
given an array, output a maximum k such that there are k elements larger than the value k.
面的时候,面试官和我说先来个简单的,结果就是这个题,我理解这个题就用了好一会儿,心想这怎么简单了。O(nlogn)的解法其实挺直接的,但是我觉得这个太简单了,G不可能,所有挣扎着想出了个O(n)的解法,就是用bucket sort的思路。

第二天,我去实验室就和印度姐姐分享了这个题,一周后印度姐姐在G的onsite上又遇到这个题,我才知道叫H-index,可惜印度姐姐我和她说了做法,她还是没做出来,最后挂掉了

面试过程中,我的电脑蓝屏了一次,重启浪费了10分钟,面试小哥一直不说话,我说好几句,他才一个嗯,一个啊。最后剩8、9分钟的时候写完,也没有给第二题。那时我觉得完了,因为只做了一个简单的题。面试之前coordinator说是两轮coding interview,所以那时我是祈祷能拿到第二轮的。一周后coordinator告诉我小哥给的是very excellent,然后我的第二轮电面直接免了。

Onsite:
我onsite是10月面的,至于为什么拖这么久,请参考“我和微软的故事(过几天再写)”。
onsite round 1:
A. 给定一个产生[0,1]直接随机数的函数,以及一个三角形。要求调用这个函数随机产生一个在三角形内的点
B. 给一个string,比如aababbc,然后对字母重新排序,使得相邻的字母都不相同,比如abcabab。

onsite round 2:
给出一些string,每一个都是一个不包含"/"的路径,比如“usrbinpython”,“usrbinperl”,“usrbinjava”,然后要求输出最有可能的路径,比如这个例子就应该输出"usrbin/java", "usrbin/p/ython", "usrbin/p/erl". 还有一些follow-up,比如怎样避免这个p被劈开,当输入数据很大的时候,怎样选最有可能的路径之类的。. more info on 1point3acres.com
这题应该是用trie吧?我反正也是挣扎了很久,写了满满一大黑板,有时候改了后面还要改前面,然后面试官就一直跟着我拍照。

onsite round 3:
给一个linkedlist,然后给了一些node。要求输出有几个group,group的定义是连在一起的node就算一个group。比如linkedlist是这样的1->2->3->4->5->6->7->8->9, 然后给的弄得是[3,4,7,2,5], 那就输出3
这题也是有很多优化和边角讨论

onsite round 4:
system design. 貌似是design了一个table什么的,想不起来具体的细节了 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

onsite round 5:
一个binary image的编码,问怎么样编码最好。答案是4-tree,就是每次把图片分成4块,如果每一块只有一种颜色,就用一个leaf表示,否则就继续四分下去。
题目就是,怎样把两棵这样的4-trees合并起来




Facebook:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
电面 1
tree level order traversal。正常方法用queue写完后,要求用更少的space。我当时提出了用populating next right pointer的写法来写,这样时间是O(n), 空间是O(1).但是可能因为是电话,我解释的不好,面试官好像没听懂,他没接受这个解法。后来经过他的提示,要求我写的是时间O(nlogn),空间O(logn)的,就是给把tree多扫描几次,每次遇到需要打印的level就打印,不需要的就不打印。

我当时的感觉是,这个解法有必要写吗?我觉得我要是一开始写得是这个才要挂。。。人家是优化,这个简直就是劣化。。

电面 2
leetcode range search
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴. From 1point 3acres bbs
onsite round 1
要我讲一个project,中间就是各种问题,包括针对project的和行为题

onsite round 2
system design. 设计facebook的post search,分为在所有post中search和在朋友圈中search.鏈枃鍘熷垱鑷1point3acres璁哄潧

onsite round 3
国际象棋的knight的走法,在一个无限大的棋盘上给出任意两点A和B,另外有些地方有障碍和跳步,求问knight能否从A走到B。这个题是早期的游戏题,我在codingame上见过,我自己也曾经写过。

onsite round 4
A. 类似于minimum size subarray sum. 给定一个array,全部都是非负的elements,以及一个target,求问是否有一个连续的sub-array,里面所有的数加起来等于这个target。
B. 这个array是正常的数组,就是包含正数和负数.1point3acres缃

onsite round 5
system design: facebook上的ad recommendation


整体感觉就是G家确实非常的难,有几题同期的面经中出现过,但是我面的时候都没见过;而且面经的量非常的大。相同点就是他们应该都是很看重交流和沟通能力的,快速解题固然重要,但是更重要的是要把思路讲清楚,能够根据考官的提示作不同的发散性思考,能对model进行抽象,能类比和归纳。更多的心得体会以后如果拿到了Fb家的offer再写。. from: 1point3acres.com/bbs




补充内容 (2015-10-30 13:46):
Google onsite 3 那个例子输出应该是2,我写错了
Google onsite 5,合并的规则是,在某个pixel位置,如果两个图片相应的pixel都是黑的,那么合并后也是黑的;否则就是白的

补充内容 (2015-11-4 03:45):
Facebook挂掉了,反馈说是large scale design没答好,不过这个也真是超出我能力之外了

评分

4

查看全部评分

本帖被以下淘专辑推荐:

 楼主| askyfeng 发表于 2015-10-31 05:14:27 | 显示全部楼层
Ziyan 发表于 2015-10-31 04:00
求问怎么映射 能具体说说吗 谢谢

我觉得面google有一个很明显的感觉,就是他们非常看重思路。其实说实话,我觉得我的题挺难的。现在你们可能不觉得难,因为你们都看到过面经,有思考过。但是这些面经都是和我差不多一个时候出来的,我面的时候一道题都没见过。这些题如果让我在家一个人做的话,我肯定在45分钟内做不出来。

在Google面试的时候是会有很多提示的,你需要做的就是分析题目,哪里有问题,哪里可以优化,优化的选项什么的,然后你在卡住的地方打几个圈,面试官就会恰到好处地提示你一两句,以保证你在分析的时候的思路的流畅。等你分析完了,你就知道怎么做了,然后写程序和test case就很流畅了。

三角形这个题,一开始你就用最最直接的办法,就是构建一个包围着三角形的矩形,然后用给的那个函数产生两个随机数,再映射到矩形里。然后根据定理算出这个点再三角形里面还是外面,如果在外面就扔了找下一个。

然后这个时候面试官就会问你,如果产生随机函数非常贵怎么办?然后你就要分析,这个很贵的话,对什么有影响,怎样减少影响。你就知道问题在于当三角形很斜或者很长的时候,大部分点都不在三角形里面,导致很多计算是浪费的。那么问题来了,怎样才能避免这种浪费?答案是很显而易见的,就是用两个一样的三角形构建平行四边形,这样每一个点都不会浪费。但是问题又来了,给的随机数是在0~1之间,但是平行四边形可能是斜的,不能完美得利用产生的0~1之间的数,怎么办?所以顺理成章的,你可以把平行四边形上面的三角形剪下放到下面,左边的剪下放到右边,就变成一个正放的面积一样的矩形。这个题我就完成到这,至于是不是最优答案,我也不知道。

我面google的时候,几乎每个题都是这样出来的;我面别的公司也从来没有像有些大神一样秒杀某些题,都是这样一步步分析出来的。所以我面的时候基本上一轮只能做出一道题。所以只要有清晰的思路,展现出思考的过程以及灵活思辨的能力,就算做题不快,我个人觉得应该也没问题。

评分

3

查看全部评分

回复 支持 4 反对 0

使用道具 举报

doudoujiejie 发表于 2015-11-13 17:26:50 | 显示全部楼层
三角形那题 参考这个博客 https://adamswaab.wordpress.com/2009/12/11/random-point-in-a-triangle-barycentric-coordinates/
回复 支持 1 反对 0

使用道具 举报

mmliu 发表于 2015-11-16 16:56:37 | 显示全部楼层
谢谢楼主分享. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

Google onsite round 3的那题没太看懂意思. 1point 3acres 璁哄潧

连在一起的node就算一个group, 连在一起是啥意思,相邻么?

没懂为啥list: 1->2->3->4->5->6->7->8->9, node 是[3,4,7,2,5], 输出会是 2
回复 支持 1 反对 0

使用道具 举报

danchou 发表于 2015-10-31 13:24:42 | 显示全部楼层
我和楼主有同感,当时去面G家时候虽然有两题是见过面经的,但是在家看面试时候都没做出来,要么就是做出来的方法很挫。然后onsite的时候各种讨论,最后给的解法都跟在家里想的不一样。所以G家感觉还是很看思路的。希望能帮助到大家。
回复 支持 1 反对 0

使用道具 举报

hwberg 发表于 2015-10-30 14:58:12 | 显示全部楼层
三角形那题是把三角形映射成一个矩形吗?
两个三角形 -> 棱形 -> 矩形 (两个随机数定义矩形内任意一点)
回复 支持 1 反对 0

使用道具 举报

 楼主| askyfeng 发表于 2015-10-30 13:57:20 | 显示全部楼层
xiaozhuxiaozhu 发表于 2015-10-30 13:44
lz申请google,facebook都是内推么

是的。但是G感觉推不推关系也不大,内推领进门,修行靠个人
回复 支持 0 反对 1

使用道具 举报

2ndpoet 发表于 2015-10-30 12:46:37 | 显示全部楼层
首先恭喜楼主!楼主可以具体讲一讲GOOGLE onsite round 5的题吗?合并两个4-Tree有什么准则吗?
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-10-30 13:37:32 | 显示全部楼层
多谢分享!
有几个问题想问一下哈!
第一题0~1的随机数和三角形的三个点有啥关系呢?
第三题给的例子为啥是3组。。我觉得是2组。。“”有很多优化和边角讨论“” 可以举几个例子嘛
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2015-10-30 13:44:42 | 显示全部楼层
lz申请google,facebook都是内推么
回复 支持 反对

使用道具 举报

 楼主| askyfeng 发表于 2015-10-30 13:44:53 | 显示全部楼层
marthew777 发表于 2015-10-30 13:37-google 1point3acres
多谢分享!
有几个问题想问一下哈!
第一题0~1的随机数和三角形的三个点有啥关系呢?

1. 没关系的,就是那个函数能输入一个0~1的随机数。三角形的三个点是另给的
. 1point3acres.com/bbs2. 我写错了,应该是2
回复 支持 反对

使用道具 举报

 楼主| askyfeng 发表于 2015-10-30 13:46:48 | 显示全部楼层
2ndpoet 发表于 2015-10-30 12:46. Waral 鍗氬鏈夋洿澶氭枃绔,
首先恭喜楼主!楼主可以具体讲一讲GOOGLE onsite round 5的题吗?合并两个4-Tree有什么准则吗?

Google onsite 5,合并的规则是,在某个pixel位置,如果两个图片相应的pixel都是黑的,那么合并后也是黑的;否则就是白的
回复 支持 反对

使用道具 举报

queeniejing 发表于 2015-10-30 14:10:37 | 显示全部楼层
恭喜lz   lz能分享下 怎么准备fb design 面试吗
回复 支持 反对

使用道具 举报

 楼主| askyfeng 发表于 2015-10-31 01:52:45 | 显示全部楼层
queeniejing 发表于 2015-10-30 14:10
恭喜lz   lz能分享下 怎么准备fb design 面试吗

我几乎没准备,就看了下hiredintech。

我也试图准备,但是看各种文章,里面各种链接晕头转向,各种engineering blog,各种cache,memory,线程什么的,完全看不懂,后来就放弃了。. from: 1point3acres.com/bbs

我只看完整了tinyurl那个题,然后面到design的时候就按着那个思路来的。感觉design这个东西也没法准备,如果自己没做过project的话,只能完全靠记忆了,而且别人一问细节怎么处理就不会了,所以后来我也放弃准备了
回复 支持 反对

使用道具 举报

 楼主| askyfeng 发表于 2015-10-31 01:53:09 | 显示全部楼层
hwberg 发表于 2015-10-30 14:58
三角形那题是把三角形映射成一个矩形吗?
两个三角形 -> 棱形 -> 矩形 (两个随机数定义矩形内任意一点)
.鏈枃鍘熷垱鑷1point3acres璁哄潧
正解,就是这么做的

补充内容 (2015-10-31 01:53):.1point3acres缃
是我这么做的,不知道还有没有别的方法
回复 支持 反对

使用道具 举报

Ziyan 发表于 2015-10-31 04:00:50 | 显示全部楼层
hwberg 发表于 2015-10-30 14:58
三角形那题是把三角形映射成一个矩形吗?
两个三角形 -> 棱形 -> 矩形 (两个随机数定义矩形内任意一点)
. 1point3acres.com/bbs
求问怎么映射 能具体说说吗 谢谢
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-10-31 04:36:37 | 显示全部楼层
hwberg 发表于 2015-10-30 14:58. visit 1point3acres.com for more.
三角形那题是把三角形映射成一个矩形吗?
两个三角形 -> 棱形 -> 矩形 (两个随机数定义矩形内任意一点)

犀利!多谢分享
回复 支持 反对

使用道具 举报

alvinca123 发表于 2015-10-31 04:59:39 | 显示全部楼层
好详细,赞一个。
回复 支持 反对

使用道具 举报

Ziyan 发表于 2015-10-31 05:42:55 | 显示全部楼层
askyfeng 发表于 2015-10-31 05:14
我觉得面google有一个很明显的感觉,就是他们非常看重思路。其实说实话,我觉得我的题挺难的。现在你们可 ...

觉得LZ的题很难  不过LZ的分析能力真的很强 赞一个!     恭喜拿到offer  
回复 支持 反对

使用道具 举报

stonezms 发表于 2015-10-31 05:46:17 | 显示全部楼层
请问下,Facebook onsite round 4 B 正常数组(包含正负)求subarray和等于target的那题怎么做的啊?
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-10-31 07:14:21 | 显示全部楼层
askyfeng 发表于 2015-10-31 05:14
我觉得面google有一个很明显的感觉,就是他们非常看重思路。其实说实话,我觉得我的题挺难的。现在你们可 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
请问三角形这题需要写完整代码吗?
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-10-31 07:40:54 | 显示全部楼层
marthew777 发表于 2015-10-31 07:14
请问三角形这题需要写完整代码吗?

两个向量加一下就好啦
比如说以某点为原点,
向量a,b是两条边,. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
那么取两个随机数, x<-(0,1), y<-(0,1)  p = x*|a|, q= 0.5*y*|b|
那么随机点的坐标就是 p*a+q*b
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 18:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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