找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 5010|回复: 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 V3 I$ p1 t/ r8 f/ J) Q- q4 {! a
1 R; b! `0 q! L: _遵照我在群里的承诺,拿到G家offer面经,今晚先发G、F和两个游戏公司的,这周周末前我会把其他公司面经整理出来;如果拿到F家offer,我会发一个面试心得和提供一些面试准备的建议。
4 D3 [- B: m( ~" X9 Y( i" `9 k5 b
) N1 ~/ b. \3 b9 NG家- `/ h5 S/ q  u! \2 Y. @8 P
电面
+ d  _, J, U8 y" M" |) z% _# wH-Index8 V- n! |: o+ b; N6 a- Y% F8 ]
我G家的电面是8月面的,但是leetcode还没有这个题,而且我拿到的题目是
! J( o1 O/ ^6 G$ i0 jgiven an array, output a maximum k such that there are k elements larger than the value k.
* N* r9 l' n& h( j$ `5 N! Z面的时候,面试官和我说先来个简单的,结果就是这个题,我理解这个题就用了好一会儿,心想这怎么简单了。O(nlogn)的解法其实挺直接的,但是我觉得这个太简单了,G不可能,所有挣扎着想出了个O(n)的解法,就是用bucket sort的思路。# c3 M: {, b2 b% X5 Z. ?4 \" A- _' j

