找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 5238|回复: 10
收起左侧

[米群网大牛独家面经总结] 15年10月,G和F家面经

[复制链接]

22

主题

6

精华

300

积分

高级会员

Rank: 3Rank: 3

积分
300
发表于 10-29-2015 11:30 PM | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 Sophia 于 10-29-2015 11:38 PM 编辑
1 m; ^3 x: Y& C- g  C
' J7 I  y3 C/ `2 N遵照我在群里的承诺,拿到G家offer面经,今晚先发G、F和两个游戏公司的,这周周末前我会把其他公司面经整理出来;如果拿到F家offer,我会发一个面试心得和提供一些面试准备的建议。# _. P3 y5 v% J% D$ e" Z9 F

2 `5 Y! _8 w- H! X1 h1 `7 yG家4 W8 e: e* U4 u4 h" `
电面9 R( H; d# e$ M4 N+ y
H-Index9 M7 p2 c$ X5 Y' {0 e+ j7 }
我G家的电面是8月面的,但是leetcode还没有这个题,而且我拿到的题目是2 x# Z" `! e3 _. g! `, x! H
given an array, output a maximum k such that there are k elements larger than the value k.
) l1 c, t+ E7 {2 E面的时候,面试官和我说先来个简单的,结果就是这个题,我理解这个题就用了好一会儿,心想这怎么简单了。O(nlogn)的解法其实挺直接的,但是我觉得这个太简单了,G不可能,所有挣扎着想出了个O(n)的解法,就是用bucket sort的思路。
3 U" i4 [5 G8 ^0 E( R. m# [2 c) }% a9 v% b2 D
第二天,我去实验室就和印度姐姐分享了这个题,一周后印度姐姐在G的onsite上又遇到这个题,我才知道叫H-index,可惜印度姐姐我和她说了做法,她还是没做出来,最后挂掉了
/ d. `" U1 ?7 t$ J- k" s0 m% d, M. J1 `9 y) i8 q) T
面试过程中,我的电脑蓝屏了一次,重启浪费了10分钟,面试小哥一直不说话,我说好几句,他才一个嗯,一个啊。最后剩8、9分钟的时候写完,也没有给第二题。那时我觉得完了,因为只做了一个简单的题。面试之前coordinator说是两轮coding interview,所以那时我是祈祷能拿到第二轮的。一周后coordinator告诉我小哥给的是very excellent,然后我的第二轮电面直接免了。' _( z' x2 K/ h; J1 U1 T

  R2 W1 k1 ]6 J" BOnsite:* R; E! Q  S6 P' v6 e  N! ^/ J
