找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 4552|回复: 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 编辑
- a! u$ {' M7 p) i+ [+ g
2 }2 B) }" y2 ~5 c1 o5 k/ R遵照我在群里的承诺,拿到G家offer面经,今晚先发G、F和两个游戏公司的,这周周末前我会把其他公司面经整理出来;如果拿到F家offer,我会发一个面试心得和提供一些面试准备的建议。, d2 o) I( D9 n$ q! a+ W7 I

9 i" w& i7 K" P) l! z, hG家
1 @. S7 Y4 d2 W, n& g$ ?1 \电面6 ^5 }% ?8 ^- N7 ?
H-Index
: T: m+ z% A9 d6 m7 C我G家的电面是8月面的,但是leetcode还没有这个题,而且我拿到的题目是( s6 y8 p9 s7 S8 {4 y$ h
given an array, output a maximum k such that there are k elements larger than the value k.+ o2 ~) Y% [( g7 A8 `* i5 _1 O2 b
面的时候,面试官和我说先来个简单的,结果就是这个题,我理解这个题就用了好一会儿,心想这怎么简单了。O(nlogn)的解法其实挺直接的,但是我觉得这个太简单了,G不可能,所有挣扎着想出了个O(n)的解法,就是用bucket sort的思路。
) ^. Z, L5 J9 V8 k' f; w0 ?( \$ ]9 _/ i
第二天,我去实验室就和印度姐姐分享了这个题,一周后印度姐姐在G的onsite上又遇到这个题,我才知道叫H-index,可惜印度姐姐我和她说了做法,她还是没做出来,最后挂掉了4 J/ @; z$ X  T. s& b! Q$ x3 M, s
5 ~1 B% v. G5 o$ [- V# C
面试过程中,我的电脑蓝屏了一次,重启浪费了10分钟,面试小哥一直不说话,我说好几句,他才一个嗯,一个啊。最后剩8、9分钟的时候写完,也没有给第二题。那时我觉得完了,因为只做了一个简单的题。面试之前coordinator说是两轮coding interview,所以那时我是祈祷能拿到第二轮的。一周后coordinator告诉我小哥给的是very excellent,然后我的第二轮电面直接免了。8 w/ D. E- d! e1 A
* |0 E0 Y( k0 }. d5 Y; ~
Onsite:2 G9 u+ v0 N$ e; a& G$ S" u
onsite是10月面的,至于为什么拖这么久,请参考“我和微软的故事(过几天再写)”。
( t1 \; L1 [, B8 a3 lonsite round 1:) s" I( n/ N# q; d; N' I) P
A. 给定一个产生[0,1]直接随机数的函数,以及一个三角形。要求调用这个函数随机产生一个在三角形内的点( L) N: O1 u: {; y% f9 F
B. 给一个string,比如aababbc,然后对字母重新排序,使得相邻的字母都不相同,比如abcabab。
) j9 ~. ]  a6 B% H0 D' j2 B' p8 @
0 {- E% T3 j: b9 lonsite round 2:
. I$ i9 Y6 j$ i+ P* W5 D1 y给出一些string,每一个都是一个不包含"/"的路径,比如“usrbinpython”,“usrbinperl”,“usrbinjava”,然后要求输出最有可能的路径,比如这个例子就应该输出"usrbin/java", "usrbin/p/ython", "usrbin/p/erl". 还有一些follow-up,比如怎样避免这个p被劈开,当输入数据很大的时候,怎样选最有可能的路径之类的。4 g. ]( U  T1 q
这题应该是用trie吧?我反正也是挣扎了很久,写了满满一大黑板,有时候改了后面还要改前面,然后面试官就一直跟着我拍照。% u) K  g7 r8 F7 e  a  |
6 X" l. }6 v. E- B& i8 W0 G$ k
onsite round 3:3 H, [) H: d) H/ |# X+ P3 E' i$ F. b5 [
给一个linkedlist,然后给了一些node。要求输出有几个group,group的定义是连在一起的node就算一个group。比如linkedlist是这样的1->2->3->4->5->6->7->8->9, 然后给的弄得是[3,4,7,2,5], 那就输出3# l2 b/ g/ ]5 ^% {" m9 X
这题也是有很多优化和边角讨论
7 @9 e4 M- \% X, A" ]1 w/ B; C
& A/ G! S1 F1 M  K$ @& r5 l  [onsite round 4:
; @  |$ f% d2 i- E8 zsystem design. 貌似是design了一个table什么的,想不起来具体的细节了+ C6 k! V* P; O) u. b' T

" G' J! K1 ]7 q4 G6 _- E/ z, Donsite round 5:' ]6 v' N  ?: S1 _2 E4 G/ o
一个binary image的编码,问怎么样编码最好。答案是4-tree,就是每次把图片分成4块,如果每一块只有一种颜色,就用一个leaf表示,否则就继续四分下去。
- E) u% {7 Z& g# }2 ~题目就是,怎样把两棵这样的4-trees合并起来
$ h( I; ?% z7 D) I% m
0 W9 }$ ]  X% U; V+ E" l# d' E  O$ G& f: A- g
; O+ g6 k4 ?' A+ P0 T8 K" ?6 N
4 V) a: @! ?( A- J7 e
Facebook:' B: f  Q. o9 [6 l- n- _
电面 1
0 q1 A' }- z8 z% e) stree level order traversal。正常方法用queue写完后,要求用更少的space。我当时提出了用populating next right pointer的写法来写,这样时间是O(n), 空间是O(1).但是可能因为是电话,我解释的不好,面试官好像没听懂,他没接受这个解法。后来经过他的提示,要求我写的是时间O(nlogn),空间O(logn)的,就是给把tree多扫描几次,每次遇到需要打印的level就打印,不需要的就不打印。7 W0 ]  c2 l- [% {, D6 i
7 b) l: ~* q- F! ^4 ~7 I+ C
我当时的感觉是,这个解法有必要写吗?我觉得我要是一开始写得是这个才要挂。。。人家是优化,这个简直就是劣化。。" D9 }5 y) g! a+ u
* x2 c3 Q9 S& B; k6 e2 H7 Z; g
电面 2
4 E, p3 l( j  `$ E6 i7 Sleetcode range search+ G( m7 p" Y3 w
& m- M* D& R5 ^
onsite round 1- j0 E1 w2 }" L8 S; {+ d, T
要我讲一个project,中间就是各种问题,包括针对project的和行为题# }" v( [4 i; X) d  b7 g9 ?

" B; t9 A# O' B% N6 G+ Fonsite round 28 U) O. `5 u# ~$ b- `2 _
system design. 设计facebook的post search,分为在所有post中search和在朋友圈中search
: Q0 q. Z8 A$ L5 C8 @6 O  S1 w* r) w# y  H3 T+ ?" Z5 E7 W; z
onsite round 3
6 K, g3 h7 H) z国际象棋的knight的走法,在一个无限大的棋盘上给出任意两点A和B,另外有些地方有障碍和跳步,求问knight能否从A走到B。这个题是早期的游戏题,我在codingame上见过,我自己也曾经写过。5 e) x% g0 g4 Z. c! u
7 h. S0 `2 D" U: K4 o7 k" a! ?$ e9 |
onsite round 4
: V7 R1 c% @. o+ w) t0 JA. 类似于minimum size subarray sum. 给定一个array,全部都是非负的elements,以及一个target,求问是否有一个连续的sub-array,里面所有的数加起来等于这个target。, h7 A% h6 a7 u& i
B. 这个array是正常的数组,就是包含正数和负数
2 ~4 {( ~" h& I# L0 z
* e% x/ F6 b9 I1 }. n1 \onsite round 5
2 s+ s5 V  C$ x4 [. K6 Ssystem design: facebook上的ad recommendation
2 o/ N& h2 T# m# F6 J; b6 V, T* v; z$ W
整体感觉就是G家确实非常的难,有几题同期的面经中出现过,但是我面的时候都没见过;而且面经的量非常的大。相同点就是他们应该都是很看重交流和沟通能力的,快速解题固然重要,但是更重要的是要把思路讲清楚,能够根据考官的提示作不同的发散性思考,能对model进行抽象,能类比和归纳。更多的心得体会以后再写。" w# N# l  D  V4 O# R+ v

& B" K: \, K2 l# X) L: f; f4 l+ D  h( o0 w

6 w; y8 j/ @- t0 D; H. \7 v4 @$ E补充内容 (10-29-2015 11:50 PM):
2 f" B$ A! }8 u2 f  IGoogle onsite 3,那个例子应该输出2( E5 N4 m- j  t, O
$ Q# e! i' d$ B7 `9 ]
补充内容 (11-3-2015 05:05 PM):
/ L. V" A% l3 f4 XFacebook已挂

评分

参与人数 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专业!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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