励志贴: 报个G家offer+面筋

CHazyhabiT

% `7 g+ Q) P8 V7 h: [
从去年11月on campus，到圣诞前的on site，再到现在（1月）拿到offer，G家的面试贯穿了整个求职历程，报喜讯的同时顺便也把on site的面筋分享一下。

( A4 p9 }- h8 x
on campus面筋戳这里http://www.meetqun.com/thread-2227-1-1.html，on site有3轮，上午10点左右开始，午饭前两轮，午饭后一轮。

第一轮================================
" F  n  U2 M2 N1 P5 Kwarm up 小于5分钟，然后就开始做题，关于用树表达图像的题目。假设一个矩形画布（理解为一个区域），该区域只能由黑白两种颜色填充，然后根节点表示的就是这个矩形画布。
3 D7 g2 f' W) d1. 一个节点表示图中的某一个区域，如果该区域全黑或者全白，那么它将不会有children（不会被split）。
* l' f" m8 K' C+ K1 o5 m. Z  D# J' F2. 如果该节点中颜色错杂，那么把该区域平均划分成四块（左上，右上，左下，右下），这时该节点就有4个子节点。
. c6 V: k8 _. W/ Y3 y
  N! O, T# `! L- m( u( t3. 这样一直递归下去
上面就是基本的情景，然后要求写出树节点的Class表达方式，为后面问题作铺垫。

5 R4 a7 z- I; p5 ~/ o) k* ?第一个问题很简单，求树的高度，用了两种方法，一是根据树递归构建的性质进行递归遍历，另一个就是层次遍历（滚动数组）来做。
第二个问题就是将两幅大小相同的图merge为一个新图，merge规则为对于两幅图上的同一个像素点，如果颜色相同，那么颜色不变，如果1黑1白，那么merge之后为白色。当然面试官是通过画了一个示例图来讲述的题目，可能会更好理解一些。我就用最容易想到的recursive的方法来做了。
- i% Z2 S& ]: b* D
第二轮================================
warm up 5~10分钟，然后就开始类似于聊天方式的做题（是个设计题），情景很长，跟gmail里显示广告有关。精练后就是有一个server，用来处理client向server发送的request请求，这个server会针对每个request返回true or false，这样得到true的client就可以向advertisement server发送获取广告的请求。这样做的目的就是限制访问，免得ad server宕机。问怎么设计这个server。。。

第三轮================================
个人觉得这一轮命悬一线，一上来就直接做题。
+ \$ {4 L/ a9 |) b% N( B
8 ~  M: P1 Z2 l$ v4 H第一题给一个BST（树节点的索引都是不重复的），然后给一个threshhold value，该value可能出现在树中，可能没有，要求分开成两棵树，一棵节点值小于等于threshhold，另一个大于threshold。这个题关键是定义好递归方程的API（即每层递归到底要做什么），然后静下心来做。

; P2 R. d" P, i0 H: Q0 o1 B, M第二题是关于二维的region merge，当然题目被封装成描绘城市轮廓。在2维平面上的一堆矩形方块，每一个方块表示一个建筑物在地平面上的横截面，默认这些建筑都在同一水平线上，所以一个方块的数据结构可以表示为Building <startX, endX, Height>，即在水平线上左右轮廓的坐标和高度。现在问题来了，给你一堆的方块，这些方块可能重合，那么要求返回所有方块的整体轮廓。返回结果的数据结构需要自己定义。
1 e+ j9 J1 ~. A) k5 H
, \! v( ?3 S4 ?. z/ h# X
总结================================
! P6 H5 H! d! L6 Q' Q# d& A由于master才读的CS，没有任何实习经验，一直都觉得能拿到G家offer真是一种看缘分的事情，可遇不可求。。。所以面试过程中心态还算好。码代码的过程中也出现了一些bug，也有一些地方还待优化，都是面试官提醒才改过来的。所以大家不要因为在过程中出现了bug就影响情绪，个人觉得相比于bug free，过程中与面试官的交流会更加重要。然后再强调一下心态的重要性，在第三轮BST题出来的时候，我就有种“完了，好难”的感觉，因为这种树的递归题，说容易也容易，说难也难，关键是在那个时间那个地点你想明白没有，做得出来OK，做不出来也不能说明什么，真的有种看天意的感觉，所以就抱着挂掉的心里准备安安静静分析，死马当活马医。。。
/ ~$ @+ c1 f: C6 t

: L( A- y( C1 v, r, Q6 l6 ?( U5 Z来源: 报个G家offer+面筋

changhaz

CHazyhabiT 发表于 1-27-2015 12:40 AM
% o& f$ E6 {: ?+ w0 k, S+ M* Z有要求，相对位置不变。

乱写了个，请问lz这思路对吗？
7 L8 t( Y) l1 b# G

1. 
   2 P- \2 ]) e, c0 G6 X% l0 o
2. void splitTree（Node* node, int target, Node* &smalltree, Node* &largetree） {
   4 d5 @- k* m7 `: G
3.     if (!node) {
     H0 W# F* @4 @3 d8 k5 c5 `7 t% ~) ?
4.         smalltree = largetree = NULL;
   8 f, H/ `  h6 c: x7 P. K3 h% H& m
5.         return;
   
6.     }
   ; @' P+ @# q4 y. n
7. 
   0 I0 O$ p) \8 P
8.     if (node -> val == target) {
   1 ]2 y2 x0 a6 s2 @4 x1 Q
9.         smalltree = node -> left;
   
10.         largetree = node -> right;
    
11.         return;
    ! f' E& L, o. {1 y) ]
12.     }
    ( y& D5 t) H+ p" v0 H3 t% o# Z6 U
13.    
    
14.     if (node -> val > target) {
    
15.         largetree = node;
    
16.         Node* leftsmall, leftlarge;
    
17.         splitTree(node -> left, target, leftsmall, leftlarge);
    8 v( N0 n7 Q! n: v% [% o
18.         node -> left = leftlarge;
    
19.         smalltree = leftsmall
    
20.     } else {
    / q- t6 \# [; |
21.         smalltree = node;
    
22.         Node* rightsmall, rightlarge;
    
23.         splitTree(node -> right, target, rightsmall, rightlarge);
    
24.         node -> right = rightsmall;
    
25.         largetree = rightlarge;
    
26. }

复制代码

补充内容 (1-27-2015 01:54 AM):
8到12行等于的部分应该去掉。20行开始的else这段来处理相等的情况

Sophia

Big congrats!!!

averill

怎么onsite只面三轮。这要多牛的人呀。
: ]" n% I5 k( y8 y; M一般都4-5轮。