onsite是10月面的,至于为什么拖这么久,请参考“我和微软的故事(过几天再写)”。
* s- @* P) ~  S, E, Zonsite round 1:
/ q  {2 ~4 ^, C, [" w5 D* KA. 给定一个产生[0,1]直接随机数的函数,以及一个三角形。要求调用这个函数随机产生一个在三角形内的点
6 a% N8 n) J! _% n' f5 WB. 给一个string,比如aababbc,然后对字母重新排序,使得相邻的字母都不相同,比如abcabab。1 |$ Z6 w+ g* W- I+ s' H' ^4 j

9 k1 |6 \0 d8 A' v+ [+ Konsite round 2:
' \( ?$ m/ W' G  D2 p给出一些string,每一个都是一个不包含"/"的路径,比如“usrbinpython”,“usrbinperl”,“usrbinjava”,然后要求输出最有可能的路径,比如这个例子就应该输出"usrbin/java", "usrbin/p/ython", "usrbin/p/erl". 还有一些follow-up,比如怎样避免这个p被劈开,当输入数据很大的时候,怎样选最有可能的路径之类的。5 t2 j2 o9 i3 c! p8 y6 i  z" P
这题应该是用trie吧?我反正也是挣扎了很久,写了满满一大黑板,有时候改了后面还要改前面,然后面试官就一直跟着我拍照。
! ~5 o. D0 z4 J, U4 b' k% S* K; t3 u- V" I
onsite round 3:
' A: j8 B) @$ B* |; Q8 T' ^/ k给一个linkedlist,然后给了一些node。要求输出有几个group,group的定义是连在一起的node就算一个group。比如linkedlist是这样的1->2->3->4->5->6->7->8->9, 然后给的弄得是[3,4,7,2,5], 那就输出3
( U8 m, ?. Y" P3 H这题也是有很多优化和边角讨论2 Q) T. Z$ I1 I- }$ T

4 y1 j2 m/ v* o9 i0 F, {5 {onsite round 4:
! h5 _' o# U- F8 g9 ]system design. 貌似是design了一个table什么的,想不起来具体的细节了5 x! F  U6 M. O7 s' `1 W3 Y6 |
! g! X4 \% ^& G
onsite round 5:9 `4 d+ Y9 [9 S, B$ y  u* _4 H
一个binary image的编码,问怎么样编码最好。答案是4-tree,就是每次把图片分成4块,如果每一块只有一种颜色,就用一个leaf表示,否则就继续四分下去。
6 Q' N  e- v2 @  M0 l' J题目就是,怎样把两棵这样的4-trees合并起来7 R0 M( [8 _( u9 S1 K$ U

7 k+ H2 h( B4 j/ U1 u2 j' M' D" O8 a1 V3 }( J6 ?

7 k  [, @) m& y- r% s7 r- E% j7 m2 {$ i7 Q6 l
Facebook:
! G/ G( i& a- Q/ B6 L' U8 ]3 X电面 1: `9 b0 B: N; V- H8 o$ g
tree level order traversal。正常方法用queue写完后,要求用更少的space。我当时提出了用populating next right pointer的写法来写,这样时间是O(n), 空间是O(1).但是可能因为是电话,我解释的不好,面试官好像没听懂,他没接受这个解法。后来经过他的提示,要求我写的是时间O(nlogn),空间O(logn)的,就是给把tree多扫描几次,每次遇到需要打印的level就打印,不需要的就不打印。* o/ Q0 M7 n4 @# I

; U# D+ c9 {' w$ K! Q9 o我当时的感觉是,这个解法有必要写吗?我觉得我要是一开始写得是这个才要挂。。。人家是优化,这个简直就是劣化。。# ], H* [  t+ \  ]

) ]% ?" T$ A* [' i# y/ N* Q1 j电面 2
: r# U* S( K* P/ s1 }2 k8 }leetcode range search1 v/ ?- v# c+ k6 N

$ s8 o- c: v; ~onsite round 1+ K7 \( m/ N% @
要我讲一个project,中间就是各种问题,包括针对project的和行为题
% [6 p6 J0 h- Z( n/ a; B4 f
' k2 T1 J4 X1 ~3 q4 Yonsite round 2
- o5 B% }0 m/ B" g* f7 Lsystem design. 设计facebook的post search,分为在所有post中search和在朋友圈中search
+ t& F  I6 h0 y& ?1 O" w7 u! a2 o1 I+ P
onsite round 3
, O, m/ |5 U1 ~国际象棋的knight的走法,在一个无限大的棋盘上给出任意两点A和B,另外有些地方有障碍和跳步,求问knight能否从A走到B。这个题是早期的游戏题,我在codingame上见过,我自己也曾经写过。0 v: k  i: W2 o7 K9 ^( P7 b5 l+ N
# J8 p% c* @* x
onsite round 4
! N, D- z7 Q, S- xA. 类似于minimum size subarray sum. 给定一个array,全部都是非负的elements,以及一个target,求问是否有一个连续的sub-array,里面所有的数加起来等于这个target。
" t3 U! L9 Q! G9 s" s: QB. 这个array是正常的数组,就是包含正数和负数
3 k( M- f+ l; s, |" n# ]& S, |7 c" R) v( M
onsite round 5
" U/ s' y& L6 z% ]: n$ \' n$ \( Tsystem design: facebook上的ad recommendation
" y, E6 m* Y4 Q. g) F% v  [  y7 v( m+ J0 S9 h) B: K% @4 r
整体感觉就是G家确实非常的难,有几题同期的面经中出现过,但是我面的时候都没见过;而且面经的量非常的大。相同点就是他们应该都是很看重交流和沟通能力的,快速解题固然重要,但是更重要的是要把思路讲清楚,能够根据考官的提示作不同的发散性思考,能对model进行抽象,能类比和归纳。更多的心得体会以后再写。' e$ E1 K1 G% U9 R
, I, k3 ^* b2 @& u* U

# ~: t6 N% v' n. ?  C6 }+ W
* s! j8 `- \7 p4 y补充内容 (10-29-2015 11:50 PM):
% w1 M; \8 K7 ^: E6 GGoogle onsite 3,那个例子应该输出2
/ G2 y/ @0 Q' X
! F8 Q" n3 E' a3 x补充内容 (11-3-2015 05:05 PM):7 T& R' h' q+ X6 W+ k" k4 q
Facebook已挂

评分

参与人数 1金钱 +30 收起 理由
Sophia + 30 感谢您的认真和用心的分享!大米满满送上!

查看全部评分

781

主题

575

精华

5670

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5670

活跃会员热心会员优秀版主

发表于 10-29-2015 11:38 PM | 显示全部楼层
感谢您这么详细的面经分享~~~精华积分满满送上了~~~也祝福您拿下dream offer~~~
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

781

主题

575

精华

5670

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5670

活跃会员热心会员优秀版主

发表于 10-29-2015 11:39 PM | 显示全部楼层
感谢大赞~回帖沾喜气~
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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