找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 792|回复: 1
收起左侧

[米群网Offer励志贴] 15年10月,G和F家面经

[复制链接]

22

主题

6

精华

300

积分

高级会员

Rank: 3Rank: 3

积分
300
发表于 10-30-2015 12:23 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 10-29-2015 11:38 PM 编辑

遵照我在群里的承诺,拿到G家offer面经,今晚先发G、F和两个游戏公司的,这周周末前我会把其他公司面经整理出来;如果拿到F家offer,我会发一个面试心得和提供一些面试准备的建议。

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被劈开,当输入数据很大的时候,怎样选最有可能的路径之类的。
这题应该是用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

onsite round 1
要我讲一个project,中间就是各种问题,包括针对project的和行为题

onsite round 2
system design. 设计facebook的post search,分为在所有post中search和在朋友圈中search

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是正常的数组,就是包含正数和负数

onsite round 5
system design: facebook上的ad recommendation

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



补充内容 (10-29-2015 11:50 PM):
Google onsite 3,那个例子应该输出2
来源: 15年10月,G和F家面经
发表于 10-30-2015 12:24 AM 来自美国米群网手机版 | 显示全部楼层
л澭~~~~~~dream offer~~~
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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