6 `' @( q. e4 E: }第二天,我去实验室就和印度姐姐分享了这个题,一周后印度姐姐在G的onsite上又遇到这个题,我才知道叫H-index,可惜印度姐姐我和她说了做法,她还是没做出来,最后挂掉了
. V  ?  t% V) |0 j9 l. D. s6 H1 U
8 P) E+ v+ N9 H7 v面试过程中,我的电脑蓝屏了一次,重启浪费了10分钟,面试小哥一直不说话,我说好几句,他才一个嗯,一个啊。最后剩8、9分钟的时候写完,也没有给第二题。那时我觉得完了,因为只做了一个简单的题。面试之前coordinator说是两轮coding interview,所以那时我是祈祷能拿到第二轮的。一周后coordinator告诉我小哥给的是very excellent,然后我的第二轮电面直接免了。. W8 g2 r  V  u5 @6 n

, e0 ?  E: }( ]' R* \. E  q% fOnsite:
6 @( _; _( ~8 h( U. K. z& _onsite是10月面的,至于为什么拖这么久,请参考“我和微软的故事(过几天再写)”。
3 R4 \' w6 P) [onsite round 1:: s; C  I; K6 z! s1 n
A. 给定一个产生[0,1]直接随机数的函数,以及一个三角形。要求调用这个函数随机产生一个在三角形内的点
  R% \! o% \% ?4 R0 R/ x! \6 zB. 给一个string,比如aababbc,然后对字母重新排序,使得相邻的字母都不相同,比如abcabab。
7 x5 O0 S, A, W" V+ y# c  w1 c$ H/ H- M2 P
onsite round 2:  j) B- l$ ]0 V" Y+ z0 l: c& o' q$ a
给出一些string,每一个都是一个不包含"/"的路径,比如“usrbinpython”,“usrbinperl”,“usrbinjava”,然后要求输出最有可能的路径,比如这个例子就应该输出"usrbin/java", "usrbin/p/ython", "usrbin/p/erl". 还有一些follow-up,比如怎样避免这个p被劈开,当输入数据很大的时候,怎样选最有可能的路径之类的。( d% d3 S8 W- x* |
这题应该是用trie吧?我反正也是挣扎了很久,写了满满一大黑板,有时候改了后面还要改前面,然后面试官就一直跟着我拍照。
) |% _- s; P, I+ ~' t
6 ?% T7 `* G1 E% }! Tonsite round 3:% p4 G! w/ {  m. H& r/ h3 ?& m2 H
给一个linkedlist,然后给了一些node。要求输出有几个group,group的定义是连在一起的node就算一个group。比如linkedlist是这样的1->2->3->4->5->6->7->8->9, 然后给的弄得是[3,4,7,2,5], 那就输出3
7 B4 f% C) Q) t+ D' q; O1 u这题也是有很多优化和边角讨论
) C) S5 k2 x2 J, p9 J% |/ l( Z! {8 P! e) k2 ^$ @. J+ n% h" g
onsite round 4:
; k8 s, `- [- t% g' o! Usystem design. 貌似是design了一个table什么的,想不起来具体的细节了* ]2 |( k* V4 Z3 e
' ?0 }  V; Y3 D5 g7 l
onsite round 5:
6 f- N4 |8 ?: S  M2 B7 S$ U一个binary image的编码,问怎么样编码最好。答案是4-tree,就是每次把图片分成4块,如果每一块只有一种颜色,就用一个leaf表示,否则就继续四分下去。- M. `" I- k& J! X
题目就是,怎样把两棵这样的4-trees合并起来
3 b; d  }  r4 |& d8 N& e9 u0 G% W$ t! o$ T% {# z0 j8 b

; ]9 s  }& H. [* E$ Y8 ^' z; p7 e
9 \3 I+ `* G/ ~7 {5 C
Facebook:/ j1 E$ t+ O8 z. i4 ^  b, q- g
电面 1- ^" j, n4 C, Y
tree level order traversal。正常方法用queue写完后,要求用更少的space。我当时提出了用populating next right pointer的写法来写,这样时间是O(n), 空间是O(1).但是可能因为是电话,我解释的不好,面试官好像没听懂,他没接受这个解法。后来经过他的提示,要求我写的是时间O(nlogn),空间O(logn)的,就是给把tree多扫描几次,每次遇到需要打印的level就打印,不需要的就不打印。
6 M4 p+ [% e. z: E' t
) M$ d5 ~3 c7 }9 D$ ~我当时的感觉是,这个解法有必要写吗?我觉得我要是一开始写得是这个才要挂。。。人家是优化,这个简直就是劣化。。
# u( r0 \0 J& S. H- u2 V6 U" ~/ E  L- p7 q4 q
电面 2  {% \1 T, P& J4 O/ I7 Z
leetcode range search( d: B. c! M$ u* P/ `

6 A, s6 Q& O6 W' r: vonsite round 1
/ [* l, O$ M, V要我讲一个project,中间就是各种问题,包括针对project的和行为题$ J" k: T0 L) v; N4 H

: T2 [( l7 Z" z1 Uonsite round 2
. X) m! e$ u/ U  k6 A. M* l) h" w( Ksystem design. 设计facebook的post search,分为在所有post中search和在朋友圈中search
9 L( z5 Q. q+ l/ O
" Z8 _$ @( `- G4 n3 n  A# fonsite round 3
+ L% G2 a7 d9 T  w6 w2 c& X' y3 v国际象棋的knight的走法,在一个无限大的棋盘上给出任意两点A和B,另外有些地方有障碍和跳步,求问knight能否从A走到B。这个题是早期的游戏题,我在codingame上见过,我自己也曾经写过。" J5 J' Q' y! ^! D7 U9 R9 }( v

: Q# L  I/ }( f+ @( |: ~" Ronsite round 4
: y7 Q9 A( ~, _& l" YA. 类似于minimum size subarray sum. 给定一个array,全部都是非负的elements,以及一个target,求问是否有一个连续的sub-array,里面所有的数加起来等于这个target。
8 H  n5 d$ a" `, q( dB. 这个array是正常的数组,就是包含正数和负数
+ b7 s, D" a, W% T+ M/ P- M( c5 J7 {) U+ O' u
onsite round 5
8 u& I/ q. G8 ]# c( y6 M- Osystem design: facebook上的ad recommendation5 h1 B( S9 w" J) g6 E& R
/ H! T8 v8 d) E' x. u* j5 |+ _
整体感觉就是G家确实非常的难,有几题同期的面经中出现过,但是我面的时候都没见过;而且面经的量非常的大。相同点就是他们应该都是很看重交流和沟通能力的,快速解题固然重要,但是更重要的是要把思路讲清楚,能够根据考官的提示作不同的发散性思考,能对model进行抽象,能类比和归纳。更多的心得体会以后再写。& \. C$ y/ ^7 t2 J1 T9 M

6 l+ {4 e8 Z. L3 o
9 J! O+ P) k3 G5 ^% }+ \  d( B0 ^. {1 o( z4 ?& i) q2 t
补充内容 (10-29-2015 11:50 PM):1 A6 e$ j7 g5 y' K& d% R5 G
Google onsite 3,那个例子应该输出2
7 H7 K1 Z& A& q8 A1 b0 w8 v
8 v& y7 J0 I# I, N$ o补充内容 (11-3-2015 05:05 PM):6 S( r+ I9 c, r! Z4 T  ?
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专业!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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